[Open thread]Multiplayer discussion


#1

Hello all

In preparation to … something … can’t say yet what it’s going to be, I’ve spent quite a bit of time thinking about how to implement multiplayer games in a smart way.

Especially technologies of how to do things and how to handle communication between devices.

In particular, I have been looking at old examples of networking (null modem cable) because in those days machine power was very limited and information had to be very tight.

Today I looked at Sopwith , a duelling biplanes game and one of the earliest dos network peer-to-peer games ever published

image

What I found was very interesting indeed. The way Sopwith implements 2 player is as follows:

  1. The master sends the random seed key to the slave
  2. Both machines use the same seed
  3. In both machines, object #0 is the player, object #1 is the other player
  4. your own plane is controlled by your keypresses that are mirrored to the network
  5. remote player is controlled by a function that reads keys from the network
  6. because BOTH machines are using the same random steps and mirroring keypresses, NEITHER is the “authoritative master” but are running the state machine independently of each other

… allowing for a complex game with loads of objects to be played across network with very, very little traffic. Genius!

If you have ideas about multiplayer, continue the thread!


#2

Very nice, but it must be perfectly synchronized. It has to be ensured the received action is executed at the same frame as on the other computer, right? Actually, does this mean the computer has to wait to receive the action over network before computing the next frame? That would be a big no no today, and very unusable with even small latency or network errors. In theory you could run an extra delayed world for the other player, but that sounds complicated and twice as much stuff to compute.


#3

Yes, its a blocking call


#4

I think in Pokitto though, it would be some sort of serial connection similar to how an old Gameboy link cable would have worked. It wouldn’t really be a ‘modern’ network.

Also, I used to love that game back in school. It was quite old by then even. (were talking early 90’s.)


#5

@drummyfish : if you have/know other lightweight multiplayer schemes suggestions are very welcome!


#6

You’re right this could still work on Pokitto.

So maybe a library for this would be nice. There would be a class from which the input would be retrieved, and the class would hide whether it is the local or remote player. Could also work for AI, game replays (ghosts in racing games) and so on. I’m sure this is some game design pattern.

I haven’t done much multiplayer :confused: But looks very interesting, I’ll take a look at it.

EDIT:

Indeed I’ve found a lot of info about the peer-to-peer model at the Wiki, here and here (nice in depth analysis of Age of Empires multiplayer system that worked like this, with all the added cleverness they invented). Apparently nowadays it’s still being used for games with few players and many objects, typically RTS games. Also they mentioned Doom used this model and played decently over LAN (not so over the Internet), so it will definitely be good enough for our needs.


#7

I like the idea of generating a world from a seed and having all clients use the same seed.

I can’t think offhand of anything clever to do at the low level, but from an architectural/design point of view I know some good ways of designing a game to be suited to both network and local play.

Firstly there’s the command pattern.

(I think this is the pattern @drummyfish was thinking of.)

(Anyone who hasn’t read Bob Nystrom’s Game Programming Patterns cover to cover yet should do so immediately.)

Which in practice would look something like this:

class Entity
{
public:
	const Point & getPosition(void) const;
	const Vector & getVelocity(void) const;
	
	void move(Vector force);
};

class Command
{
public:
	virtual void execute(Entity & entity) = 0;
};

class MoveCommand : public Command
{
private:
	Vector motion;

public:
	MoveCommand(Vector motion)
		: motion(motion)
	{
	}

	void execute(Entity & entity) override
	{
		entity.move(this->motion);
	}
};

class CommandSource
{
public:
	virtual bool hasPendingCommands(void) = 0;
	virtual std::unique_ptr<Command> getNextCommand(void) = 0;
};

class GamepadCommandSource : public CommandSource
{
public:
	// Generates commands based on button input
};

class NetworkCommandSource : public CommandSource
{
public:
	// Receives commands over a network stream
};

Alternatively there’s the EntityController pattern (which I explained to @sbmrgd a while back):

class Entity
{
public:
	const Point & getPosition(void) const;
	const Vector & getVelocity(void) const;	
};

class EntityController
{
public:
	virtual void updateEntity(Entity & entity);
};

class GamepadEntityController : public EntityController
{
public:
	// Controls an entity based on input from a gamepad
};

class NetworkEntityController : public EntityController
{
public:
	// Controls an entity based on messages passed over a network stream
};

#8

What I meant is what you named CommandSource – I imagine creating this class is a very common practice in games, but still can’t find the name for the pattern. Could it be something like C++ stream, if that can be called a pattern? It streams you actions/events and you can switch the stream source.


#9

I think it’s something more fundamental than a pattern - an object that generates objects/data.

