How to build a "traffic AI"?

Question

A project I am working on right now features a lot of "traffic" in the sense of cars moving along roads, aircraft moving aroun an apron etc.

As of now the available paths are precalculated, so nodes are generated automatically for crossings which themselves are interconnected by edges. When a character/agent spawns into the world it starts at some node and finds a path to a target node by means of a simply A* algorithm. The agent follows the path and ultimately reaches its destination. No problem so far.

Now I need to enable the agents to avoid collisions and to handle complex traffic situations. Since I'm new to the field of AI I looked up several papers/articles on steering behavior but found them to be too low-level. My problem consists less of the actual collision avoidance (which is rather simple in this case because the agents follow strictly defined paths) but of situations like one agent leaving a dead-end while another one wants to enter exactly the same one. Or two agents meeting at a bottleneck which only allows one agent to pass at a time but both need to pass it (according to the optimal route found before) and they need to find a way to let the other one pass first. So basically the main aspect of the problem would be predicting traffic movement to avoid dead-locks.

Difficult to describe, but I guess you get what I mean. Do you have any recommendations for me on where to start looking? Any papers, sample projects or similar things that could get me started?

I appreciate your help!

Answer 1

There are so many ways of addressing this problem I'd struggle to give a decent and comprehensive answer here. But here are some high level design points.

• You're building an agent simulation here. Pathfinding is simply one input into the system - the agent has a goal, and path-finding is just a way it can achieve that goal. Actually, thinking of it in real terms the agent has two goals: a driver's foremost goal is "don't crash", second to that is "get where I want to go".

• Your systems should build on real world parallels. The reason why most roads have two or more lanes is because it's much easier to organise traffic with that system, no-one has to think very much. In a single lane scenario, drivers have to sort out various problems:

  detection - recognising that you and the oncoming car will crash unless you avoid each other

  reaction - slowing down and entering into a negotiation phase.

  negotiation - one of the drivers has to take the lead, the other has to yield. The rules for how to decide this are vague, but basically you want something where one driver arbitrarily (or based on a heuristic about how many cars are coming in the other direction) decides to take priority. E.g. A takes priority at time 1, B sees A take priority, and yields (by moving out of the way and stopping). If both A and B try to take priority, they should both stop, wait a random amount of time (or signal each other) and try again. Eventually one will yield to the other.

  The beauty of this implementation is that it avoids the need to maintain artificial queues or other fake constructs. The negotiation is done in terms of real world perceptions - once both parties are in the negotiation phase, any significant forward motion is easily detected as an attempt to take priority. It should also react appropriately to the user, who will most likely not adhere to good driving rules.

• Assume the worst. Even in a perfect system, odd situations can come up, and your actors should act sensibly. This is even more likely if the player can interfere (artificially block off areas, etc.) Often, stopping altogether is the only sensible response (gridlock!) Spinning on the spot or obviously being in a broken state is a failure of AI. Stopping altogether is at least plausible in real world terms.

  The closer you model your actor's AI on simple real world logic, the easier it will be to create convincing AI. Real people don't stop or oscillate back and forward if they can't reach their goal. If the only road to the AI's destination is blocked, they should recognise that and choose a response (stop altogether, give up and drive home, give up and drive elsewhere).

• Layer behaviours to get what you want. Remember, 1st goal is not to crash. So avoidance (steering) logic should always dominate the driver's actions. Layer on top of that the directional logic that comes from the path-finding ('I want to take a right at the next junction'). Layer on top of that occasional re-evaluation of paths, with higher level logic ('prefer to go forward, but if I can't make progress, allow a new path that involves a U-turn').

• Path-finding comes from memory, but situational awareness is based on perception. Don't try to make your agents perfect. They know the way from their home to the office, so they know which turns to make. But they don't know that the street 2 miles away is blocked. Don't try to make your agents plot a perfect path, because there are none - even if it starts out perfect, other factors may block their path. Agents should only need to plan a few streets ahead where they're going.

