Three tiers of a driver

Part four of a series. It follows what DrivEngine actually is, the road you edit and the lanes cars drive, and a junction is a decision.

A driver has to answer three questions at three completely different rates.

Where am I going? Answered once, when the car gets a destination, and again only if the route becomes invalid.

What should I be doing right now? Answered every tick. Should I brake, should I yield, is the junction ahead full, is that pedestrian going to step out.

How do I move the wheel and the pedals to make that happen? Answered every tick as well, but it is a different kind of question. It is not about traffic. It is about a machine that has mass and a steering rack.

DrivEngine puts these in three tiers, and a tier never reaches down into the one below it.

Tier one: the route

Routing is a search across the lane graph from part two. The cost of an edge is travel time rather than distance, which takes the speed limit of each lane into account, so a driver prefers a faster road even when it is longer.

The result is a path: a list of lanes, plus where on the first lane the car starts and where on the last lane it should end. Nothing else. No timing, no speeds, no instructions.

Two things about this tier are worth saying because they are easy to get wrong.

Routing over the same graph the cars drive on. There is no separate navigation mesh, no simplified road graph beside the real one. The lanes the router walks are the lanes the car physically follows. A route that the router says exists is a route a car can actually drive, because the same connectors that the junction bake kept are the edges the router walked.

Rerouting is normal, not exceptional. A car reaching its goal gets asked what to do next by the code that owns the simulation, which can hold it, despawn it, or send it somewhere new. A car that has drifted off its path tries to reattach to the network near where it is. A car that cannot find any path from where it stands is marked stranded instead of left spinning. The interesting part of routing is not the search, it is having an honest answer for every way a route can stop being true.

Tier two: the decision

This is the large tier, and it is where all the traffic behaviour lives. It runs every tick for every car, and it produces two outputs: a target speed, and a point to steer at.

That is it. The decision tier never touches the wheel, never touches the pedals, and does not know what kind of vehicle is underneath it.

Look ahead along the path, not around the car

The first thing a driver does is scan forward along its own path. Not a sphere around the car, not a cone. Along the path it plans to take, for a distance that depends on how fast it is going.

This is a small decision with large consequences. A car approaching a junction does not care about the road to its left in general. It cares about the specific movements that cross the specific connector it is about to use. Because the path is known and the conflicts between lanes were computed at bake time, the question "what crosses my path in the next eighty metres" is a graph lookup rather than a geometric search.

The scan collects the things worth reacting to: curves and how tight they are, speed limits and where they change, junctions ahead, conflicts ahead, crosswalks, and the end of the path.

Every rule proposes a speed, and the lowest one wins

The decision tier became much easier to debug after I changed how rules combine.

Each concern produces a proposal: a speed, and a reason for it. The speed limit proposes a speed. Each curve ahead proposes the speed at which it can be taken. The car ahead proposes a following speed from the gap and the closing rate. A crosswalk with someone on it proposes stopping short of it. A conflict where the driver has decided to yield proposes stopping at the line. A junction whose exit has no room for this car proposes stopping before entering.

Then the solver takes the lowest proposal, and it keeps the reason.

My first instinct was a chain of conditions: follow a car, otherwise check the light, otherwise check the junction. Once several things matter at once, that chain hides why a decision won. Proposals leave all candidates visible.

Proposals fix that in a way that goes beyond tidiness:

Adding a behaviour does not touch existing ones. Pedestrian crossings were added as a new proposal. Nothing about car following changed, and nothing about car following needed to be re-tested.

The winner is a value, so it can be stored. Every car carries the reason its speed was chosen. That reason is in the debug overlay, it is in the recorded run on disk, and it is in the analysis tools. When traffic is behaving oddly, the first question is not "what do I think is happening", it is "what did every car say was holding it back", and that question has an exact answer.

Counting reasons becomes a measurement. If a change moves the number of ticks where the winning reason was "blocked junction", you learn something about junctions specifically, rather than about traffic in general. Several of the results in the rest of this series exist only because reasons are countable.

