Sign in to follow this  
pjuke

Movement-algoritm over the network ?

Recommended Posts

Yo! I've been experimenting with some network programming lately and I've also been experience some huge problems.But my main-issue is how to do the movement so it will be as synced as possible over the network. And currently I've found one way to do it: On the client-side, I'm updating the position like "position += velocity * dt" where dt is deltaTime between every frame. Then, every 30th of a second, a package which contains player position and velocity is sent to the server which it self broadcasts this package to every client connected. And when a client receives a package, it updates the player position and the velocity to the given in the package. This movement is kinda smooth over the network, and very very synced, just a few millisecs out of sync. BUT. Is this a proper way of doing it? I mean, by feeding my server with 30 packages / s ? It doesn't sound very well to me... But at first, I was only sending that package when a player started to move and when it stopped, this caused a snapping to occur when the player stopped because the calculated position on the client wasn't the same as in the package for some reason, does anyone knows why? So my question is; How to do a proper movement over the network which is in "real-time" ?

Share this post


Link to post
Share on other sites
I tend to just send key input to the server and let it simulate the game on its own. Then at a constant time it broadcasts its server state to the clients. (Using delta packets and such).

Then use an extrapolation and interpolation algorithm on the clients. If you look at EPIC in the Forum FAQ it might give you some ideas.

Also make sure that the server has an authoratative state and a fixed update step. I'm not sure from reading what you've written if that's what you have. If you're just letting clients send positions to the server and then the server just immediately sends them out then your networking is problematic.

There's some tricks you can do if your gameplay allows it. One being using inertia. So if your character moves in one direction have them ever so slightly come to a stop. If they try to start moving put a slight acceleration into it. I use that kind of idea in my tests and it works wonders.

Also is this TCP or UDP?
Quote:
Is this a proper way of doing it? I mean, by feeding my server with 30 packages / s ? It doesn't sound very well to me...

In TCP never send packets at 30 times per second. Stick to 10 packets or less and throttle based on latency. (I assume your monitoring RTT between the server and client). In UDP I'm not sure what the normal packet rate is. My trick for it is to get it to work with the least amount of packets imaginable. Like try 5/sec. If it plays alright with that many then you should be fine.

Share this post


Link to post
Share on other sites
Send the velocity vector of the player to the server. Don't send the actual key presses otherwise the server now needs to know about key mappings.

To explain the snapping you are seeing think of it like this you were walking to the left you and then stop you tell the server about this change in velocity. It takes time to get there. During that time you start walking to the right, you send a packet to the server informing it of moving to the right. After this packet is sent you receive the response from the server from when you stopped moving left and jump back to the point were you stopped moving left. You then receive a response from the server about moving to the right now depending on your implementation you may jump again.

This also means you game is open to warp hacking, since I can falsify my position.

Share this post


Link to post
Share on other sites
Better yet, you'd probably just send an event-type, rather than a velocity vector. That's nearly as bad as the position-authority be given to the client.

Ideally the simulation authority is the server, not the client, so it wouldn't matter what the client was inter/extrapolating anyway (so it's own velocity is moot). Only which actions the user is making, and let the server simulate it from there.

By event I mean your coded packet to specify MOVE_FORWARD (or whatever) and the duration it was held down for the step between issuing an update. You wouldn't need to know the key bindings, just the action of the keys (moving forward, strafe right, jump, etc).

Share this post


Link to post
Share on other sites
I am fairly new to this but here is what I do and I find to work pretty well.
You have a client and server that both host in broad terms similar simulation engines of the game.
All events are validated both locally and remotely. Local validation serves the purpose of having smooth interaction while upholding game rules this validation can be done fine grained. Remote validation serves the purpose of keeping game consistency at any cost.

When you wish to move forward you send a event to your local simulation if the event passes a pretest it is transmitted to the server. I transmit position, time and event type. When the server receives the event it also validates the event and if ok the event is activated on server also. Otherwise reject and post back to client.
Before this happens some time may pass and in order to keep the two simulations in sync as much as possible. So when another event happens that affects motion you again transmit the position, time and event.
This time the server can calculate the exact position of the player by delta_time * first_position and then validate it against the second position. If it is close enough (position +/- some_epsilon) then set the exact position and proceed otherwise do something to maintain consistency.

Basically only send information with regards of what you are doing or intent to do. Also you need some periodic synchronization to ensure consistency but this can be done at a low frequency.

Obviously there is a lot more to it when adding motion prediction etc. but this was the basic Idea I started from and slowly progressing :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Sirisian
If you look at EPIC in the Forum FAQ it might give you some ideas.

Ok, so this is the actually algoritm I should use or what?

Quote:
Original post by Sirisian
Also make sure that the server has an authoratative state and a fixed update step.

Before the server broadcasts, it saves all the variables of every player, so yes, the server holds the player positions and velocity as well.

