# Using interpolation to traverse waypoints

I'm making an isometric turn based strategy. Characters can move between tiles and tiles only, so I made a function for moving one tile in any direction. Regarding path-finding, I implemented A*, which returns a list of directions to the target, for example: North, North, West; etc. Also, the game loop calls a MovementUpadate() for the character, to check if it has reached the next tile, if it has, move to the next, if there is one. For starters, is this good or is there a better approach?

Now with the character movement/animation, I'm using linear interpolation between tiles 'till the target cell is reached. In the end, there is a lag between tiles, little, but still. Also, how to interpolates so, that the character doesn't start off fast, and slow down at the end?

void Character::MovementUpdate(){
if(moving){ //if moving, then do the calculations
float rate=(float)(moveTime-movesLeft)/moveTime; //ratio between coordinates
posX=(int) ( (float)(currentTile->x+20)*rate + (float)posX*((float)1-rate));
posY=(int) ( (float)(currentTile->y-25)*rate + (float)posY*((float)1-rate));
movesLeft--; //it has, for example 30 updates to move to that position

if(movesLeft==0){ //if no moves left, reset and move to the next
if(moveList.size()>0){
Move(moveList.at(0));
moveList.erase(moveList.begin());
}else{
moving=false;
characterSprite->UpdateAnimateSprite(moving);
}
movesLeft=moveTime;
}
}


}

• Check this for more sophisticated interpolation methods.
– Lufi
Oct 15, 2013 at 11:32

Your issues boil down largely to a single design flaw. Interpolating between waypoints in a turn-based move is insufficient. You need to interpolate along the whole path, initially using a linear piecewise interpolation most likely (easy to find the algorithm/code for that). That is, t=0 needs to be on the starting node and t=1 needs to be directly on the final node. Interpolating between each node is going to make that pause between nodes a bit harder to eliminate. The "slow start/end" feature is also going to be a bit less direct/obvious if you interpolate each waypoint than if you interpolate the whole path. You'll also be able to apply a small bit of smoothing around each node much easier if you interpolate along the whole path.
For starting out and ending slow, you want an easing function. Again, this is much easier once you interpolate along the whole path, assuming you don't actually want to ease into each individual waypoint. (You could ease out from the start node to the second node, ease in to the last node from the second-to-last, and then special case when you have no intermediate nodes to both ease out and ease in from start to end, but that's just extra work). Again, you should be able to easily find a lot of information on interpolation easing; the gist of it boils down to applying a function over t so that the actual t value you supply to interpolation is not your time-based t, which often involves some simple exponents or cos.
• @MustSeeMelons: (1) find length L of all segments' length m=|B-A| summed. (2) find positional along path d=t*L. (3) iterate over segments subtracting length m from d until d<m. (4) perform normal linear interpolation on segment with t=d/m`. Oct 17, 2013 at 16:18