About sprite movement, questions and solutions.

[Traveler]

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:
http://www.gameprogrammer.net/pics/outside/prob_path.jpg

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.

[arthurprs]

hi will, it's a block orientated 2d field ?

[NecroDOME]

if its a block orientated 2d field, its simple.

1: Walk forward
2: if Path = blocked (current tile + 1) then
3: Search for new dir, except the one you came from.
3.1: If there are no valid directions, follow your path back
4: Walk forward
1: start over at step 1

I once made a pacman clone with that sort of AI. 1 ghost tried to follow the player on the X-axis, 1 on the Y-axis en the other 2 just randomly walked around.

[User137]

So i imagine you have a premade path of checkpoints either using editor or path finding... There's few points i could think of:

- Having timer that has fixed interval like 50fps that doesn't run when window isn't focused would eliminate lag very easy.

- Having timer with lag count but if lag > say 200ms then decrease the lagcount by 200ms in a for loop and run physics until the counter reach <=1. (Note, in this scenario you only count physics many times within a frame, but no need to render it more than once at the end)
If calculation takes too long after a massive alt+tab, leave some of the lagcount to next frames or it may freeze...

- You can use Hypot() to count distance in 2D world from 1 point to another. This can be checked from 1 whole tile away just to set state "Tile reached - walk as near as possible to the middle of it and turn towards next waypoint".

[Mirage]

A) It depend on how you specify the path to move through. If you have some kind of precalculated path (e.g. array of coords, where index is relative physics tick) you can add an angle variable to it.
B) It can be solved by fixed FPS physics as already told User137. Fixed FPS physics has many more advantages so a recommend to use it almost always
C) Go further through the path ;)

[Traveler]

@arthurprs: no it does not have to be. I made this image to look like it but it can be anything else.

But okay,.. say for the moment we do have these small tiles. Especially in online games, lag can vary from a second to several. Checking for the next tile, during lag might very well shoot your sprite a whole tile ahead.
Agreed, this example is not likely to happen often. But still...

@NecroDOME, see above reply. its not as simple as checking for a tile marked as blocked or obstacle.

@User137. Why use a premade path? Consider using the A* algorithm to create a path for me and a second algorith to determine a suitable place for my sprite to move to on the choosen tile.
Alternatively, you could also think of a sprite controlled by my mouse, where specific X and Y coordinates for my sprite are given.

I will look into the fixed FPS suggestion. Thanks for that :)

[cairnswm]

My solution to this type of problem is as follows

The Sprite has a direction of movement (typically a deltax, deltay). Each update the sprite moves in the direction the distance identified by the time update. After moving the sprite I check that the point the sprite is moving to is still in the original direction. If the sprite has passes the destination in this last update, I move the sprite back to the destination, and then check for turns etc.

If the sprite passes the checkpoint in a 1 second update, there might be a delay in its turning as the update would just move it back to the checkpoint, and not try to move him the right distance in the next direction.

[arthurprs]

My sugestion is the same of NecroDOME

a sprite with a "facing" propriety and wall method then ....

[WILL]

The method I used for Garland's Quest, and a method I don't generally recommend involved keeping track of the sprite's direction, current tile and progress to the next tile.

This was probably one of the most disjointed means of moving and detecting objects I have ever used in ANY of my projects. It was terrible mainly because I had to detect other objects to it. which was a pain as there was multiple conditions involved from different angles to merging from non-adjacent tiles, etc... a complete mess. However at this point, I've found that so much has been built up upon this system of object movement that I can't really get out of it without rewriting the entire engine.

Avoid this trap. Stick with objects within a confined space. Committing them to a series of node and directions is not a bad thing, but keep with objects that take up a solid set of space within your map. 4-way Direction facing works well too.

If you use something more akin to a pac-man style map where it's literally all open walkable spaces or wall blocks it would be easiest to work with. For me Subject 33 (pac-man style) movement compared to GQ movement way a whole heck of a lot easier and a bit more fun to work with too.

[Andreaz]

Easy solution for problem B;

1. Store the distance between the sprite and the target (or the squared distance to avoid the sqrt).
2. Move the sprite towards the target.
3. If the distance to the target is bigger then the last frame, you have reached and passed the target.
4. Move the sprite to the target.

Totally bulletproof!

[Traveler]

Thanks all. It sounds like a few good ideas. I believe we pretty much think along the same lines. It's definitely not going to be a "pacman/tiles" kind of collision detection, though.

I believe tiles should only be used to calculate the most optimal path to the destination and nothing more. Getting from a to b is merely adding or deducting a variable value from the x and y values each time frame.

[Andreaz]

Missed one senario in the above post, in 3, it's better to check if the move vector of the sprite is larger then the vector to the target.