1
\$\begingroup\$

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

enter image description here

\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hmm. That’s sounds like a good potential optimization, but I may still need velocity and maybe other data to “undo” a vehicle’s action if it collides with another vehicle after the initial movement calculation, right? \$\endgroup\$ – Justian Meyer Feb 27 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.