Collision Detection

Spatial Lookup

For acceleration purposes: use a grid over the map to perform fast lookup of geometry (buildings, roads, ...) and other vehicles.

Static geometry

• Initialization
  1. Create the grid
     • Grid size: cover the entire static map.
     • As cell size use a size bigger than a circle around vehicles.
     • Goal: Lookup maximum 4 grid cells.
  2. Store static geometry (buildings, roads, ...) in every cell that overlaps it.
• Collision detection
  1. Get the AABB (Axis-aligned bounding box) of the vehicle.
  2. Get cells overlapping with the AABB.
  3. Go through geometry listed in the cell and test for collisions.
  4. Add the geometry object in a (hash-) set for already tested objects. (And skip those in step 3)

Dynamic Geometry (other vehicles)

• At every time-step, for every vehicle:
  1. Get the coordinates of overlapping cells for the vehicle's AABB.
  2. Use a spatial hashmap with those coordinates.
  3. Test collisions with any vehicle already registered in these cells (+use "tested" set)
  4. Add the vehicle to the cells.

Notes:

• Using a spatial hash-map allows to "destroy" it every time-step in order to reset the positions of the vehicles. (Instead of going through all cells and clearing the lists.)
• Only performing the collisions with already registered vehicles removes duplicate (symmetrical) checks between vehicles.

Vehicle-Vehicle collisions

• Cuboid-cuboid detection: Separating axis theorem -> Check 15 axes
• https://www.jkh.me/files/tutorials/Separating%20Axis%20Theorem%20for%20Oriented%20Bounding%20Boxes.pdf

Vehicle-geometry collisions

Handling collisions