# Box collisions between vehicles in traffic pattern

I'm working on a traffic simulator. Right now, I have ways to manage 4-way stop intersections and a solution for efficiently determining which vehicles are colliding with one another. All vehicles operate independently of each other and will overlap/ignore any vehicles they pass.

I'm looking to build a way to resolve collisions between vehicles such that a Vehicle will follow the Vehicle in front of it. If a Vehicle stops at an intersection, any Vehicles that follow thereafter should stop and wait as well.

Below are the relevant components I already implemented:

• TileGrid containing road segments.
• TravelGraph graph of waypoints for Vehicles to travel along the TileGrid.
• CollisionTracker for efficiently determining which vehicles are colliding, i.e. O(1) lookup for get_collisions(<vehicle_id>) -> List[<vehicle_ids>]
• Intersection for determining which vehicles are waiting at an intersection and determining which Vehicles may pass through it.

The only seemingly-viable algorithm right now is:

1. Calculate velocities and position of all vehicles after tick
2. Determine which vehicles are in a collision
3. Determine which vehicles are in a "collision group" (e.g. if A collides with B, collides with C, then (A, B, C) are in a group)
4. Determine the order of the vehicles in each group based on their velocities (e.g. if A, B, and C are moving to the right and C is the rightmost, followed by B, followed by A, then the order is [C, B, A]).
5. Recalculate the positions of all vehicles, in order from front to back (e.g. C, B, A) such that they reside adjacent to, but not touching the Vehicle in front of them.

Problems with this solution:

• This requires a lot of recalculations. If there's a line of n vehicles waiting on a light, I'd effectively compute 2*n positions per tick in addition to all other overhead for establishing groups, order, etc.
• If the vehicles are following each other around a turn, the logic for finding the "vehicle order" becomes more complex, adding on to the computations per tick.

Ideally moving the vehicles would require n calculations per tick.

I'm open to any/all suggestions here. I've tried building my code as modular as possible, so I'll happily rewrite large parts of it if there's a better architecture to solve this problem.

Below is the visual representation of the TileGrid (black), TileGraph (purple), and Vehicles (circles).