Box collisions between vehicles in traffic pattern

Question

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).

Answer 1

This is commonly achieved by casting rays out from the front of your vehicle.

If your engine doesn't have an implementation of that, at a high level you could implement it manually as:

For each vehicle:

• Find all vehicles in a radius r (or just round up to a bounding square to save the maths)
• Determine whether a line projected forward from the vehicle passes through the bounding box of any target vehicle¹.
• Check line length < radius (or don't bother an instead account for overshoot in the next step)
• Perform some scaling/clamping to get a "braking" factor.

The closer your vehicle gets to one in front, the more rapidly it will brake. Cars behind will follow in turn.

You'll probably want to fire 3 or 5 rays per vehicle in a fan pattern to handle corners/lane changes.

¹ For this step, it's basically just checking whether the ray crosses any of the 4 lines defining the bounding box, althoughn I'm guessing you have this already.

Answer 2

Couldn't you create an event collision box in or around your vehicles to detect if there is another vehicle in front of them?

Then, on that collision you could get the id of the leading car, and create the chain. Since it'll compute once, on_collision_enter, you won't have to keep constant track of every cars speed and velocity.