Search code examples
javalinear-algebrapath-findinga-star

How can I reliably move a character between an array of points?

I currently have an array of points (x,y) from the result of an A* pathfinding function. This array is set up so that the first index is the point closest to the character and the next one is the next point that needs to be traveled in the path.

These points are on a grid (currently 8 pixels between each point on the grid, this is changable.)

My current strategy is to move the character to the first point, when he has arrived at that point, then move to the next one, simple as that.

I move to the first point by creating a vector from the character to that point and find how far it is. Then I find the angle and move in that direction.

// How the character is moved
double xMove = Math.cos(charAngle * (Math.PI / 180)) * 0.1 * delta;
double yMove = Math.sin(charAngle * (Math.PI / 180)) * 0.1 * delta;

x += xMove;
y += yMove;

absVx -= Math.abs(xMove);
absVy -= Math.abs(yMove);

absVX and absVy store the absolute distance left to go and it is decremented after each movement. If they are both below or equal to zero, then we have reached our destination, we remove it from the array and recalculate everything again with the next point.

I have two issues.

  1. Sometimes the character skips over a point and then he just travels forever. This is most likely due to the delta the game engine adds to the movement (slick) and the character moves too far, I'm not sure on this one though.

  2. This works fine when I single click the destination but what I need is to be able to hold down the mouse button. Currently the character just "stands still" on the first point if I hold the mouse down.

I had an idea for a solution to the 2nd problem but I'm not sure it's a good one. It is to store the location you want to go from the last mouse click but not actually calculate it untill you have passed the point you were moving to.

So, I hope someone really smart and fun can have a little conversation with me about this :D

Solution

  • About 1, the most probably cause is a rounding issue; adding these xMove / yMove introduce an small error and the x and y never really get the value of the destination, so the algorithm keeps running.

    Ways to solve:

    1 Define "reaching destination" so it allows a degree of error

    2 Find out how many "ticks" will take to the character to arrive to destination, when it "arrives", force the character position to its destination (this allows to correct accumulated error).

    Also, I would go back to graphics theory. IIRC, your path moving between points should be equal to Bresenham's line drawing algorithm. For later stages, your character could follow a B-Spline along his path.