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
- 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.
- Store static geometry (buildings, roads, ...) in every cell that overlaps it.
- Create the grid
- Collision detection
- Get the AABB (Axis-aligned bounding box) of the vehicle.
- Get cells overlapping with the AABB.
- Go through geometry listed in the cell and test for collisions.
- 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:
- Get the coordinates of overlapping cells for the vehicle's AABB.
- Use a spatial hashmap with those coordinates.
- Test collisions with any vehicle already registered in these cells (+use "tested" set)
- 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