Quote:
Original post by Sirisian
Also is this TCP or UDP?

It's TCP!

Quote:
Original post by Sirisian
Stick to 10 packets or less and throttle based on latency.

So I should actually send packages all the time while Im moving to the server, containing velocity and positioin ?

Quote:
Original post by Oliii
http://gafferongames.com/game-physics/networked-physics/

Ok, is this for 2D-games as well as 3D ?

Quote:
Original post by Stonemetal
Send the velocity vector of the player to the server. Don't send the actual key presses otherwise the server now needs to know about key mappings.

Im sending the velocity vector, not the actual key. I maybe didn't explain that very well..


And maybe I should explain a little more how my movement actually is done?
In the main-loop of the client, a function called move_player(dt) is executed every loop. dt is the deltaTime between every frame...
Then in move_player, it take the last velocity-vector received from the server, and sets the player position like "position += velocity * dt * 130", where 130 is 130 pixels/second to move.
Then every 30th of a second, a package to the server is sent with the calculated position, and the velocity. THIS package is not sent back to the client that sends it, it is only send to the other clients connected.

Then when the client receive a package, the client executes set_position(position, velocity), which sets a position- and velocity-vector for the player, given in the package.

--
But w/e.
The only thing I really need to know, is HOW I'm supposed to do in order to make it as good as possible. I looked at EPIC and didn't really get it how it works, and I also looked Glenn Fiedler's page which seems to have a good "algoritm".


[Edited by - pjuke on June 5, 2009 9:54:19 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by pjuke
And maybe I should explain a little more how my movement actually is done?
In the main-loop of the client, a function called move_player(dt) is executed every loop. dt is the deltaTime between every frame...
Then in move_player, it take the last velocity-vector received from the server, and sets the player position like "position += velocity * dt * 130", where 130 is 130 pixels/second to move.
Then every 30th of a second, a package to the server is sent with the calculated position, and the velocity. THIS package is not sent back to the client that sends it, it is only send to the other clients connected.


Bolded the part of concern. Why would you send the client position/velocity/anything to the server, which then would be relayed to other clients. To me, it sounds like a vulnerability.

The server should be simulating the clients and telling the clients where they ought to be. The clients would only interprate the data from the server and try to compensate to stay in sync... Never the other way around.

Share this post


Link to post
Share on other sites
If you don't worry about cheating, then sending pos/ori/vel 30 times a second is a fine way of doing it, and will result in smooth, natural gameplay. It will, however, allow for fly/teleport/aim hacks, should your players find your game interesting enough that they want to hack it.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
If you don't worry about cheating, then sending pos/ori/vel 30 times a second is a fine way of doing it, and will result in smooth, natural gameplay. It will, however, allow for fly/teleport/aim hacks, should your players find your game interesting enough that they want to hack it.


Yeah, I know it works in the way I'm doing it, but I just thought that it maybe would be a better / more proper way of doing it than this ?

I don't really care about cheating, this game is for a final-test at my school in programming, so it's only for educational and fun purposes only :)

But again, is there any better way?
Because I've seen lots of ways, some are including a timestamp on the package as well to stay in sync or something. Im just curious!

Share this post


Link to post
Share on other sites
If it's for a school project, it might not matter, so long as you make note that you realize it's a security flaw, but for testing purposes, allowed it to fly.

Otherwise, it'll be a smoother and more forgiving system than extrapolation (as I've recently been toying with, and finding out, on my own).

Since it's LAN only, if someone does cheat, I mean you can sock them in the nose.

Share this post


Link to post
Share on other sites
I think you way you do it is fine. The better way would be to have the server being the authority (gaffer's article), as a security precaution, but for your purpose, that's overkill. You can link the article as a reference.

You can also look at how Source does its interpolation / extrapolation, but that's also overkill :)

Share this post


Link to post
Share on other sites
Quote:
Original post by catch
If it's for a school project, it might not matter, so long as you make note that you realize it's a security flaw, but for testing purposes, allowed it to fly.

Otherwise, it'll be a smoother and more forgiving system than extrapolation (as I've recently been toying with, and finding out, on my own).

Since it's LAN only, if someone does cheat, I mean you can sock them in the nose.

Our goal is to make it public actually, but you know, the server also keeps position and velocity of the players, so if someone wants to cheat or something, the server wont let them, so I don't really know if you actually can cheat, you are only gonna fool yourself :)

But extrapolation, is that what EPIC is all about?
If so, does anyone have a good "step by step"- tutorial of how it works? Because I downloaded it and checked the source, but it's so much code so I get kinda confused.