• Information quality. Your behaviours should be simple, but to achieve that you need good query functionality. You need to be able to ask questions of your environment like "is that oncoming car occupying my lane?", "how many cars are oncoming?", "are there any cars behind me", "can I do a U-turn".

Answer 2

Having seen some horrible failures in released games I have a couple of suggestions:

1) Unless there is a good reason otherwise make two lanes and for AI purposes make them have priority for a normal direction of flow--permit two-abreast travel but if something's coming the other way the guy on the wrong side of the road always yields to it.

2) Some sort of logic to unwind a traffic jam if it occurs. I've watched situations where the traffic jam handling only applied to the vehicles that were trying to run into each other but utterly failed when confronted with a -> -> <- <- pattern. I recall one map that was prone to this--it was a chokepoint meant to make the AI base harder to attack but sooner or later two resource harvesters would come in while an attack group was heading out and that was that. The units in contact would spin around trying to find a route out but they had no legal moves. It didn't backtrack and figure out that some other unit had to move first, and thus the AI took no useful actions until the roadblock was removed. (You could watch the units in contact spin around and nothing else do anything.)

I believe this could be solved by making a stuck unit tell neighboring units to get out of the way--this would propagate until it reached an unstuck unit that could back away. This would have to involve some sort of logic to keep them away until the problem was cleared.

Note that simply looking for an alternative path is often a bad answer. I've watched a livelock situation of that kind--unit A notes that B is blocking the road up ahead and so it turns around to use a different route. This now blocks the road for B who turns around--now the road is unblocked so both turn around again. Each turn they alternate between moving forward and moving backwards.

The same game I've seen a different version of it, also due to the fog of war. There was an enemy unit at a chokepoint. On auto-move the pathfinding would not fight unless actually targeted on the enemy unit. It would move forward and see the road was blocked. It then moved back, it could no longer see the blocker and it would move forward again. Repeat until the human realized it wasn't getting where it was supposed to go.

Answer 3

I'm not too experienced with traffic simulations, but a few things spring to mind.

Firstly, to prevent bottlenecks in the first place I would have two lanes that allow the vehicles to travel in opposite directions. on the same "road".

Secondly, for collisions that may occur, you should have a collision avoidance steering behaviour to prevent a massive pile up. Steering behaviours may be low level, but they're very useful in creating realistic looking emergent behaviour.

If you don't want to have more than one lane you're going to have to store more information in the graph. For example, if agent A is on a road (represented as a graph edge) and agent B is on the same road moving in the opposite direction to A then they will collide/deadlock/whatever you've coded to deal with this behaviour.

However, if agent A is on a road, it could request ownership of that road. Owning the road would mean that no other agent can travel along that edge (you could do this quite simply by changing the edge cost to a massive number to make sure A* doesn't choose the road when calculating a path). Then when agent A is free of that road it relinquishes ownership.

Honestly, it's a hacky solution that I'm not particularly fond of and most traffic simulations (if not all?) that I've seen use a multi-lane approach.

Answer 4

You said you looked up several articles about steering behaviour, though just in case, have you looked up the following one?

http://www.red3d.com/cwr/steer/

If not, it might provide you some answers, as it covers some of the problems you named, for example the bottleneck problem (Queuing).

Answer 5

I think what you need to do is implement a path finding algorithm.

Break up your map into as small of pieces as you can (say squares) but only for valid places for traffic to travel. You would then determine where the vehicle is and where it is going and find a path, shortest or most direct perhaps. The path will be a array of squares, each step of the way to the destimation. What you would then want is to calculate not only the current position of all vehicles but the future positions of vehicles for a couple of steps in the future. If two vehicles are going to be in the same square in the future then you need to change the velocity of one or both of them.

A* (A star) is a very simple path finding algorithm that you can probably just easily translate the psuedo code in wikipedia into your language of choice and it will work: http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 6

When I implemented Enemy Nations my final fall-back was that if a vehicle was stuck for over 2 seconds, I jumped it forward on its path. So when they got stuck a unit basically transported. No one ever complained so I figure the few times it happened no one was watching and didn't see it.