For quite some time now, I've been thinking about a solution for a problem. It involves a very common subject namely: sprite movement.
The image below may hint you towards a tile based game, but really, if you give it some thought, it may apply to a lot more games. And while the solution may appear simple at first, it really is not.

My main intend for this post was actually to ask a question, but while writing, I came up with a possible solutions myself, added some experiences from past projects and some other random thoughts as well.

I ask you to just read it over, give it some thought. And if possible write up an answer yourself. I'm very interested to see what else is possible.

Anyway, let me explain the situation first.

Consider for a moment the image below:


You see a sprite walking a patch of dirt. The engine has marked all red tiles as obstacles and thus cannot be walked on. The sprite is following the direction of the white arrow.
There are two turns the sprite has to make in order to walk off the patch, both marked by a green dot. The blue dot represents the players 'checkpoint'.

Now, here's the main question:
- A) How do you calculate when the sprite is to take a turn?
While answering the first question, keep the next in mind:
- B) How do i prevent the sprite from missing the turn?
And if you have these two covered
- C) How does the sprite continue when these questions are countered?


In Village Defense, I used the following solution for question A.
I made all sprites to have one or more check points. I used them to check against other points of interest, such as turns in the road, obstacles, or to calculate the direction of the projectiles. NB, I dont check for tiles. They restrict the sprite's movements. (Imagine your tiles being much larger or even smaller) Also, checking for tiles does not correctly solve question B.

Ok, so in this image, the sprite is moving down. He is moving down until his checkpoint collides with the green dot. If that is the case then he will change direction. After that he will move up until,.. well you get the idea. In theory, this works like it should. There is however one tiny problem. Lag. Lag is the reason why I ask question B. Lag is the reason why this solution wont work.

The issue of time based movement instead of framebased movement has been discussed countless times already so I'm not going over that here. But it is exactly what is causing problems here. See, in VD I was constantly checking for the green dots to match the blue one.
Figuring that with each dot say 3x3 pixels large, and a movement of less than a pixel each cyle, a hit was bound to happen..... right?
Ah well, no, not exactly!

Consider for example a simple alt-tab action or perhaps the antivirus scanner starting it's daily check. A mere 1 second delay is enough to make the sprite 'jump' 4 pixels, possibly missing the collision and there you have it. The sprite in question will never ever hit its target again. (That would make your game look stupid in the process, too).

Ok,.. so thats is not really going to work. It does however give some insight in the answer of B. Because correct me if I'm wrong. Question B cannot be prevented. At some point or another there will be lag and the sprite will miss its turning point. It's what we do afterwards that counts.

Ok,. so with all this in mind I came up with the following.

Suppose I do not calculate a collision of the green and blue dots, with each cycle. Instead, I calculate how much time I have left to reach a green dot and based on the answer, move accoordingly.

This way I can also check if the sprite is past a turn (timeToTurn < actualTime), and even jump to the direction it should have gone instead.

So there you have it:
A) calculate time it takes to reach a certain point.
B) it's not possible to prevent it.
C) calculate the time after turntime and move in the given direction.

So what do you think? It sounds like a solution, no? I wonder thought how the 'big guys' are doing this. I've seen similar situations in professional games. But they seem to take this a couple steps further. During lag I see animations run faster, attacks (ie from cannons and tanks) appear to speed up to match with the rest. Are those similar things using the same solution or is there something else?

Anyway, love to hear other opinions & thoughts.