Me and my groupmates are making a fighting game by the name of Shattered Tides, like any game we’re implementing collision detection code. There are many ways to implement it, however the real challenge is finding the most effect in the best possible time given our anemic time frame. After looking into it, it would seem that the quadtrees are the most common way to go but in some resources they mention the grid based solution.
So which is better and more effective? The right answer depends a little bit on the actual game you’re making, and choosing one over the other is needs implementing both and doing profiling to find out which one is more time or space efficient on your specific game.
Grid detection seems to solely apply to detecting collisions between moving objects and a static background. The greatest advantage is that the static background is represented as a contiguous memory array, and each collision lookup has the Big O of O(1) with good locality if you have to do multiple reads because entities need to be covered more than one cell in the grid. The disadvantage however is if the static background is large, is that the grid can be rather wasteful of space.
If instead you represent the static background as a quadtree, then the cost of individual lookups goes up, but because large blocks of the background take up small amounts of space, the memory requirements decrease, and so more of the background can sit in the cache. Even if it takes 10 times as many reads to do a lookup in such a structure, if it’s all in the cache, it’s still faster than a single lookup with a cache miss.
Personally I’d go with the grid implementation, because it’s easier to do and would be more productive for me to study. If I notice that our game is running slow, we’ll do some profiling and see what could use some help. If it looks like the game is spending a lot of time doing collision detection, we’d try quadtree and see if that’s any better.
bassemtodary 