Jump to content
  • Advertisement
Sign in to follow this  
Alex131

Unity Optimization Tips on a point-and-click algorithm

This topic is 3016 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello to the community!

Recently I have decided to rewrite my isometric "game" (I thought of posting in the isometric forum, but I think that this is a problem in general game programming) using more object-oriented concepts. I also found out that much of the calculations on the game were relative to the computer's hardware capabilities (FPS) rather to the actual time (Time gap between frames).

So I started rewriting the point-and-click algorithm for the movement of my main character which now works fine, but if I try to implement it in the OnMouseMove event as well (currently available in OnMouseClick and performs very well) (I want to implement it in on mouse move because all of the games which use point and click movement, make the character move if you have clicked the mouse button and move the cursor to the location where you want to be) the game slows down a lot. I would like to ask for a possible solution to my problem which could be another algorithm, which performs faster, or optimization tips which would enhance the current algorithm and make it faster.

And here is the code:

procedure TCreature.TestLineTo(var x0, y0, x1, y1: integer);
var steep, first: boolean;
deltax,deltay,error,ystep,y,x,temp,lastX,lastY,i: integer;
begin
//1
first := false;
steep := abs(y1 - y0) > abs(x1 - x0);
if steep then
begin
temp := x0;
x0 := y0;
y0 := temp;
temp := x1;
x1 := y1;
y1 := temp;
end;
if x0 > x1 then
begin
temp := x0;
x0 := x1;
x1 := temp;
temp := y0;
y0 := y1;
y1 := temp;
end;
deltax := x1 - x0;
deltay := abs(y1 - y0);
error := Round(deltax / 2);
y := y0;
if y0 < y1 then ystep := 1 else ystep := -1;
SetLength(Path,1);
for x := x0 to x1 do
begin
if((Length(Path)=1) and not First) then First := True else
SetLength(Path,Length(Path)+1);
i := Length(Path)-1;
if steep then
begin
Path.X := y;
Path.Y := x;
end else
begin
Path.X := x;
Path.Y := y;
end;
error := error - deltay;
if error < 0 then
begin
y := y + ystep;
error := error + deltax;
end;
end;
//2
if(Path[0].X <> FootX) then
begin
for x := 0 to Floor(Length(Path)/2) -1 do
begin
temp := Path[x].X;
Path[x].X := Path[Length(Path)-1-x].X;
Path[Length(Path)-1-x].X := temp;
temp := Path[x].Y;
Path[x].Y := Path[Length(Path)-1-x].Y;
Path[Length(Path)-1-x].Y := temp;
end;
end;
//3
lastX := Round(FootX);
lastY := Round(FootY);

for x := 0 to Length(Path)-1 do
begin
y := Path[x].X;
Path[x].X := Path[x].X - lastX;
lastX := y;
y := Path[x].Y;
Path[x].Y := Path[x].Y - lastY;
lastY := y;
end;

end;


Basically the code does this:

1)Implement Bresenham's line algorithm to find the points from the line connecting the character's feet and the cursor's location (FootX is the same as x0 and FootY is the same as y0 (forgot that they could be merged)).

2)Due to the fact that sometimes the algorithm swaps the first and last points, I sort the array so that it starts with the character's feet position.

3)I convert the relative to the screen positions to actual movement directions so that after every point in the path my character's x,y coordinates get increased by an amount.

Share this post


Link to post
Share on other sites
Advertisement
I don't see anything obviously wrong with that code (other than the inconsistent indenting, and lack of comments). Have you tried using a profiler to track down the slow bit?

The only reason I can think of for it being slow would be if the path length end up high and SetLength() is slow, or the Length(Path) function is slow.

If my guess is right and that is the slow bit then try keeping a separate counter for the real length, and resizing the array in bigger increments or just starting with an array that is big enough that it doesn't ever need to be resized.

Share this post


Link to post
Share on other sites
Thanks for the advice.

I tried making the array big enough and even shortened a part of the code (still remained functional) but it seems that it still isn't fast enough to perform smoothly every time the mouse is moved while the button is pressed.

I don't know how Diablo II handles this type of movement (it is a tile based game but the movement system it is using is a combination of straight line when there aren't any obstacles and a* when there are obstacles), but it seems that I will have to make the character move only when a click has occurred and if you want to make him move, you will have to click again.

Share this post


Link to post
Share on other sites
You might want to check when and how many times this function is being called. If it's called on every mouse movement, it seems like that could result in the function being called many times with the same arguments (I'm assuming the x and y's in the code refer to tiles). This would result in running through the code many times, even if the destination tile remains the same.

Share this post


Link to post
Share on other sites
Actually the x and y's in the code are the mouse coordinates relative to the screen so every time the on mouse move event is called, these coordinates are changed for sure.

Without checking how many times the procedure is called I know that it is being used a lot (imagine the user moving the mouse to 200 different locations in a second) so it should be optimized as much as possible to cost less precious CPU time.

The problem is that besides the turning of the array upside down and it's growth I can't come up with much more to optimize. If I use a procedure I had used before I could get a small speed boost which wouldn't be seen and would affect the algorithm to end up not in the point, where the mouse cursor was, but rather in a range of 10-20 points around it.

Considering the fact that much of today's real-time strategies, RPGs, etc. require the user to be quite active with the mouse I think it wouldn't be a problem to use the algorithm, but only in the Mouse Click event so that the CPU can process the information. If you have a fast computer and the possibility to click 200 times per second it wouldn't be a problem either ... (I think that at max you can click around 20-40 times per second which won't slow down the game much and after all I doubt that people will click more than 5 times a second anyway)

Share this post


Link to post
Share on other sites
I see, I guess I jumped to the conclusion that it was tile based from the single word 'isometric'. Since that's not the case, you could make a not very elegant fix by simply not calling that function each time the mouse moves, unless a certain amount of time has passed since the last call (e.g. 25ms).

Share this post


Link to post
Share on other sites
Thanks, this thing now actually works.

I managed to implement your solution and even at an interval of 50ms I don't see much of a difference and the game runs smoothly :)

As for the word 'isometric' I think I shouldn't have mentioned it, because the game is actually isometric but the general idea of the path finding algorithm will be this:

1)Make a straight line to the location the user has clicked and begin walking towards there.

2)If on the way you collide with an object, activate the a* path finding algorithm and alter the path so that you can reach the target.

3)If you don't collide you will get to the location in a straight line which kinda makes the game feel less tile based.

I use this because if I only use the a* path finding algorithm I get the feeling that I'm not playing a game but rather a maze solver ...

Thanks again, I will post the prototype of the game once I get the base of the engine coded and at least 2 levels with functional enemies for you to slay.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!