Quote:
Original post by catch
I think you way you do it is fine. The better way would be to have the server being the authority (gaffer's article), as a security precaution, but for your purpose, that's overkill. You can link the article as a reference.

You can also look at how Source does its interpolation / extrapolation, but that's also overkill :)

Ok so I guess I'll be fine to spam my server over TCP with 30 packages / s :)

But my very last question is actually; What is Interpolation and Extrapolation, since im Swedish, some words are not that common to me, and I haven't really found any article or something describing what it actually means.

Take care.

Share this post


Link to post
Share on other sites
extrapolate means predict. It's basically algorithms to predict the position of an object forward in time, given his previous positions.

interpolation is calculating any position between a set of known positions to give a smooth motion.

Some algorithms use curve-fitting (catmul rom, b-splines...), trying to compute a smooth path between a set of points.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
extrapolate means predict. It's basically algorithms to predict the position of an object forward in time, given his previous positions.

interpolation is calculating any position between a set of known positions to give a smooth motion.

Ok, so then I'm using extrapolation in my game, since it's like "position += velocity * dt" .

But interpolation still confuses me a bit, is there any good example out there showing it how it works?


Quote:
Original post by hplus0603
In Swedish, "to interpolate" is "interpolera" and "to extrapolate" is "extrapolera." So, not that far from the English versions of the words :-)

Haha, yeah, I also checked it up but it didn't make any sense to me, lol.

Share this post


Link to post
Share on other sites
With interpolation, you receive position data P0, P1, P2 ... at time t0, t1, t2 ...

Assuming the data comes in at a regular interval, then you make it so that you plot the position at time (Tcur - (t2-t1)), where Tcur is == t2 when you receive P2, and moves ahead at real-time pace.

Let's call the update interval (t2-t1, also t1-t0 etc) the Tu.

The position of the object at time T is then P1 + (P2-P1) * (Tcur - t2) / Tu.

More generally, instead of "1" and "2" you can use "N-1" and "N" when you have received an update for step N.

This will have the effect of showing the interpolated entity moving in linear segments between each update point; when you know that the entity was at point P1 and P1, the interpolation will move through exactly those points, which in general is a lot more precise match to the actual path of the object on the sending side, than a forward-extrapolated entity position would be. The draw-back is that you have to display the object back in time.

Share this post


Link to post
Share on other sites
it's explained here...

http://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Share this post


Link to post
Share on other sites
Oh thank you for the explanation, I think I got it!
But what do you mean by displaying it back in time?
Because as far as I know, CS:S for example (thanks Olii for the link) is very synced between the players, right?

But maybe the time differance is so small that it's almost unnoticeable ?

I'm sorry if I'm bothering you with all my questions (lol), but I'm just new into this and wanna make sure I make it as good as possible and not some random hoax that just swallows my CPU...

Share this post


Link to post
Share on other sites
in the article, they take a sample back in time by (t - updaterate * 2). So it means that until you receive the next scheduled update, you will be interpolating. If a couple of packets are delayed / lost, you will be extrapolating a little.

That occurence would be pretty rare in normal conditions.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
in the article, they take a sample back in time by (t - updaterate * 2). So it means that until you receive the next scheduled update, you will be interpolating. If a couple of packets are delayed / lost, you will be extrapolating a little.

That occurence would be pretty rare in normal conditions.

Ah now I get it!
What a cleaver way of doing it, lol.

I think I finally got it, just gonna read that article in and out and then experiment a bit !

Thank you once again!

Share this post


Link to post
Share on other sites
Ok, so just to make sure Im doing this right:

I've got three positions (P0, P1, P3) stored in a buffer at (T0, T1, T3), just like you said.
Then my updaterate is every 50 millesecond (my Tu, right?), so its 20 updates / second.

And now, correct me if I'm wrong:
The position of the object at time T is then P1 + (P2-P1) * (Tcur - t2) / Tu.

The "time" we are talking about, is just a counter going on in the background which is synced between clients and the server, right?
So lets say that T0 = 100, T1 = 150, and T2 = 200.
And just to make it simple, we use only one axle in the position (lets say the X-axle):
P0 = 10, P1 = 22, P2 = 34.

So now, I want to interpolate between P1 and P2 to get a smooth movement.
How should I do that? Should I calculate that equation every millisecond in the loop to get the position at exactly that tick, or what?
Because I want to interpolate for 50 milliseconds until my next update arrives, right?

And also, how would the equation look like if I want to calculate the position at say the 157th tick (or any tick between T1 and T2)?

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
You don't calculate it every millisecond, unless you have a frame rate of 1,000 :-)


Ok lol, so how often should I calculate then ?
My framerate is locked to 60 btw.

And also, can you please help me with my previous questions, because I do understand the logic behind it, but not really how it should look in the equations and so...

Because I really don't understand how to use the equation you gave me. :/

[Edited by - pjuke on June 9, 2009 2:04:54 PM]

Share this post


Link to post
Share on other sites
Quote:
I really don't understand how to use the equation you gave me. :/


It sounds like you're taking water over your head. I suggest you step back and work on learning the fundamentals first.

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