Sign in to follow this  
mzechner

rts networking & time based movement

Recommended Posts

greetings, i'm currently in the design phase of a simple tower defense variation that should be focused on multiplayer. while reading the aoe networking article on gamasutra i came across the following conceptual problem: as describd in the article a turn is composed of first processing all commands received from all players ( moving units, etc ) and then simulating unit actions n frames for the rest of the turn. the duration of a turn is the maximum round trip time, the number of frames per turn is equal to the number f frames the slowest machine can process during that duration. due to various factors the time taken for each frame of a turn will vary on the different machines. when using time based movement this leads to a problem. even though each machine executes the same number of simulation steps per turn the time used to do that will vary among the machines and so will the final positions/orientations of the units for that turn. over time this will lead to desynchronization. a small fictional example: - a turn consist of 2 frames and has a duration of 40 msecs - the position of a unit is updated each frame by p' = p + t*d where p' is the units new position, p is the units position in the previous frame, t is the time taken by the current frame and d is the units direction scaled to the units speed - for simplicities sake assume that p for the first frame is (0,0) and d stays constant at (1,0) for that turn ( it moves to the right at a speed of 1 unit per msec ) - on machine one frame one takes 19 msecs, frame two 18 msecs, so the unit ends up at p' = ( 37, 0) - on machine two frame one takes 23 msecs, frame two 27 msecs, so the unit ends up at p' = ( 50, 0) both machines end up with different game states that might be used to decide what action to take next potentialy leading to macro scale divergence ( on machine one the unit attacks a nearby enemy in its radius on machine two it heads in another direction). i have no clue how to solve that problem other than using frame basd movement. i'd appreciate any hints and thoughts on the matter. sorry for the lenghy post, my typos and my english

Share this post


Link to post
Share on other sites
Yes, you have to use a fixed time-step instead of a variable time-step.

E.g. use a value of 10ms for t every time you update.

[edit]
You can implement this inside a variable time-step system. Here's a quick example (tho it's not perfect due to precision probs!):
void update( float elapsedTime )
{
const float stepSize = 0.01;
elapsedTime += m_leftOvers;
while( elapsedTime >= stepSize )
{
updateWorld( stepSize );
elapsedTime -= stepSize;
}
m_leftOvers = elapsedTime;
}

Share this post


Link to post
Share on other sites
thanks for your answer. i'll probably go the easy road and use fixed time steps for now. i think another solution would be to adjust the step time based on the turn duration and the number of maximum frames. this should approximate time based movement well in case the turn duration and maximum frames estimates are good.


update( turn_duration, frames )
step_time = turn_duration / frames
for i = 0; i < frames; i++
frame_start = time()
updateWorld( step_time )
frame_time = time() - frame_start
if frame_time < step_time
sleep( step_time - frame_time )


coupled with fixed point math and carefull rand() usage it should be straight forward.

thanks for the suggestion

Share this post


Link to post
Share on other sites
I encourage you to stick to a fixed time-step if you want your simulation to stay in synch.

To demonstrate why, I'll reuse your previous example, but add some acceleration as well:
Quote:
Original post by mzechner
- a turn consist of 2 frames and has a duration of 40 msecs
- the position of a unit is updated each frame by p' = p + t*d where p' is the units new position, p is the units position in the previous frame, t is the time taken by the current frame and d is the units direction scaled to the units speed
- for simplicities sake assume that p for the first frame is (0,0) and d stays constant at (1,0) for that turn ( it moves to the right at a speed of 1 unit per msec )
- Lets say that d is the units direction *and* speed.
- Lets add some acceleration so that d starts at (1,0) and is updated each frame by: d' = d + t*a, where a is (1,0). This computation is done before the computation of p'.

- on machine one frame one takes 10 msecs, frame two 30 msecs
- on machine two frame one takes 20 msecs, frame two 20 msecs

Machine 1:
Original: d(1,0), p(0,0)
After frame1: d(11,0), p(110,0)
After frame2: d(41,0), p(1340,0)

Machine 2:
Original: d(1,0), p(0,0)
After frame1: d(21,0), p(420,0)
After frame2: d(41,0), p(1240,0)

Because each machine used different time-steps, the end result of their integrations are slightly different, even though they both ran for 40msecs!
This small errors are always going to occur with variable time-steps, because the update algorithm that we most often use in games (a'=a+t.b) is a known as Euler's method of integration and in some cases it's a pretty poor approximation.

Share this post


Link to post
Share on other sites
yes, the simulations will go out of synch badly when using the actual frame time for t on each machine. however, i think if one uses t = turn_duraton / frames, which is always the same on all machines one gets the desired behaviour. let me try to illustrate it with your example:

Quote:

- Lets say that d is the units direction *and* speed.
- Lets add some acceleration so that d starts at (1,0) and is updated each frame by: d' = d + t*a, where a is (1,0). This computation is done before the computation of p'.

- on machine one frame one takes 10 msecs, frame two 30 msecs
- on machine two frame one takes 20 msecs, frame two 20 msecs


- additionaly the turn duration is 40 and the number of frames for this turn is 2 ( the slowest machine needs 20 msecs to process one frame, roundtrip time is 40 msecs ). both machines use this values according to the aoe networking model
- given the turn duration and number of frames for this turn the simulated time span for every frame on both maches is the constant t = turn_duration / frames = 20 msecs

machine 1:
original: d=(1,0) p=(0,0)
frame 1: d=(21,0) p=(420,0)
frame 2: d=(41,0) p=(1240,0)
as frame one only took 10 msecs the code would sleep for an additional 10 msecs that frame. the second frame took 30 msecs so no sleep would be executed. the turn took 10+10+30=50msecs, 10msecs more than the optimal turn duration. the simulation however simulated 2 frames with exactly 20 msecs duration=t each.

machine 2:
original: d=(1,0) p=(0,0)
frame 1: d=(21,0) p=(420,0)
frame 2: d=(41,0) p=(1240,0)
this machine also simulated 2 frames with exactly 20 msecs duration=t each. the whole turn took the optimal 40 msecs

both machines end up with the exact same gamestate as they used the same fixed time step for each frame. the only difference is the real time it took on both machines to simulate the whole turn.

three cases can happen:
1) the machine needs less than the fixed time step each frame. here all is fine as at the end of each frame the machine waits for t-actual_t msecs. the whole turn will take exactly the calculated turn duration. the simulatin stays in synch. ( machine 2 above )
2) each frame needs more than the fixed time step. the simulation stays in synch but the actual turn duration will be bigger than the optimal turn duration.
3) some of the frames will take longer than the fixed time step. the simulation stays in synch but the actual turn duration will be bigger the optimal turn duration ( machine 1 above )

in summary: the algrithm uses the same fixed time step for each frame of a turn on each machine. the fixed time step is recalculated each turn based on round trip time and minimal frame rate. therefor the simulation stays in sync on all machines. each machine will additionaly try to take exactly the turn duration calculated approximating time based movement.

i really appreciate this discussion. thanks for your time and help. i hope this is helpful to others to, thus the lenghty posts

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