Hey,

I'm currently working on a school assignment which is in short explained in a thread I started here:

http://www.gamedev.net/topic/676440-multiplayer-network-design/

But to recap, it's a simple top-down game. Four players each control a "ship" and they're divided into two teams and each one spawns in a separate corner. There is a ball as well which both teams should try to push into the screen edge of the opposing team spawn thus scoring. It's "physics based" meaning collisions causes bounces and accelerations e.t.c. - Very simple game.

However, the school assignment is to convert this four player local game into an online multiplayer game. So I have the game, physics already written and it's working locally but I need to implement online multiplayer. It's written in java, no network libraries e.t.c. are allowed. Main parts of the assignment is to:

1. Fight lag

2. Fight cheating

So far I have a server which sends a full world snapshot at a given rate. Since the world is very small and I am under a bit of time constriction I'm not going to bother with delta-snapshots but instead just keep sending the whole world.

The clients at the moment send their input every frame, that is, which buttons they're pressing at the given frame. I know this isn't optimal but I need to get things going before I start to optimize. The server reacts to the input once it receives it which in whole just gives clients a delayed input but everything is perfectly synched.

However, now that I've got that working I'm trying to implement client prediction but it's not working very well at all. The client side prediction at the moment is as follows:

1. Client stores input for each frame and sends the input along with the frame number.

2. When client receives a world update from server, it sets the clients m_frame variable to what the update says (provided that it's the most recent update, otherwise client ignores it.)

Client then checks the turnaround time to the server and updates local world (latency / time_per_frame) times and also increments the m_frame variable for each update. For every update, the client also checks the input buffer mentioned in step 1 and replays the input for each frame being predicted.

3. At this point I'm thinking that the client should be processing ahead in time. So if the client now sends, let's say input for frame 1000 and the server is currently at 960 the input should arrive in time for the server to process frame 1000.

Now my problem is that the local players is jittering, a whole lot. When I'm testing I'm running it all locally but with a simulated latency. So packet loss shouldn't be an issue at this point. Maybe this is wrong, but if there is only a single player connected, there should be no visible artifacts at all, no matter how much latency? Since the server is only playing back the input given by the player on a deterministic game.

Any suggestions on how to proceed from here?

I can do a quick pseudo-code :

It's basically a dumb down version of the standard host-authoritative client prediction.

struct Vector
{
    float x, y;
};

struct Inputs
{
    int mouse_vx;
    int mouse_vy;
    int mouse_buttons;
};

struct Player
{
    Vector pos;
    Vector vel;

    void update(Inputs inputs)
    {
        // .....
        // ....
        // ... 
        // ..
    }
};

// inputs for each frame.
struct InputsPacket
{
    Inputs inputs;
    int    frameId;
};

// player updates on server.
struct SnapshotPacket
{
    Player player;
    int    frameId;
};

struct Client
{
    // list of inputs since last server update.
    std::list<InputsPacket> inputsQueue;
    
    // predicted player position on client.
    Player player;

    // the current frame id.
    int frameId;

    // initialise to a player position.
    void reset(Player _player, int _frameId)
    {
        inputsQueue.clear();
        
        player = _player;
        
        frameId = _frameId;
    }

    // update for frame.
    void update(Inputs inputs)
    {
        // increment frame id.
        frameId++;

        // create input packet.
        InputsPacket inputPacket(inputs, frameId);

        // cache input packet.
        inputsQueue.push_front(inputPacket);

        // update player.
        player.update(inputs);
        
        // send latest input packet.
        sendToServer(inputPacket);
    }

    // remove inputs from frame id, down to the oldest. 
    bool acknowledgeFrameId(int frameId)
    {
        // iterate inputs frames that haven't been acknowledged yet.
        for(std::list<InputsPacket>::iterator it = inputsQueue.begin(); it != inputsQueue.end(); ++it)
        {
            // found matching inputs frame.
            if(it->frameId == frameId)
            {
                // erase older inputs. We won't need them anymore.
                inputsQueue.erase(it, inputsQueue.end());
                return true;
            }
        }

        // couldn't find the inputs for that frame. 
        return false;
    }

    // host send us a player update for that frame id.
    void receiveFromServer(SnapshotPacket snapshotPacket)
    {
        // remove inputs up to the frame id.
        if(acknowledgeFrameId(snapshotPacket.frameId) == false)
        {
            // frame id is invalid. don't do anything.
            return;
        }

        // rewind player to the server frame id.
        player = snapshotPacket.player;

        // replay inputs that haven't been acknowledged, from oldest to newest.
        for(std::list<InputsPacket>::reverse_iterator it = inputsQueue.rbegin(); it != inputsQueue.rend(); ++it)
        {
            // update player.
            player.update(it->inputs);
        }
    }
}

1. Client stores input for each frame and sends the input along with the frame number.

2. When client receives a world update from server, it sets the clients m_frame variable to what the update says (provided that it's the most recent update, otherwise client ignores it.)
3. Client rewinds the player position to what the update says. Removes old frame from the cache, since we won't need them anymore.
4. replay all inputs from after the server frame id, up to the latest.



And that's about it, basically. No messing about with latency and whatnot. It's all taken care of automatically, you'll just have more frames to replay when the latency increases. At least, I don't think you have to do anything.

The rest of the standard client-side predictions are just optimisations, not really affecting the general algorithm.

EDIT : BTW, if your transport is limited to UDP (aka not reliable), instead of sending a single inputs packet per update from the client, send the entire inputsQueue, which is in effect the list of inputs that haven't been acknowledged by the server. Or just ignore packet loss all together send single frames, or a couple of frames at a time.

EDIT 2: bugs!

Does the client (predicted) frame change smoothly and monotonically?

So when it predicts forward from the server provided state (latency / time_per_frame) times, the value is guaranteed to be higher than equal to what it was last frame, and theres no fluctuations in either latency / frame time (or you apply a smoothing function somewhere). I assume the server applies the client input at exact same frames as client does, and for exact same length of time.

Does the client (predicted) frame change smoothly and monotonically?

So when it predicts forward from the server provided state (latency / time_per_frame) times

Frame rate should always be decoupled from simulation rate.

Without it an enormous list of problems appear. Tunneling, skiing, and wall-climbing are a few of the highly visible items on that list of problems.