# How to optimize collisions

I'm building a 2D MORPG using JavaScript, Node JS and socket.io

To prevent cheating, I have to run all collisions for all players on my server.

I'm currently doing fairly simple square collisions like this:

  for (var i = 1 ; i < collidables.length ; i++) {
if (y < collidables[i].y + collidables[i].z &&
x < collidables[i].x + collidables[i].z &&
x + z > collidables[i].x &&
y + z > collidables[i].y) {
// Handle collision
}
}


When a player collides with a wall I halve their speed and bounce them back.
This is not working optimally, but it's fine for now.

The same logic is used to check bullet collision and possibly collision with monsters in the future.

I'm currently using 3 different loops for the follwing:

1. Player vs Terrain collisions
2. Bullet vs Terrain collisions
3. Bullet vs Monster collisions

Since all of them have slightly different logic.

Should I put them all in the same loop or is using multiple loops fine? I feel like using multiple loops will slow down my server a lot once there will be some more terrain / players / monsters.

I chose square collisions because I think they are a lot faster than any other type of collision checking, and my game will have a LOT of collision checking.

I think I will allow between 50-100 players on a single server, with most likely hundreds of monsters and thousands of bullets flying around.

There will also be a rather big map that has to stay loaded on the server. But since the server doesn't actually have to draw anything this should be fine? Client-side the map is split up into smaller parts and only loads the parts near the player.

My game is working fine for now, but there's no real way to test with 50 players until people actually start playing.

I'm afraid I will find out way too late that my collision checking is taking up way too much server memory and/or cpu.

How can I improve the efficiency of my collision checks?

...

Here's a preview of my game in pre-alpha, it should make my question less abstract.

http://185.115.218.199:3000/

If I need to post any more info / code, please let me know and I will do so!

I'm currently running this game on a very small test-server with 512MB RAM and 1 VCPU (can't find the specifications)
This is scalable to up to 16GB RAM and 8 VCPU's and probably beyond that.

• Load it down with collisions and find out. There's no way we can ascertain this from the outside. – Almo Jul 17 '18 at 14:19
• Do you do any partitioning to test collisions only against nearby objects? Also, your assumption that multiple loops will be slower than doing it all in one is often opposite what we see in practice. As Almo says, no one here can profile your code on your target hardware better than you can, so it will be up to you to tell us if your current setup is not meeting your needs, and if so, to identify where there's a bottleneck we can help you overcome. – DMGregory Jul 18 '18 at 11:07
• Well, I'm not asking to do profiling, I'm asking if there are smarter ways to handle all my collision checking. I'm currently not doing any checking to only check collisions for nearby objects, but I definetely should do that! – Pascal Claes Jul 18 '18 at 11:38
• "How many collisions can my server handle" is a profiling question. I've gone ahead and edited-out that part of your question. Is it safe to assume you've read through previous Q&As here about collision checking efficiency, broadphase passes, etc? – DMGregory Jul 18 '18 at 13:07
• @DMGregory I've read a lot about collision checking, but haven't really figured out how to box them to prevent checking everything against everything. – Pascal Claes Jul 19 '18 at 7:25

## Query only nearby objects

As you already know, you need to check only nearby objects. This means that you need a way to retrieve a list of nearby objects to check.

To do that, you need to divide the map in areas, and each area has a list of objects that are currently there. Then, you can solve collisions within each area※.

※: Areas do not overlap. Yet, there could be collisions between objects from one area to an adjacent one. Two solutions: 1) Add objects to more than one area, 2) check with objects in the current area and adjacent ones.

To keep these lists of objects that are in a area, every time an object moves, you need to remove it, and add it to the new one (or new ones).

On a grid

You can divide the world in grid, and make each cell one of the collision areas.

You can optimize the query of finding a cell from coordinates using a very simple locality-sensitive hash: just truncate the coordinates, concatenate them, and that is the index of the cell.

About your grid, you want to pick a size that would make it rare that an object is in two or more grids. Therefore, you want large cells. However, you do not want your cells to be too large that you get a large list of objects in each grid. There will be an optimal size for your game. Test.

On a tree

You can divide the world in a tree, for example using binary space partitioning (good for labyrinth like zones) or simply working with a recursive grid (that would make an quad tree). The process should give a tree where each leaf is one of the collision areas.

Using the tree, it is trivial to find adjacent nodes, which is what you would do to narrow the list of nodes where an object could have gone.

Note: Beyond this point I will describe more optimizations, however, they are not a good fit for every game. So, do not forget to test.

I will talk to you in terms of relational databases for a moment. Imagine you have a table that has all your objects, and we want to check for collisions, so we query a join of this table with itself, and each result is a potential collision.

However, this gives us sorted pairs. The first thing we want to avoid - which should be obvious - is to check the same collision both ways. We want to check collision regardless of the order in which we receive the objects.

