Two layers: the road you edit and the lanes cars drive

Part two of a series. Part one is what DrivEngine actually is.

There are two descriptions of every street in DrivEngine, and they do not look alike.

The first is the one a person edits. It says: this road runs from here to there through these control points, it has two lanes each way, the lanes are this wide, the left one becomes a turning lane near the end, and there is a median.

The second is the one a driver reads. It says: here is a curve, three hundred points of it, it starts at this position with this tangent, its left edge is here and its right edge is here, it leads into those two other curves, and a car on it may change onto the curve beside it.

The first is called the editor layer. The second is the lane layer. Turning the first into the second is called a bake, and almost every good property of the system comes from the fact that these two are not the same data.

Why not just one representation?

Two versions of the same road sound like a synchronization bug waiting to happen. In practice, only the editable version is a source. The lane layer is rebuilt from it, so there is no choice about which one is current.

The editor layer is lossy in the right direction. "Two lanes each way, three and a half metres wide" is a small amount of data that a human understands and can change. The lane layer is the expansion of that, and it is large. You do not want a person editing an expansion, and you do not want a driver parsing an abstraction at sixty ticks a second.

The driver never sees authoring concepts. A driver has no idea what a median is, or that a lane was widened at one end, or that two roads were joined at a port. By the time the car exists, all of that has been resolved into geometry and connections. This is the main reason the driver code stays small. Every question a driver asks has already been answered by the bake.

The bake is where the hard checking happens. A turn tighter than a car can steer is caught once, at bake time, rather than being discovered at runtime by a car that physically cannot follow its own path. More on that in part three.

One of them is the thing you serialize. Saving the world saves the editable definition. Loading it and baking gives you the same lanes. That also makes a road exchange format possible, which is how road networks from other sources get imported.

What a road bake produces

A road in the editor layer is a chain of nodes. Each node has a point, a direction, and a cross section, and the cross section is a list of slots: drivable lanes, and non drivable ones like shoulders and medians. Between two nodes, each drivable slot becomes one lane, as a curve offset sideways from the road spine by the widths of everything to its left.

Two details in that sentence carry most of the complexity.

The first is that the cross section can change along the road. A lane can start at one width and end at another, a lane can appear, a lane can end. So the bake has to work out which slot in this node corresponds to which slot in the next one. When two nodes disagree in a way that cannot be resolved, that is an error the author has to fix, not something the bake guesses at.

The second is that lanes are offset curves, and an offset curve is not a simple thing. Offsetting a curve sideways changes its curvature: the outer lane of a bend is a longer, gentler curve than the inner one. That is correct and it is also a place where geometry bites, because a tight enough bend makes the inner offset fold over itself. The editor layer is where a person can see that and widen the bend.

Once the lanes exist, the bake connects them. Along a road, each lane leads into the next segment's lane. Beside it, a lane gets a lane change link to its neighbour, but only where the author allowed a change and only where both lanes go the same way.

What a junction bake produces

A junction is a point with arms, and its bake produces connectors: one curve for every permitted movement from an arm lane to another arm lane. Part three is about how that list of permitted movements is decided, so here I will stay on what comes out.

Beside the connector curves, the junction bake produces something more interesting: the relationships between them.

Merges. Two connectors that end at the same exit lane are merging. A driver reaching that point has to think about the car beside it, not only the car in front.

Conflicts. Two connectors whose curves cross are in conflict. The bake stores where the crossing starts and ends along both curves. Drivers do not need to intersect geometry as they approach. Both read the same stored numbers.

That last clause matters more than the performance saving. If two drivers compute the same fact separately, they can disagree, and two drivers who disagree about whether their paths cross is exactly how you get a collision. Computing it once at bake time and letting both read it means they cannot disagree.

One graph, several kinds of edge

After the bake you have a set of lanes, and between them several distinct kinds of relation:

• leads into: a car on this lane can continue onto that one.
• may change to: a car on this lane may move sideways onto that one.
• merges with: these two end in the same place.
• conflicts with: these two cross, here, at these distances.

Plus the links back to the editor object that produced each lane, which is what lets a rebake delete exactly the lanes it is replacing and leave the rest of the world alone.

Everything in the runtime is a query over this graph.

Routing is a shortest path search across "leads into" and "may change to". The cost is not distance, it is travel time, taken from each lane's speed limit. So a driver prefers a longer arterial road to a shorter residential one, which is what real drivers do and, more usefully, what makes generated towns feel like they have a road hierarchy even when nothing explicitly says so.

Lane changes fall out of the same search. A lane change is just an edge with a cost. The router does not have a special case for it.

Junction crossing is not a special case either. A route through a junction is simply a path that happens to pass through connector lanes. There is no separate junction pathfinder.

Yielding reads the conflict edges of the lanes ahead.

Because these relations live in one graph, a new road question often needs another relation rather than another parallel system.

Joining roads and junctions

Roads and junctions are baked separately, and they are baked from separate editor objects. So after both have run, a junction's connectors are floating free of the road lanes they should attach to.

The joining is a second pass, and it walks the ports. A port is a declaration in the editor layer that says "this end of this road attaches to this arm of that junction". The pass walks those declarations, matches each connector to the road lane its arm lane corresponds to, and adds the "leads into" relations that make a road and a junction one continuous graph.

Ports do one more job, before the bake rather than after. Attached ends are snapped: the road end takes the position and direction of the thing it is attached to. This is why dragging a junction in the editor drags the road ends with it, and why an author cannot accidentally leave a two centimetre gap between a road and the junction it plugs into. The attachment is a fact in the data, so it is enforced rather than maintained by hand.

Spatial queries and change tracking

Drivers ask geometric questions constantly. Which lane am I on. Which lane is nearest to this point. What is around this car.

Lane curves are not cheap to test against, so the lanes live in a spatial tree keyed by their bounding boxes. The tree is not rebuilt every frame, because that would be wasteful on a set of objects that mostly never move. Instead the world tracks which components were added, changed or removed since the last time anyone looked, and the index updates only those.

There is a nice property here that comes from using an entity component system with change tracking underneath. A rebake despawns some lanes and spawns others. The index does not need to be told about the rebake. It sees lanes appear and disappear, and it maintains itself. Nothing in the bake code knows the spatial index exists.

What the bake costs, and the part I have not solved

A bake is not free. Baking a whole town is a job you run on a worker thread and wait for, not something you do while the user is dragging a gizmo. The junction bakes parallelize well, because junctions are independent of each other, and that is done. The joining pass at the end is a single walk.

The weak point is granularity. Moving one junction rebakes more than necessary. Every lane already knows which editor object produced it, so the affected set can be found, but selective rebaking is not implemented yet.

Keeping the boundary

The runtime never reads the editor layer. When a driver needs a fact that is missing, I add that fact to the baked data. So far, each missing fact has fit naturally as another relation in the lane graph.

---

The next article is about the place where that rule is hardest to hold: the junction, where a shape drawn by a human has to become a set of turns that cars can actually drive.