Coordinate based travel through multi-line path over elapsed time
- by Chris
I have implemented A* Path finding to decide the course of a sprite through multiple waypoints. I have done this for point A to point B locations but am having trouble with multiple waypoints, because on slower devices when the FPS slows and the sprite travels PAST a waypoint I am lost as to the math to switch directions at the proper place.
EDIT: To clarify my path finding code is separate in a game thread, this onUpdate method lives in a sprite like class which happens in the UI thread for sprite updating. To be even more clear the path is only updated when objects block the map, at any given point the current path could change but that should not affect the design of the algorithm if I am not mistaken. I do believe all components involved are well designed and accurate, aside from this piece :- )
Here is the scenario:
public void onUpdate(float pSecondsElapsed)
{
// this could be 4x speed, so on slow devices the travel moved between
// frames could be very large. What happens with my original algorithm
// is it will start actually doing circles around the next waypoint..
pSecondsElapsed *= SomeSpeedModificationValue;
final int spriteCurrentX = this.getX();
final int spriteCurrentY = this.getY();
// getCoords contains a large array of the coordinates to each waypoint.
// A waypoint is a destination on the map, defined by tile column/row. The
// path finder converts these waypoints to X,Y coords.
//
// I.E:
// Given a set of waypoints of 0,0 to 12,23 to 23, 0 on a 23x23 tile map, each tile
// being 32x32 pixels. This would translate in the path finder to this:
// -> 0,0 to 12,23
// Coord : x=16 y=16
// Coord : x=16 y=48
// Coord : x=16 y=80
// ...
// Coord : x=336 y=688
// Coord : x=336 y=720
// Coord : x=368 y=720
//
// -> 12,23 to 23,0 -NOTE This direction change gives me trouble specifically
// Coord : x=400 y=752
// Coord : x=400 y=720
// Coord : x=400 y=688
// ...
// Coord : x=688 y=16
// Coord : x=688 y=0
// Coord : x=720 y=0
//
// The current update index, the index specifies the coordinate that you see above
// I.E. final int[] coords = getCoords( 2 ); -> x=16 y=80
final int[] coords = getCoords( ... );
// now I have the coords, how do I detect where to set the position? The tricky part
// for me is when a direction changes, how do I calculate based on the elapsed time
// how far to go up the new direction... I just can't wrap my head around this.
this.setPosition(newX, newY);
}