Now, there would be rules to discard collisions (for example, a flying entity does not collide with ground obstacles).

However, we can think in terms of discarding checks... each case, has a check one way, and a check the other way, if we discard both, we discard the collision.

What we do, in practice, is have a loop that goes over each object in the collision area, and then inside another loop that goes over each other object in the collision area that we haven't checked yet.

Imagine we have a large number of objects that do not move. Only a few objects move. It is much more efficient to go over each moving object and check against nearby objects, than going over each stationary object, and check if they collide with a moving object.

That is, we can discard the collision checks that starts with the stationary objects.

## Query objects by their kind

As I was saying above, it is useful to know if an object is stationary. In fact, you want to separate objects that move from those that do not (terrain obstacle, for example). With that, you can also avoid checking if an object has changed from one collision area to another, just because it is stationary.

An optimization you will find in physic engines is to declare an object that has no or negligible speed stationary. You can choose to do the same.

Also, not everything can collide with everything. For example, you may have flying units that do not collide with terrain, or you may not have friendly fire (meaning that bullets from allies do not hit), or whatever. Usually, projectiles will not collide with each other (at least not with projectiles from the same faction).

Separate objects by what they can collide with... then, each collision area will not just have a list of objects, but a dictionary where you can get a list of objects of each given kind.

Dumb objects

While classifying objects as described above can separate objects that move from those that do not. We are also interested in objects that follow a simple predictable motion.

For example, your projectiles. Unless you have seeking projectiles that pursue their target, can bounce or something like that, I bet your projectiles follow a line with a fixed starting position and a velocity. Perhaps with a maximum travel distance.

Note: For large maps, you want a maximum travel distance for projectiles. It helps reducing the number of moving objects. In real life, a projectile that has traveled for a long time will just fall to the ground, and it will help with the optimization I describe below.

As you know, you need to put them in a collision area... do it in advance. Add to your collision area a dictionary (ideally a circular buffer) of dumb objects, and the key to the dictionary will be time. Now, you can add your projectile to all the areas it would pass ahead of time... and when you query for objects in your collision area, you take the list of dumb objects that correspond to the current time.

Eventually, the projectile will collide, and then you remove it. In addition, of course, you want to remove lists of dumb objects that are too old.

As Philipp was explaining spatial data structures speed up collision checks, they slow down updates. What I describe here will speed updates back up but will slow down creation and destruction. As always, it is tradeoffs. However, going from something you do for every object each update cycle to something you do for every object once is very good on my book.

## Systematic Collision Detection

There are two approaches for collision detection (and physics in general): Discrete and continuous. You seem to be doing Discrete, which is also simpler to understand, so let us start there...

Discrete physics simulation

You update the positions and velocities of each object (depending on their kind) each update cycle. Thus, each update cycle the objects will have a new position. Then we check at that position if there is a collision.

The problem with discrete physics is that it can allow tunneling. A naive solution is to increase the update frequency. A more advance solution is to find potential collisions pairs first, and then consider the movement of these pairs at more fine time steps.

To find our potential collision pairs - aside from looking only within our current collision area and considering objects by their kind - we can consider for each object a rectangle that covers the initial and final position of the object, then, collide these rectangles.

Continuous physics simulation

Instead of considering the objects at a finite amount of time steps, we will consider their trajectory.

That means:

1. Get the potential collision pairs.
2. Create a collision volume that takes into account the time between updates and the object speed. This is a bounding box of the positions of object.
3. Collide these volumes.
4. Figure out the collision moment, and decide if they did or if they just missed each other.

If you need it, you can also extract the contact points for physics simulation.

There are multiple approaches to do do this, thus, I will not go into detail. What matters for performance is to organize the code in such way that you can discard the cases where there was no collision as soon as possible.

Notes

1. There will be an ideal time step for your hardware and load. Too fast and your CPU is busy doing very little, too slow and each update require a lot of work. Test.

2. remember that your client can do (and arguably should be doing) simulation and prediction for their local space at a higher rate than the server does for the whole map.

3. If you work with squares instead of rectangles, your collision detection reduces to a Manhattan distance check. You can describe your objects as a set of squares at different resolution, and this would converge to pixel perfect collision detection. Errata: A "circle" (all the points at the same distance from a point) using Manhattan distance is a square, but one rotated an eighth of a turn (45º). You would need to do this rotation transformation to use straight up Manhattan distance for collision checks.

## Can you trust the players?

You could let a client - selected by the server - simulate an area and then push to the server what happens.

Sacrebleu!

ROBLOX does this, there are articles describing it in more detail. Keep in mind that this is not a solution for a few thousand players, but for hundreds of thousands of players.

You can do something similar, letting the client simulate, however the server still needs to check that received simulation makes sense (all velocities are consistent, nobody did teleport, etc...). Having multiple clients doing this can allow the server to discard updates from cheaters.