A ‘stream’ isn’t a C++-specific concept, C# and Java have their own concepts of streams.
A ‘stream’ is simply a flow of data, either bidirectional or unidirectional (and arguably a bidirectional stream is actually just two unidirectional streams pointing in different directions).

The idea of having interchangable implementations of a stream is the Liskov substitution principle.
(I.e. that’s the principle that allows you to ‘switch the stream source’.)

The idea of depending on an abstract stream interface class is the dependency inversion principle.
(I.e. this is the principle that involves designing code based on abstract interfaces rather than concrete implementations.)

(Overall I’m not a fan of the SOLID principles because I consider some of the principles to be substantially more useful than others, and some are too poorly defined to be useful.)


#10

Sure, all this is true, it’s using fundamental design principles and so on. I just think this particular situation and the solution keeps reappearing very often, hence it’s a pattern, and very likely has a short name that makes it easier to reference in speech. Nevermind, let’s not derail this thread too much. If I happen to find a satisfying answer somewhere, I’ll share it.

Summary

EDIT:

Event queue is a named pattern that comes close in a sense that it decouples the source of the events, but in a different way (the queue is one intermediate global object as opposed to multiple event sources).

It’s similar to, or a subset of bridge, but that’s still too general.

Data Bus?


#11

I think you’re thinking of something slightly different.

The idea of forming a list of objects and accessing/extracting them one-by-one is a common concept across all languages, but different languages tackle the problem in strikingly different ways.

Depending on the language the idea can be called ‘iterators’, ‘enumerators’, ‘cons lists’, ‘generators’ etc.
Fundamentally they’re all different implementations of the same idea, but there’s no single word for that idea.

Boring stuff for crazy people

C#'s IEnumerator<T>:

interface IEnumerator<T>
{
	T Current { get; }
	bool MoveNext();
	void Reset();
}

Java’s Iterator<E>:

interface Iterator<E>
{
	boolean hasNext();
	E next();
	default void remove();
	default void forEachRemaining(Consumer<? super E> action);
}

C++'s concept of an InputIterator:

Definitions:

  • The type I is an implementation of an input iterator.
  • The objects i and j are instances of I.

Rules:

  • The expression i != j returns an object that is explicitly convertible to bool
  • The expression *i returns an object of type I::reference, which is implicitly convertible to I::value_type
  • The expression i->m is equivalent to (*i).m
  • The statement ++i returns an object of type I&
  • The statement (void)i++ is equivalent to (void)++i
  • The expression *i++ returns a value that is convertible to I::value_type, and is equivalent to I::value_type x = *o; ++i; return x;

(The reason this is defined as a set of rules rather than an actual class is because defining it in terms of rules is more flexible and avoids the memory/performace overhead of inheritance.)

Haskell’s [] (pronounced ‘list’):

data [] a = [] | [a]

Which probably doesn’t make much sense unless I also define:

head :: [a] -> a
head [] = error "Cannot remove from empty list"
head [x] = x

null :: [a] -> Bool
null [] = True
null [x] = False

D’s InputRange(E):

interface InputRange(E)
{
	bool empty();
	E front();
	void popFront();
	E moveFront();
	// also opApply, but I've left that out because I don't have time to understand the syntax
}

(This is that scary moment where I suddenly realise how many languages I’ve dabbled in.)
(I remember Lua also has a similar concept but I can’t remember how it works. Look up Lua’s pairs and ipairs and there will probably be something about it.)

Edit

Aparently Wikipedia classes it as an ‘iterator’, and ignores language-specific nuances.
It also makes the link with generators and streams.

Interestingly the first language to use iterators was the 1974 language CLU,
which coincidentally was designed in part by Barbara Liskov,
and ironically didn’t feature inheritance.


#12

So let’s get back to multiplayer – while researching design patterns at WikiWikiWeb I found a page about multiplayer that speaks about games such as Doom. One comment suggests dead reckoning (quantity prediction) algorithms to deal with the problem of peer synchronization (frames having to wait for inputs from network). That’s the idea I’ve mentioned above. Since then it has crystallized into this:

  • Have a shared world whose state is the same at each computer. This world is advanced by frames that are delayed and possibly tearing by the blocking network waiting. But that is OK, because this world is not directly presented to the player.
  • Additionally, have a local world at each computer. This world is derived from the last state of the shared world. In this world, the local player’s actions are immediately taken into account and the actions of the remote players are extrapolated/predicted. The local world is being updated as the shared world is waiting on network. Therefore this world is smooth, undelayed for the local player and so it is the one presented to the player.

