Has anyone have experience implementing collision detection on server side? I am writing a top down 2D multiplayer game. All the players are constantly moving. I want to implement collision detection on the server side so at any time the server will know which player collide with which player and broadcast the result.

The problem is if I use brutal force collision detection to detect collision of every player the resource consumption on the server will be huge (my game updates 60 times a second). I only have experience detecting collisions on client side where I can use broad-phase collision detection such as spatial partitioning. But I have thought about that on server side the server has to know the state of every player so detecting collisions only in a small area doesnt make much sense. So do I have other more efficient algorithm for collision detection on server side?

Here is how I do this:

  1. I pick a moving sprite from the sprite array
  2. do a spatial hashing for it and get some nearby sprites
  3. based on the above method, I loop through the entire sprite array and pick one by one to get some nearby sprites
  4. I put all the results into a big array and it will store all the sprite for collision detection.

Because I need to send out state information to every moving sprite/entity I have to loop through the entire entity list to do spatial hashing for each one.


I have get answers from gamedev.net forum. What I thought I should be doing was wrong. I don't need to compute all nearby entities for all the entities in one go. All I need to do is loop through the entity list and when I need to send out the nearby bucket list for an entity I do a spatial partitioning for that specific entity. I don't need to do this on every frame. In fact maybe I just need to do it 5 or 10 times per second.

  • \$\begingroup\$ Spatial partitioning still makes sense on the server too. It's generally unlikely that all n of your players will be simultaneously colliding with each other in a giant n^2 pile-up. You'll usually have small, spatially separated clusters of nearby players that you can solve independently by partitioning them into buckets of some variety. The principles of doing this on a server aren't different from doing it on a client. \$\endgroup\$ – DMGregory Apr 9 '17 at 17:10
  • \$\begingroup\$ @DMGregory ok so I just need to modify my algorithm a little bit to make that happen. \$\endgroup\$ – newguy Apr 10 '17 at 0:50
  • \$\begingroup\$ @DMGregory I tried to do a spatial hashing for every player but it ends up putting every moving player into the array for collision detection check, which is literally a n^2 problem.I have tried from as low as 50 sprites up to 500 moving sprites. I am testing it on a small map (640 x 480) though. \$\endgroup\$ – newguy Apr 10 '17 at 11:25
  • \$\begingroup\$ Comments aren't​ the place to describe your problem. If you want help improving a specific collision detection algorithm, use the edit button to put a description of your current strategy into the question itself. Remember, you don't need to have just one giant array for collision checks. You could break your world into a grid of buckets proportional in size to a player's movement speed, then only check for collisions between items in the same bucket or adjacent buckets. \$\endgroup\$ – DMGregory Apr 10 '17 at 12:13
  • \$\begingroup\$ Thanks I have updated my question. The thing is every player is moving on the map don't I need to do a collision check for each one so that I can send out the state to each one? \$\endgroup\$ – newguy Apr 10 '17 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.