Tag Archives: detection

Quadtrees vs. Grid detection

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.

More on Havok, physics and collision

What is the most important aspect of a video game? That’s something that has been debated since the inception of video games, and said question could be applied to its technological, spiritual predecessor which are sports, board games and other sorts of games. Every individual has their own opinion on the matter, and my personal opinion is that the most vital fundamental aspect of any game is interactivity; the point where the player’s choices and the game’s mechanics meet on mutual ground and develop an agreement. All games have rules that allow players certain freedoms and limitations, the player’s enjoyment essentially comes down to what state of mind these boundaries put them in.

Last week we made a very general observation of the Havok physics engine. This relates to my thesis statement as physics are an integral part of a games internal logic; the ability to move your character and do any other action is part of your freedoms, whilst falling in chasms and not penetrating walls makes up your limitations.

Collision detection is important for every game in that regard. Take away any form of collision and every object would fall through the ground with the ground itself, making any form of interaction impossible, unless you’re making a kill screen, this is not a reasonable programming design.

Collision and physics are more often than not a tightly knit pair. This is because at the moment collisions are detected, they are always resolved as part of the engine’s logic in physics and constraint integration.

The purpose of collision in a game engine is to determine whether any of the objects in the game’s world are in contact. In order to properly address this, each logical object is represented by geometric shapes. The collision system of the engine determines whether or not these specific shapes are intersection, which means that the collision detection is system is nothing more than a geometric intersection tester.

Collision systems are more than a true or false question regarding shape intersection. Its purpose is to provide relevant information about each contact. That information can be used to prevent unrealistic visual anomalies on screen. For example, last weekend at game jam, I coded an invisible border at the end of the level to go to the game over screen, an example of collision utilized to convey certain information on screen through the programming interface.

This information is used to prevent on-screen anomalies by moving the interpenetrating objects apart prior to rendering the next frame. They can also provide support for an object, such as an object at rest on the ground thanks to the force of gravity on the geometric shape of the ground acting upon it.

Indeed collisions essentially make up most of the gameplay. Think about it; coming into contact with a health power up, shooting at an object to destroy it, even being on the ground is a form of collision. Collision is the main fundamental aspect of interactivity in games, it supports nearly all of the player functions while fulfilling the main objective of the game, to enforce an experience on players.