This also leads to some physics artifacts due to discrepancies in timing with the clients, in particular when an object passes from being simulated by a client to another or to the server. I would suggest to use the moment of collision to change the ownership of objects to hide the artifacts (that is, do not change ownership midair).

## Other optimizations

Since you know the direction of movement of an object, you may check only objects on that direction. If you are checking adjacent collision areas, you can decide which to check by this.

Moreover, if you can organize the list of objects in each collision area by one axis, the speed of the object can allow you to discard checks with objects based on their position on the list. However, this is just discarding check, but not discarding collisions, since there could be collision between objects moving in the same general direction.

You can actually go beyond, and build a tree inside each collision area. That would result in a hybrid solution between using grid and a tree.

When picking your data structures, you may want to choose cache aware ones. In particular, many tree data structures are not cache aware. You want the memory of nearby objects to be nearby, so that it can stay in cache while checking collisions, minimizing trips to RAM.

It can also be useful to set a maximum speed you will see in the game. Many fast collision detection solution have problem with fast moving objects... well, do not have fast moving objects.

Using that maximum speed, you can ensure that an object will not completely skip a collision area in one update cycle (or, conversely, decide how deep you have to do into adjacent collision to check). It is also useful to decide if an object is close enough to an adjacent area to add it there (or check collision there).

Is the server having too much trouble with collisions? Slow down time (thank EVE online for the idea). I do not mean to reduce the frequency of the update cycle, but to reduce speeds. A very simple implementation is to clamp the time between updates, so you do not mess with your speeds, but you make time actually pass slower. Less time per update cycle means less collision per update cycle.

The interesting part about the approach that EVE online took for this is to apply it in different areas proportionally to how dense they are. Meaning that players that are on part that currently have very little action are not affected.

Consider using parallelism to check for collisions. This would be hard to implement on node.js, as it does not really have threads... however, you can have multiple processes on the same server. You will find that collision detection has a lot of opportunity for parallelism. You can run different collision areas in parallel, you have collision detection for different pairs of objects happening in parallel, or even there are chances for parallelism in the checks for a single pair of objects.

Finally, another thing that would be hard to implement (but not impossible) with node.js is GPU-Assisted Collision Detection. If everything else fails, research this.

My game is working fine for now, but there's no real way to test with 50 players until people actually start playing.

There is. Just write a bot client for stress-testing your gameserver. While it is hard to write a convincing bot which behaves exactly like a real player would behave, it is usually not that difficult to write one which just logs in, joins a game and performs some simple automated actions to generate some server load. The bot should be simple and lightweight, so you can easily run a lot of instances of it (i.e. no graphic output). Run 50 instances of your bot on your local workstation and have them connect to the server.

By the way, you might notice that such a bot can be used to automate a lot of other tedious testing tasks. You could even go so far and implement a whole automatic integration test suit by having some bots play preprogrammed matches and check automatically if it still turns out the way it is supposed to.

Checking every object in the game against every other object in the game is an algorithm with a time complexity of O(n²). That means the execution time raises quadratically with the number of objects in the game. When you notice that the amount of collision checks creates notable performance degradation, look into ways to reduce the number of objects you need to compare every object with.

One useful method is to divide the game map into sections, keep track of which section contains which objects and only check collisions between objects in the same or in neighboring sections.

Another is to store all your game objects in a spacial tree like an octree or 3-d tree which allows you to quickly iterate all objects in a given area.

But keep in mind that while spacial datastructures speed up collision checks, they slow down movement because you need to update these structures whenever something moved. That means they work best for objects which move rarely or never. A section-based approach (sometimes referred to as "spatial hashing") does not have that much overhead for moving objects, because all you need to do when an object moves from one section into another is remove it from the old section and add it to the new one. So you could also try a hybrid approach. Use trees for checking collisions between game objects and walls and use sections for checking collisions between game objects and other game objects.

There are different ways to deal with collision, but we should always prioritize efficiency. A brute force algorithm such as the one you’ve implemented runs n^2 times, or at O(n^2), which is expensive and will greatly decrease your speed the more objects you have to compare.

As already mentioned, you want to compare only objects that are close enough to where collision is even possible. To achieve this, you should use Quad-trees for 2D games or Oct-trees for 3D games.

Think of your scene as a graph with four quadrants, starting with the top-right quadrant going counter-clockwise, labeling 0-3 respectively. Each quadrant can have a maximum number of objects (x) and level number (n). When a quadrant contains the maximum number of objects, this is where the level number will come into use because the quadrant will be split into another four quadrants and the same rules will apply for those as well. The new quadrant will be assigned level number n+1.

Using this recursive algorithm to assign an index (quadrant) and level number to each object, you will have a significantly less amount of checks by returning the list of objects that are in the same quadrant and objects that may overlap boundaries. This runs at O(nlog(n)). So much better. Same applies to OctTrees with eight quadrants.