Sign in to follow this  
ZeHa

Dead Reckoning vs. thin corridors

Recommended Posts

Hello, I'm programming a tile based game engine which makes use of the dead reckoning technique, with timestamps and calculating position from the last direction change. One problem for me: if I have a thin corridor, where the dude should walk into, he sometimes passes by, because he walks a few pixels too far (e.g. because the framerate makes the player walk 3.7 pixels per frame). I already found a perfect "Pacman like" algorithm, for letting the player press the direction key a little earlier than needed, and the dude walks on until he can turn to the desired direction, and that worked really well, but only in "fixed framerate, fixed pixel steps" environments. I also experimented with doing my update(time) function call more often than my render(time) call, e.g. when the last frame and the current frame have too much time in between. But this could of course also slow the game down, because the update function also takes its time. Now I got a new idea: As soon as the game knows that the player wants to walk into a corridor, it could calculate the timestamp on which the player would be at the correct position to turn, and then add this timestamp to a list. Now it would be guaranteed, that the update function would definitely be called with that timestamp, because the game could always check if there are timestamps in the list which lie a bit in the past and haven't been updated yet. Is this a good / common approach? Or would there be better techniques? Of course there would be also making the bounding boxes smaller, but this isn't perfect because as soon as the framerate drops too much, the problem would be the same again. So, what else is available to try?

Share this post


Link to post
Share on other sites
The simplest solution is to perform the updates at a fixed rate to get consistent behavior. Dead reckoning usually refers to estimating where an object should be based on its past behavior, as in a network game that estimates the locations of other players (and then corrects the locations with data received from the server).

Share this post


Link to post
Share on other sites
I'd refer to Pacman as an example.
In a Pacman map, each intersection or bend has exactly one point, in the center, where Pacman or a ghost can turn; these points and the corridors form a simple navigation graph that constrains the movement of the five actors.
If the length of Pacman's steps is a divisor of the grid size, he'll automatically stop at these special point every frame, while if you drop this guarantee you can simply check the navigation graph to see if the calculated straight movement crosses an intersection.
In that case, if user input wants Pacman to turn, you can break the movement into a first part in the old direction and a second part after turning.
Graphically, Pacman will be near the corner one frame and round the corner next frame, at variable fractional distances.
This trivial calculation works with any timestep and scheduling, without complications, and also applies to forced turning in corridor bends.

P.S. This is not dead reckoning, Pacman's movement is exactly known and completely deterministic. Dead reckonong is predicting an unknown position from an old position and an inexactly known velocity (usually assuming constant speed).

Share this post


Link to post
Share on other sites
Ahh okay, well that would be somehow similar to what I suggested, I guess. Knowing that the player will turn, the game can predict the exact turning point and then set the new position and direction as soon as the timestamp has passed. I'll try to implement that ;)

Well, as far as "Dead Reckoning" goes, of course I don't have to predict (because at the moment it's a single player game), but the technique I use to calculate the current position is exactly the same (using timestamps instead of just adding up the position values).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this