Every rule computes a proposal even when it will not win. The extra work is small arithmetic per car per tick, and it keeps every candidate available for debugging.

A survey before anybody decides

Rules like "who is in front of me" and "which of us has right of way" cannot be answered by a driver in isolation, and the order in which cars are asked must not change the answer.

So each tick starts with one pass over the whole population that computes the relational facts: who follows whom, who is merging with whom, who yields to whom, who is occupying which piece of a junction. Only after that pass finishes does any car make a decision.

If a driver were allowed to decide while surveying, the result would depend on the order the cars happen to be visited, and the same scenario would drive differently for no visible reason. Fixing the order is what makes runs repeatable, and repeatable runs are the precondition for measuring anything at all.

The part that is still hard

Right of way is the hardest problem in this project and it is not finished. There is now a layer above the driver's own judgement: a junction hands out admission, which means the decision about who may enter is made once, for the junction, and not negotiated pairwise between drivers who each hold half of the picture.

Getting there took several designs that failed for one reason that took me a long time to see, and parts five and six of this series are about it. I will not compress it here, except to state the conclusion, because it generalizes: a promise has two sides, and if only one side can read it, it is not a promise.

Tier three: the control

The decision tier has produced a target speed and a point to steer at. Turning that into motion is a different discipline.

Steering runs a controller on the angle between where the car is pointing and where the steering target is. The target sits ahead of the car at a distance that grows with speed, which is the classic pure pursuit idea: look further ahead when moving faster, so that the correction is gentle instead of a twitch.

Speed is the part I got wrong for a long time.

The naive design is one controller on the difference between target speed and current speed. It works, and it has a flaw that hides for months: to brake at a given rate, the controller needs an error large enough to push the pedal that far, which means the car must already be going faster than it planned to be. Comfortable braking only happens once the car is uncomfortably fast.

The fix is to separate the plan from the correction. The decision tier does not only say what speed it wants, it says what acceleration it intends to use to get there. That intended acceleration maps directly onto pedal travel, because the vehicle model knows what its pedals are worth. The controller is then left with a much smaller job: correct the difference between the speed the plan predicted for this moment and the speed the car actually has.

Plan open loop, correct the residual. The controller stops fighting a problem the planner already solved, and the pedal stops being a proxy for how wrong things are.

That story has a sequel that is more interesting than the fix itself, and it is part seven of this series. The short version: once braking was correct, a large number of hard braking events did not go away. They had never been a control problem.

The vehicle underneath

The default vehicle is a kinematic bicycle model: enough to make a car turn like a car, obey a steering limit, and accelerate and brake at plausible rates, with none of the cost of a real vehicle simulation. For hundreds of background cars that is the right answer.

But the tier boundary means the vehicle is replaceable. A car can be marked as owned by something else, and then the host engine drives it. The game pushes the car's transform into the simulation each frame, the simulation reads it, and every other driver sees that car exactly as it sees any other. That is how a physics vehicle and an AI car share a junction: the physics car is not special to the traffic, it is just a body that moves and that the traffic can see.

This is also the path the player takes. A player driving a car in the world is, from the traffic's point of view, one more car whose transform somebody else is computing.

The tick, in order

Putting it together, one simulation step does this:

1. Refresh the spatial index for anything that moved or changed.
2. Scan each car's path ahead, from where it is now.
3. Survey the whole population: followers, merges, right of way, junction occupancy.
4. Ask each junction who it admits.
5. Decide, per car, producing a target speed, a steering target, and the reason.
6. Step the controllers to get steering, throttle and brake.
7. Step the vehicles.
8. Put each car back on the road surface, since the road has height and the planner works in the plane.

The order matters. Everything relational happens before anything individual. Everything decided happens before anything applied. A plan reads the world, and only then does a write touch it.

The tiers can be tested separately. Steering needs no traffic, and a speed proposal usually needs only a few numbers. New behaviour arrives as another proposal rather than another branch through existing behaviour.

The most useful result is the stored reason. It appears in the live overlay and in recordings, so I can count why cars slowed across a full run instead of guessing from a replay. That became the basis for several investigations later in the series.