Quadtree vs Spatial Hashing Collision Checking

Because I need to check collisions on the serverside to prevent wallhacking/warping into walls in my game, I was looking into ways to do that as quickly as possible so that there isn’t a long delay from the server processing collisions between the player and every collidable tile. I knew about quadtree collision checking algorithms, which is what I’m using on the clientside, but I didn’t know about spatial hashing, so I thought you guys might be interested in this article with a visualization.

http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

Apparently spatial hashing is much more performant on uniform objects, but I don’t know if that applies to my case because the player is not a uniform object compared to the tiles, but the tiles are all uniform objects compared to each other. So I’m not sure if that means quadtrees or spatial hashing is better in my case, because only one object is not uniform, however that’s the one that is having collision checks run against it every time. I’ll have to look further into it and ask around online or write a benchmark test for myself using implementations of both algorithms.

If by uniform, you mean size… as written in your link. What is keeping you from making your player multiple squares of the lowest denominator?

like 16x16 tiles checked against 32x52. (or the opposite, wtv)

Player would be 2 objects large and 4 in height, the 4th overlapping the 3rd.
That’d be 8 objects to check by player though… I don’t know how much more efficient spatial hashing is, just throwing an idea.

That’s an interesting idea, I didn’t really think of that.

Though I don’t know if I want to do that because I would have to change the way collisions are set up on the clientside (A different collision box for the head, body, and the collision box extended dynamically based on the length of the weapon you’re using) and make each one a collection of 16x16 collision boxes which would not only add a layer of complexity on both sides that might give me a headache to implement, and make the collision boxes more inaccurate because it would have to be in multiples of 16.

Spatial hashing is much more efficient at least in that guy’s use-case, but either way I’ll have to test it myself to see which one works out better for my scenario. For now I might just stick to quadtrees because this isn’t a super high priority for me right now and quadtrees are much easier to implement because it’s a common and popular method with many examples, and just look into it again in the future when I want to start optimizing the game more.