Movement prediction discussion

[Downsider]

Soo. I've been planning on replacing Quake's protocol for a whole so I can get a bit of indie game development off to a better, more modernized style of netplay.

Since I recently got grounded for around a week, and when I get grounded I'm not allowed to do anything, from going out, to going on the computer, it's all restricted. Thus, since I don't have much to do, I've decided to go through some planning stages of the more complicated parts of my game.

Right now I read a few articles on how to accomplish something like this. One was the Source networking article, which shed quite a bit of light on how something like this is accomplished, another was Carmack's on why a replacement for NetQuake was needed and a generalization on how he's gone about writing things for QuakeWorld, and the last one was a general article that was less specific to a game engine but discussed it in depth as well.

I understand the concepts involved, I think, but I've got some questions as well. I'll explain what I think would work, and ask some questions. If anybody spots any problems with my plan, reply, please.

This only predicts the local player. The other clients have not been considered yet.

1) Input from controls and server. If packet arrives with a time that's greater than the last recieved packet's time, drop the packet; it was recieved out of order.
2) Input is preformed on the client. (Player moves, interacts with world.)
3) Store position in an array of history.
4) Compare predicted position to where the server thinks you were when the packet was sent by the server and the corresponding time in history. If correct, or within a threshold, do nothing. If incorrect, jump client to the proper position. It'll probably have to be smoothed over several frames for the best effect.
5) Here's where my question is. If something like an explosion pushes the player on the server, or there's any paradox such as that, won't the client and server now be out of sync until the player stands still for a few seconds, at which it should be restored? I read somewhere that you must "record" input and "replay" it from the position corresponding to the time in the history array in which the correctional packet was sent. Is there another way?

This thread is also here so I can collect my thoughts as best as possible.

Hopefully you guys can answer some of my questions or discuss a better method.. Thanks.

P.S... I haven't really made this thread so people can go and say "But movement prediction sucks! It makes things so inaccurate for the player!" I'm not really concerned about that so much as immersing the player as best as possible. Having choppy and delayed movement really sucks, especially on the PSP, where with WiFi, packet loss happens quite often..

I'm also considering if I should add CSQC support and do it with a CSQC and SSQC approach and remove movement code from the engine alltogether.

[mh]

The other thing about QW-style prediction that you've left out, although I guess you're aware of it, is that the underlying network transport layer is quite different.

The first move was to scrap the current net code. It was based on a reliable stream as its original primitive (way back in qtest), then was retrofited to have an unreliable sideband to make internet play feasable. It was a big mess, so I took it out and shot it. The new code has the unreliable packet as its basic primitive, and all the complexities that entails is now visible to the main code instead of hidden under the net api. This is A Good Thing. Goodbye phantom unconnected players, messages not getting through, etc.

[Downsider]

Yeah I read that as well. I didn't put much consideration into it and I don't think it's ridiculously important, although if it turns out being so, I could make nessecary changes, of course.

[mh]

It might not be a big deal, but I wouldn't assume that Q1's prediction code isn't reliant on it. Either way I genuinely wish you luck with this; it would be quite something if you could get NQ working well and remain compatible using this approach.

[frag.machine]

If you're going to scrap everything and start fresh, I'd suggest you to get some inspiration from Quake III protocol. While quite different, it keeps enough resemblance to previous incarnations:

http://www.tilion.org.uk/Games/Quake_3/Network_Protocol

Also, a couple years ago I stumbled in some very interesting articles from Michael Abrash in the subject. Too bad I lost the URL (among other important things) in my notebook HD crash.

[Spike]

QW prediction works by the client remembering input frames, and applying those input frames to the state received from the server.
This requires three things.
1: Client and server must share movement code to some extent. QW its just players. Basically you need to do lots of work here...
2: The two instances of movement code also need to be able to feed the same inputs into the movement code, including time. Basically you need to timestamp inputs properly.
3: The client needs to know which input frames are already applied, so it knows which ones still need to be applied. Basically the server needs to echo an input frame number somehow.

QW(and Q3) generates a new input frame every graphical frame. You can interpolate if you want to generate input frames less frequently.

[Downsider]

The goal here really isn't to maintain compatibility with default NetQuake, I guess you could say.

So if I'm understanding correctly, each input packet also needs to be sent with an extrapolated time variable, extrapolated from the last good packet from the server, then the server will have to preform it's physics based on the time passed in the last frame, utilizing the time between the last movement packet and the current one, and the client will do so as well.

Am I right?

[Spike]

NQ clients already echo the time from the server.
However, if you do use that directly (you could), your client will not be able to generate new input frames when old ones are lost. So yeah, extrapolate the server's time in some smooth way and you can keep generating them. But remember that the existing time value in the client's packets are used serverside to calculate ping, so you will need to extend the protocol.

[Spike]

You can mostly maintain compatibility with mods.
Note that darkplaces already runs client movements out of sequence (as do QW engines).
From my experience, only one mod of all the ones I tried had an issue with it - headhunters (one of the extra weapons depends upon newmis working or something, tbh its a bug). You can keep it compatible by buffering input packets, but I don't personally see that as really required.

Protocol (certainly demos) will be incompatible, but you can query support before activating it, and then use different clc/svcs.

[Downsider]

Running client movements out of order would reduce the ping of each client to what it actually should be, but is it nessecary? I feel dirty doing that, but I guess I could, although in turn it would complicate things.