Sunday, November 22, 2015

The 2D game that I’m making is like a top-down view of a maze. The player can walk through the maze and shoot monsters. As for the implementation, I started out with a grid. At first, grid cells were either a wall or a floor, and things were incredibly simple. Then I scaled up the size of the grid cells, so that a single grid cell would contain multiple objects; items for the player to pick up and monsters to fight. Using a grid for spatial partitioning is quite alright, but it’s inefficient.

Some concerns I have regarding the use of grids:

• requires storage space regardless of whether the grid cell is empty or actually contains objects. In practice, lots of space is wasted
• the player can be on a grid cell boundary, meaning that you have to check multiple grid cells for collisions, which is a hassle
• player might hit a large object that spans multiple grid cells

A much better solution exists, namely the quadtree. The quadtree is a brilliant, academic, high performance solution for doing spatial partitioning in game codes. There is a lot to be read about the quadtree on the interwebs, but somehow it’s not enough.

Basic algorithm

The basics of the quadtree spatial partitioning algorithm are simple. You have a 2D space (the map) and there are objects that live within the bounds of that 2D space.

• if there are more than N objects in the 2D space, split the space into 4 quadrants
• reinsert objects into the quadrants
• recurse as needed

Objects that are in the same quadrant might collide. N is a small constant, typically between 3 and 8. For collision testing, we only need to select the right quadrant and do at most N/2 tests. This holds true regardless of how many objects exist in the game world.

Caveat #1 : Only leafs contain objects

As a consequence of the rules of the partitioning algorithm, objects always reside in leafs of the quadtree. The intermittent nodes do not contain any objects. There are plenty of bad examples to be found on the internet where people get this wrong. If you get this wrong, the code will not perform optimally because it will falsely detect collisions in objects that could never collide. And thus you are wasting cycles doing excess collision tests, and missing the point of why we are using a quadtree in the first place.

Caveat #2 : Objects have size

It’s rather logical that objects in a 2D space have size (ie. width and height). Consequently objects may cross quadrant boundaries, and thus objects may reside in multiple quadrants at the same time. This requires an implementation with pointers to objects, where multiple pointers may be referencing the same object. If you get this wrong, certain collisions will go undetected, ruining the game play.

Caveat #3 : Objects in motion

A quadtree can only hold objects at a fixed position. For objects that are in motion, this means that the quadtree represents a snapshot of a situation, a point in time. Consider a game running at 60 frames per second. Each frame is a snapshot in itself. When an object moves from left to right, the object will be in a different position in every single frame, creating the illusion of movement. Because the position changes, we have to update the quadtree on every frame. If you get this wrong, collision detection won’t work. Updating the quadtree involves removing the object and re-inserting it. These are relatively expensive operations, so in some cases you might as well simply recreate the entire quadtree from scratch for every frame.

Caveat #4 : Fast-moving objects

Related to the last caveat, things are getting tricky at high velocities. Consider a fast-moving object at position (x0, y0) at the start of the frame. It’s traveling fast, and will be at (x1, y1) by the end of the frame. During this time step the object really is in two places at the same time—and in all other positions in between as well. During the time step, the dimensions of the object stretch from (x0, y0) to (x1, y1). Implementation-wise, an object now has two kinds of dimensions: bounds used for drawing, and stretched bounds used for detecting collisions by means of a quadtree. If you get this wrong, fast-moving objects may well teleport right through a wall.

Caveat #5 : Wrapping worlds

I like the game world to wrap around (ie. keep walking left, and emerge on the right side of the map). Wrapping in all directions is called a toroidal topology. The quadtree has no provisioning for this. The best thing to do is to transform the object’s coordinates from world space to camera space (or “arena space”) and work with that. Now there are two kinds of object positions: world coordinates and the transformed coordinates. If you get this wrong, the world will not correctly wrap and you may get things as crazy as objects spontaneously popping in and out of view.

I’m not trying to scare you. The quadtree is a high performance partitioning device and well-worth the coding effort, but it’s also quite complicated to get right.