Even if the “simple to implement” case with just the shared world worked on Pokitto, I would seriously consider using the described method in order to be able to decrease the transmit/processing rate and possibly purposefully increase the delay along with buffers in order to relieve the processor and leave more juice for rendering etc.

This seem like a quite nice solution, doesn’t it? Again, it could be built into a nice and tidy library that would hide this from the programmer. I imagine you’d simply declare a bunch of variables (= world) that you’d want to have synchronized over the network and the library would take care of the rest.


#13

Thats blockchain!


#14

If the world isn’t presented to the player then the ‘frames’ aren’t being rendered, so there’s no tearing as such.
(I’d say ‘ticks’ or ‘updates’ rather than frames, because frames implies graphics and/or rendering.)

And if anyone finds that hideously dull, there’s the slightly less dull and slightly more to-the-point Client-side prediction.

There’s a decent-ish ~5 part article about client-side prediction (and ‘server reconciliation’) here.

There’s another example here but it’s slightly harder to understand.

I’ve attempted to C++-ify the pseudocode, but I had to guess a lot of it because it wasn’t obvious from the context what’s global and what’s local, let alone what the types are supposed to be.

// Called when we receive a player state update from the server. 
void onServerFrame(ServerState serverFrame)
{
    // Remove frames from history until it's duration is equal to the latency.
    double deltaTime = std::max(0, (historyDuration - latency));
    historyDuration -= deltaTime;
    while((history.Count > 0) && (deltaTime > 0))
    {
        if(deltaTime >= history.front.deltaTime)
        {
            deltaTime -= history.front.deltaTime;
            history.pop_front();
        }
        else
        {
            const double time = (1 - (deltaTime / history.front.deltaTime));
            history.front.DeltaTime -= deltaTime;
            history.front.DeltaPosition *= time;
            history.front.DeltaRotation *= time;
            break;
        }
    }

    ServerState serverState = serverFrame;

    // If predicted and server velocity difference exceeds the tolerance,
    // replay inputs. This is only needed if the
    // velocity for one frame depends on the velocity of the previous
    // frame. Depending on your game you may also need
    // to do this for angular velocity or other variables.
    if(distance(serverState.velocity, history.front.velocity) > velocityTolerance)
    {
        predictedState = serverState;
        for(auto & frame : history)
        {
            ServerState newState = playerController.update(predictedState, frame.deltaTime, frame.input);
            frame.deltaPosition = (newState.position - predictedState.position);
            frame.deltaRotation = (newState.rotation - predictedState.rotation);
            frame.velocity = newState.velocity;
            predictedState = newState;
        }
    }
    else
    {
        // Add deltas from history to server state to get predicted state.
        predictedState.position = serverState.position;
        predictedState.rotation = serverState.rotation;
        for(auto & frame : history)
        {
            predictedState.position += history.deltaPosition;
            predictedState.rotation += history.deltaRotation;
        }
    }
}

// Called every client frame.
void update(double deltaTime, Input input)
{
    // Run player controller to get new prediction and add to history
    ServerState newState = playerController.update(predictedState, deltaTime, input);
    Frame frame = Frame(deltaTime, input);
    frame.deltaPosition = (newState.position - predictedState.position);
    frame.deltaRotation = (newState.rotation - predictedState.rotation);
    frame.velocity = newState.velocity;
    history.push_back(frame);
    historyDuration += deltaTime;

    // Extrapolate predicted position
    // CONVERGE_MULTIPLIER is a constant. Lower values make the client converge with the server more aggressively.
    // We chose 0.05.
    auto rotationalVelocity = (newState.Rotation - predictedState.Rotation) / deltaTime;
    auto extrapolatedPosition = predictedState.Position + (newState.Velocity * latency * CONVERGE_MULTIPLIER);
    auto extrapolatedRotation = predictedState.Rotation + (rotationalVelocity * latency * CONVERGE_MULTIPLIER);

    // Interpolate client position towards extrapolated position
    double t = deltaTime / (latency * (1 + CONVERGE_MULTIPLIER));
    clientState.Position = (extrapolatedPosition - clientState.Position) * t;
    clientState.Rotation = (extrapolatedRotation - clientState.Rotation) * t;

    predictedState = newState;
}

I tried to verify the claim about DOOM,
but the source code is hideous so I gave up looking.


#15

I’ve seen articles refer to the iterations as frames, ticks I’ve seen used mostly with physics. Updates seems like the most reasonable option.


Indeed in an article I linked to previously, I’ve now found the same solution:

