```
while the game is running
foreach entity in the world
update(entity)
update(entity):
entity.old_position := entity.current_position
modify entity.current_position based on entity.velocity and other factors
if Colliding(entity) then entity.current_position := entity.old_position
Colliding(current_entity) -> bool:
foreach entity in the world
if entity != current_entity then
if Entities_Collide(current_entity, entity) then return true
return false
Entities_Collide(e1, e2) -> bool:
foreach polygon p1 in e1
foreach polygon p2 in e2
if polygons_intersect(p1, p2) then return true
return false
```

- Segregation is Good We divide the world into a regular grid that partitions objects into smaller groups, with the goal of reducing the number of entity-entity comparisons the system needs to make. Every time we move an object, we compute which squares of the grid it overlaps. For our engine we chose a two-dimensional grid, although it is a true 3D world, because the game is played over a landscape and we do not expect many objects to be piled on top of each other.
- Bounding Spheres Before doing the polyhedron-polyhedron check, we look at the distance between the centers of the two objects. If they are further than the sum of the two objects' radii, the objects cannot possibly interpenetrate. To speed this up slightly, we can check the distance squared versus the sum of the radii squared (this avoids a costly square root operation).
- I Prefer Jersey Actually, we originally had a third filter that ran before the bounding sphere test, which looked at the Manhattan distance between the objects' centers. This was not really worth the bother (It almost never saved any execution time worth worrying about) so we deleted it.

```
struct Polyhedron {
List *faces; // All polygons contained in this object
Point center; // Center of the object
float radius; // Radius of its bounding sphere
BSP_Node *bsp_tree; // BSP tree representing this object
};
enum flag_value {
TOUCHES_POS_HALFSPACE = 0x1,
TOUCHES_NEG_HALFSPACE = 0x2,
SLICED = 0x3 // Touches both halfspaces
};
struct BSP_Node {
float a, b, c, d; // Coefficients of plane equation (ax + by + cz + d = 0)
List *polygons; // Polygons that are coplanar with said plane
BSP_Node *positive, *negative; // Contents of each halfspace
};
bool object_hits_world(BSP_Node *node, Polyhedron *solid) {
if (node == NULL) return false;
int status = classify(node, solid->center, solid->radius);
if (status == SLICED) {
if (test_solid_against_polygons(node->polygons, solid))
return true;
}
if (status & TOUCHES_NEG_HALFSPACE) {
if (object_hits_world(node->negative, solid)) return true;
}
if (status & TOUCHES_POS_HALFSPACE) {
if (object_hits_world(node->positive, solid)) return true;
}
return false;
}
int classify(BSP_Node *node, Point center, float radius) {
float distance = (center.x * node->a) + (center.y * node->b)
+ (center.z * node->c) + node->d;
int status = 0;
if (distance - radius <= 0.0) status |= TOUCHES_NEG_HALFSPACE;
if (distance + radius >= 0.0) status |= TOUCHES_POS_HALFSPACE;
return status;
}
bool test_solid_against_polygons(List *polygons, Polyhedron *solid) {
Polygon *face1, *face2; Foreach(polygons, face1, {
Foreach(solid->faces, face2, {
if (polygons_intersect(face1, face2)) return true;
});
});
return false;
}
```

```
longest_radius := 0.0
foreach vertex in the object
vertex_distance := distance from vertex to object's origin if
vertex_distance > longest_radius
then longest_radius := vertex_distance
```

Object Type | # of Polygons before BSP cuts | # of Polygons after BSP cuts |

hovertank | 97 | 111 |

cargo box | 12 | 12 |

repair pad | 69 | 96 |

Collison Test | # of definitive answers | Average Running Time |

bounding spheres | 3800 | tiny |

bounding box safety | 1911 | 26.13us |

plane divides entities | 93 | 231.94us |

BSP hard case | 842 | 450.98us |