5.6.5 Grids

The (chickadee data grid) module provides a simple spatial partitioning system for axis-aligned bounding boxes (see Rectangles) in 2D space. The grid divides the world into tiles and keeps track of which rectangles occupy which tiles. When there are lots of moving objects in the game world that need collision detection, the grid greatly speeds up the process. Instead of checking collisions of each object against every other object (an O(n^2) operation), the grid quickly narrows down which objects could possibly be colliding and only performs collision testing against a small set of objects.

In addition to checking for collisions, the grid also handles the resolution of collisions. Exactly how each collision is resolved is user-defined. A player bumping into a wall may slide against it. An enemy colliding with a projectile shot by the player may get pushed back in the opposite direction. Two players colliding may not need resolution at all and will just pass through each other. The way this works is that each time an object (A) is moved within the grid, the grid looks for an object (B) that may possibly be colliding with A. A user-defined procedure known as a “filter” is then called with both A and B. If the filter returns #f, it means that even if A and B are colliding, no collision resolution is needed. In this case the grid won’t waste time checking if they really do collide because it doesn’t matter. If A and B are collidable, then the filter returns a procedure that implements the resolution technique. The grid will then perform a collision test. If A and B are colliding, the resolver procedure is called. It’s the resolvers job to adjust the objects such that they are no longer colliding. The grid module comes with a very simple resolution procedure, slide, that adjusts object A by the smallest amount so that it no longer overlaps with B. By using this filtering technique, a game can resolve collisions between different objects in different ways.

Procedure: make-grid [cell-size 64]

Return a new grid partitioned into cell-size tiles.

Procedure: grid? obj

Return #t if obj is a grid.

Procedure: cell? obj

Return #t if obj is a grid cell.

Procedure: cell-count cell

Return the number of items in cell.

Procedure: grid-cell-size grid

Return the cell size of grid.

Procedure: grid-cell-count grid

Return the number of cells currently in grid.

Procedure: grid-item-count grid

Return the number of items in grid.

Procedure: grid-add grid item x y width height

Add item to grid represented by the axis-aligned bounding box whose lower-left corner is at (x, y) and is width x height in size.

Procedure: grid-remove grid item

Return item from grid.

Procedure: grid-clear grid

Remove all items from grid.

Procedure: grid-move grid item position filter

Attempt to move item in grid to position (a 2D vector) and check for collisions. For each collision, filter will be called with two arguments: item and the item it collided with. If a collision occurs, position may be modified to resolve the colliding objects.

Procedure: for-each-cell proc grid [rect]

Call proc with each cell in grid that intersects rect, or every cell if rect is #f.

Procedure: for-each-item proc grid

Call proc for each item in grid.

Procedure: slide item item-rect other other-rect goal

Resolve the collision that occurs between item and other when moving item-rect to goal by sliding item-rect the minimum amount needed to make it no longer overlap other-rect.