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.
Discarding checks instead of collision
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:
- Get the potential collision pairs.
- 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.
- Collide these volumes.
- 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
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.
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.
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.
