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:
TileGridcontaining road segments.
TravelGraphgraph of waypoints for
Vehiclesto travel along the
CollisionTrackerfor efficiently determining which vehicles are colliding, i.e. O(1) lookup for
get_collisions(<vehicle_id>) -> List[<vehicle_ids>]
Intersectionfor determining which vehicles are waiting at an intersection and determining which
Vehiclesmay pass through it.
The only seemingly-viable algorithm right now is:
- Calculate velocities and position of all vehicles after tick
- Determine which vehicles are in a collision
- 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)
- 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]).
- 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
Vehiclein front of them.
Problems with this solution:
- This requires a lot of recalculations. If there's a line of
nvehicles waiting on a light, I'd effectively compute 2*
npositions 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
TileGraph (purple), and