The solution is to keep a circular buffer of past character state and input for the local player on the client, then when the client receives a correction from the server, it first discards any buffered state older than the corrected state from the server, and replays the state starting from the corrected state back to the present “predicted” time on the client using player inputs stored in the circular buffer. In effect the client invisibly “rewinds and replays” the last n frames of local player character movement while holding the rest of the world fixed.

This way the player appears to control their own character without any latency, and provided that the client and server character simulation code is reasonable, giving roughly exactly the same result for the same inputs on the client and server, it is rarely corrected.


Nice, that’s something to start with!

This is all using linear prediction though – that’s mostly what we’ll want, but I’d suggest to have an option to specify the type of prediction/extrapolation for each variable in the potential library. For some types of movement (say planes that quickly fly around the screen in circular motion) the user may want a better curve predicted from more than two previous values… and also this can go the other way around – for example for objects moving very slowly you may want to disable even the linear prediction to save some divisions.


#16

I’d class that as incorrect unless it was happening at the same time and at the same speed as a frame being rendered.

Sometimes people forget that a frame is actually the thing drawn to the display because they get used to the idea of trying to lock their game logic to the same speed as the framerate.

That’s unsurprising, it’s common to class physics/logic updates as ‘ticks’ when working in a game where physics/logic might update at a different frequency to rendering.

For example, Minecraft classes redstone updates as ‘redstone ticks’.

When it comes to writing the circular buffer, I could probably make a good templated one comparable to a stdlib container.

In terms of flexibility, extrapolation is a minor issue compared to the fact that different games will have different data structures, unless you’re expecting all games to use the same physics library.

Allowing different extrapolation methods is trivial, you either template the function in a way that permits lambdas to be used or accept the extrapolation function as a function pointer.
(The former permits inlining of the lambda in certain cirumstances.)


#17

I was wondering that if we use prediction, suppose that objects will go along certain trajectory, there will be hiccups when we synchronise worlds. E.g. Some object might have crashed with another object in the local, predicted world, but in reality the other player might have avoided the crash.

But anyway it might be better that just waiting for the response and halt everything during that time.


#18

Yep, there’s no ultimate solution, AAA MMORPGs suffer from this too. However, as I mentioned above, it can be at least suppressed:

  • You can have different kinds of curves – the most typical is linear – but it can be some spline or something.
  • You can use approximation curves instead of interpolation curves – This will prevent non-continuous movement (doesn’t only have to be movement of course).

EDIT:

The smart curve could work like this: you make linear prediction of the value (e.g. position) from the two last known values and then you keep going in the direction given by current value and the last received previous value and keep “changing direction/steering” a little towards the predicted value. This way the value will never “change suddenly/jump” – only the predicted target will. Probably makes no sense, I’d better draw a picture.

EDIT 2:

I mean like this:

image

The disadvantage is that the curve doesn’t necessarily hit the points exactly and can diverge quite a lot – in this case we can simply abandon this approach and teleport the player once, tough luck. Parameters like the maximum divergence distance could be specified in the library.


#19

If someone was to make a multiplayer chess/checkers/card game, I’d expect the networking code to be completely different from a racing game or an FPS.

For turn-based games or maybe Pokemon/Tamagotchi, you don’t need much more than:

  • some way to find others (broadcast packets?), start and close a connection
  • bool isConnected()
  • bool send( const void *data, uint32_t size )
  • bool recv( void *data, uint32_t size )

Racing/FPS can build on those 3 functions with a layer of interpolation algorithms.

RPG games could use an AI-based approach where characters walk to their correct position (using A*?) instead of interpolating.


#20

Ah, glorious rubber banding.
Hilariously this is still present even in modern games.

100% agree with this.
This is why I said:

In terms of flexibility, extrapolation is a minor issue compared to the fact that different games will have different data structures, unless you’re expecting all games to use the same physics library.

A chess game would be able to just push chess notation over the network.

I’d probably try to implement something along the lines of std::future.

Then you could have something like:

template<typename T>
future<T> receive(void);

template<typename T>
future<bool> send(std::shared_ptr<T> object);

Which can then be used like:

// ...
auto future = receive<DataPacket>();
// ...
switch(future.wait_for(50_milliseconds))
{
	case future_status::ready:
		// Handle data
	case future_status::timeout:
		// Handle other work
	case future_status::deferred:
		// Some kind of error?
}
// ...

Also void * should usually avoided or wrapped in a template,
and size should always be measured with std::size_t.

E.g.

bool isConnected(void);
bool send(const void * data, std::size_t size);
bool receive(void * data, std::size_t size);

template<typename T>
bool send(const T & object)
{
	return send(&object, sizeof(T));
}

template<typename T>
bool receive(T & object)
{
	return receive(&object, sizeof(T));
}