gdalgorithms-list

[Algorithms] Multiuser synch

[Danny K. <dr...@we...>]

Hi there

I'm trying to implement a fairly simple algorithm but it's proving difficult
to get right, and I wondered if there is a standard method that I don't know
about.

We're developing an online demo system within our software that allows one
user (the 'shepherd') to take control of a group of other computers (the
'sheep'). It's important that the software remains in synch, otherwise the
actions the shepherd takes may not replicate correctly. So what we need is a
simple one-way synch algorithm.

What we're currently doing is this:
The shepherd tries to run at the standard frame rate. Every frame, it
broadcasts its (attempted) frame rate to the sheep.
If the sheep are within a certain range (5-25 frame behind), they use the
same frame rate as the shepherd.
If they're less than 5 frames behind, they run a bit faster than the
shepherd (if they can)
If they're less than 0 frames behind, they pause
If they're more than 25 frames behind, they try to run as fast as they can,
and they tell the shepherd.
If the shepherd knows that some sheep are lagging behind, it starts to slow
down
Otherwise it starts to speed up


This is working pretty well, but we're getting quite a lot of 'bunjee'
effects (hysteresis, I guess it would be called), where instead of settling
to a reasonably stable speed, it's slowing down and speeding up alternately.
Also when the shepherd is running slower than the sheep, it's proving
difficult to stop the lag getting below 0.

Like I say, I'm sure this is a common problem with a standard algorithm -
anyone know, or have any suggestions about improvements to my existing
system?

Best
Danny

Re: [Algorithms] Multiuser synch

[Danny K. <dr...@we...>]

Sorry, tiny correction:
 
> If they're less than 5 frames behind, they run a bit faster than the
> shepherd (if they can)

I meant a bit slower, of course

Danny

Re: [Algorithms] Multiuser synch

[Jon W. <jw...@gm...>]

Danny Kodicek wrote:
> We're developing an online demo system within our software that allows one
> user (the 'shepherd') to take control of a group of other computers (the
> 'sheep'). It's important that the software remains in synch, otherwise the
> actions the shepherd takes may not replicate correctly. So what we need is a
> simple one-way synch algorithm.
>   

First, you need to run physics at a fixed rate everywhere, not tie it to 
the graphics frame rate. See 
http://www.b500.com/~hplus/graphics/game_loop.html for example.

Second, you probably want to use the lock-step network sync method. See 
the "1,500" archers article for a great introduction: 
http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_288_network_.php

Once that's done, if you still have questions, you may want to check out 
the FAQ for Multiplayer and Networking over at gamedev.net; it has more 
networking and multiplayer references (all the way from basics, through 
classics, to avant-garde): 
http://www.gamedev.net/community/forums/showfaq.asp?forum_id=15

Hope this helps!

Sincerely,

jw

Re: [Algorithms] Multiuser synch

[Danny K. <dr...@we...>]

Hi, Jon 
 
> First, you need to run physics at a fixed rate everywhere, 
> not tie it to 
> the graphics frame rate. See 
> http://www.b500.com/~hplus/graphics/game_loop.html for example.

Actually, what I'm running is a science simulation, and because it needs to
be deterministic (or as near as we can make it) we do tie it in with the
frame rate. It's more important that they're synched than that they have
smooth physics experiences.

> 
> Second, you probably want to use the lock-step network sync 
> method. See 
> the "1,500" archers article for a great introduction: 
> http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_2
88_network_.php
> 
> Once that's done, if you still have questions, you may want 
> to check out 
> the FAQ for Multiplayer and Networking over at gamedev.net; 
> it has more 
> networking and multiplayer references (all the way from 
> basics, through 
> classics, to avant-garde): 
> http://www.gamedev.net/community/forums/showfaq.asp?forum_id=15

Thanks for these references, that's really helpful. It's always hard to know
where to look (although I should have thought of trying gamasutra and
gamedev)

Best
Danny

Re: [Algorithms] Multiuser synch

[Jon W. <jw...@gm...>]

Danny Kodicek wrote:
> Actually, what I'm running is a science simulation, and because it needs to
> be deterministic (or as near as we can make it) we do tie it in with the
> frame rate. It's more important that they're synched than that they have
> smooth physics experiences.
>   

If you want it to be deterministic, you absolutely need a fixed time step.

Sincerely,

jw

Re: [Algorithms] Multiuser synch

[Danny K. <dr...@we...>]

> Danny Kodicek wrote:
>> Actually, what I'm running is a science simulation, and because it needs 
>> to
>> be deterministic (or as near as we can make it) we do tie it in with the
>> frame rate. It's more important that they're synched than that they have
>> smooth physics experiences.
>>
>
> If you want it to be deterministic, you absolutely need a fixed time step.

This is kind of going off-topic and I suspect that we're using different 
words for the same thing. My point is that the physics isn't tied to real 
time at all, time is simply measured in frames. It is a fixed time step, in 
the sense that as long as two people run for the same number of frames, at 
the end they will be in the same position (however long it takes in real 
time)

Danny