Code for this is at https://github.com/ertyseidel/collisions

Motivation

In a multiplayer game, it is useful to be able to do collision detection on the server, to ensure that your players aren’t cheating or moving incorrectly. When we take latency into account, and the other myriad problems that can come about when we deal with packets, this problem suddenly becomes very difficult.

Say we have three players (p1, p2, p3) and they each have a client that sends packets containing location data to the server. To keep things simple, we’ll say that these packets contain the player’s coordinates (x, y). So, mapping these players at t=0, we get:

The server knows these positions, so we can assume that we have a fully updated representation. Then time begins to pass, and the players start to send updates with their new locations. At t = 10, let’s say we receive a packet from player 1. Thus we are in the following state:

Player 1 has moved, but players 2 and 3 haven’t received any updates from their clients! If we have a collision here, there’s no way to check yet. There’s no guarantee that player 2 isn’t colliding with player 1 right now according to player 2. Let’s run a few more frames:

Can you spot the collision? Answer: Right in the center, where 1 and 3 cross, at time 18 or so (assuming each snapshot took 10 time).

Algorithm

So obviously we need some sort of interpolation and time-checking for this! Let’s look at how the main update function works.

The first thing we need to do is figure out what “step” we’re on. We do this by setting a stepSize, something like 25; this is the “bucket size” for each time step on the server.

E.g., with a step size of 25, all the packets received between time 100 and time 124 inclusive will be in the time = 100 bucket.

Let’s get some packets! We start out with knowledge of all our players positions at time 0 (It’s actually more complex than that and handles players entering/leaving, but for now let’s say we know where everyone is at t=0).

Then we get a packet from player 1 at t= 56:

But let’s say the next time we get a packet is at time 105, from player 1:

The next thing we do is interpolate player 1’s position for the missing row, t=25. We do this by linearly interpolating between P1’s x and y values, given the time between the updates (green values are interpolated):

Now let’s get a packet from P2 and P3 in the T=100 bucket. Then we do collision detection on P2 and P3 at t=100, since there is more than one data point at that timestamp.

And interpolate the values of P2 and P3 back to t=0:

Right here, we perform collision detection between P2 and P3 at t=75, and between all three players at t=50 and t=25. Essentially, whenever we add data to a row, we do collision detection against the other existing data in that row. This means that we don’t have  to wait until all of the data for a row are in before we try collision detection across them. It also means we can detect collisions in the past, and the game can retroactively decide to act on that collision, or not.

There’s one last step at this point – we remove the rows at t=0 and t=25 since we’ve already collision checked all of the players at these points, and t=50 is the data from which every player will interpolate from this point forward. Thus our table ends up looking like:

until we receive more data from the users.

There are functions dealing with adding and removing users, but you’ll have to explore the code to see that.

Todo

Setting a step-size that is much smaller (I use t=5ms) allows us to do very fast server-side collision checking. This is nice, since we don’t have to do collision detection AND rendering on any given computer.

The main problem facing this is that we currently only do collision detection against other players  – I have no idea how it will fare with more complex objects or things that don’t move.

I’d love to see if this library works for other people writing javascript multiplayer games, and since this is alpha-level development, forks and pull-requests are greatly appreciated!

From Manhattan,

–Erty