A town from a seed

Part nine of a series. Earlier parts cover what DrivEngine is, the two layers, junctions, the three tiers of a driver, right of way in two parts, a debugging story, and how any of it gets measured.

Almost every measurement in this series was taken on a town nobody drew. You give the generator a number, and it gives you streets, junctions, lane counts, hills, and in some configurations signs and traffic lights too. The same number always gives the same town, and that is a test rather than a nice property.

Why it exists is not the reason people usually assume.

It is not there to make pretty cities. It is there to produce road networks that no human would ever draw, so that the tools have to survive them.

A hand drawn test map is a map you designed, which means it is a map that agrees with your assumptions. Every junction meets at a sensible angle, because you drew it that way. Every road is a sensible length, because a road three metres long looked silly so you fixed it. The generator has no taste. It produces two roads meeting at fifteen degrees, three roads where two are nearly parallel, hairpins, and streets barely longer than the cars on them. Every one of those has broken something real, and each break was a defect that a human drawn test map would have politely hidden until a customer found it.

From one number to a graph

The chain is short, and every step in it is ordinary. The interesting part is the order.

A number becomes a field. The seed initialises fractal noise, a few octaves of it, which is a smooth random surface over the whole area. This one field gets used three times over, for three unrelated purposes, and that reuse is the first thing I would take from this design.

The field becomes points. Candidate positions are drawn at random across the area and kept or rejected according to the field. So point density follows the terrain instead of being uniform, and the seed alone decides where the town wants to be dense.

The points become a triangulation. A Delaunay triangulation over the scattered points, which is the standard way to turn a cloud of points into a mesh with no absurdly thin triangles.

And then the roads are not the triangulation. This is the decision the whole generator rests on.

Why the roads are the dual

The obvious move is to use the triangulation edges as streets. The points are places, the edges join them, done.

It produces a terrible town. Triangles mean three way junctions everywhere, at every angle, with long thin blocks between them, and it looks like a spider web rather than anywhere anyone lives.

The roads are the dual instead. Every triangle contributes a point, and a road joins the points of two triangles that share an edge. That dual is a Voronoi diagram, and what it does is invert the meaning of everything:

• The original scattered points stop being places to connect. They become the centres of city blocks.
• The dual cells around them become the blocks themselves.
• The dual edges, which are the boundaries between blocks, become the streets.
• The corners where three or more cells meet become the junctions.

The result reads as a town. Irregular blocks of believable size, streets that curve around them, junctions with three or four arms rather than a uniform mesh of triangles. It is the same shape you get in old European cities that grew instead of being planned, for roughly the same reason: roads end up being the space between things people built, not the lines between the things themselves.

There is a second, less romantic benefit. A Voronoi layout produces exactly the awkward geometry the tools need to survive. Corners where cells meet at glancing angles are common, not rare. That is a feature for a test map and would be a bug for a shipping city.

The merge grid, which is a few lines and saves a lot

Two dual corners can land almost on top of each other. In the raw output this happens constantly, wherever four points in the original cloud are nearly co-circular.

Two junctions a metre apart are worse than one. The road between them is shorter than either junction is wide, so each junction eats it, and the bake produces either a road of zero length or two junctions that overlap. Both are failures three layers further down, and both look like junction construction bugs when they surface.

Junction positions pass through a spatial grid as they are created. A new corner within the minimum distance of an existing corner reuses that existing point. This removes the bad geometry before it reaches the junction builder.

Merging the points here avoids zero-length roads and overlapping junctions later in the bake.

Where lane counts come from

Now the field gets used a second time. Every junction records the value of the noise field at its own position, and the junctions where that value is high are marked important. Importance is just "the terrain wanted this to be busy", which is arbitrary, but it is consistently arbitrary and it correlates with the density of the surrounding blocks, because both came from the same field.

Then: for every pair of important junctions, find the shortest path between them through the graph, and give every road on that path one more lane.

That is it. And out of that comes a proper road hierarchy. Roads that many important pairs must share accumulate lanes and become wide. Roads that serve one block stay at one lane each way. The wide roads form connected corridors, because they are made of shortest paths, and shortest paths through a graph overlap heavily in the middle.

You get arterials without drawing arterials. The town has a structure it was never told to have, and the structure is a consequence of where the important places are, which is the same thing that happens in a real town for the same underlying reason.

Lane count then decides road class: one lane a side is local, two or three collector, more than that arterial. Class is what signs, speed limits and later styling read.

The third use of the field is elevation. The same noise, sampled at a different frequency and scaled to a hill height, gives the height of every point in the network, so the roads drape over terrain that was never authored either.

One number. Three jobs. Nothing has to be kept consistent between them, because it is all the same field.

Control from the graph, not from the picture

A generated town can also generate its own traffic control, and the rule for that is short, because it is entirely a graph decision.

A junction gets nothing at all if it has fewer than three arms, or if none of its movements conflict with each other. Two roads meeting is a bend, and a junction where nothing crosses anything needs no rule.

It gets signals when it looks like a real intersection of two significant roads: its busiest approach has to be at least a collector with more than one lane, that same level of busyness has to be shared by at least two approaches, and there have to be enough crossing movements to be worth a phase plan.

It gets priority signs when its approaches differ in importance. That is the normal case and it is the common outcome: a main road through, side roads yielding.

It gets nothing when its approaches are all equally unimportant, which is the residential case where everybody just negotiates.

Notice what is absent from all of that. No geometry. No angles, no distances, no shapes. The decision reads the arms, their road classes, their lane counts, and the count of conflicting movements. This is possible only because of the decision in part three, to make movements and conflicts explicit data at bake time. Once the conflicts are objects, generating control is a small graph question. If conflicts were still implicit in the geometry, it would be a research project.

Where it hurts

Three things about generated networks that cost real time.

Junctions that cannot be built. The Voronoi dual produces hairpins and glancing angles, and the strict junction rules can legitimately remove every single movement from one. That is what the escalating sequence of build attempts in part three exists for, and when even the most permissive attempt yields nothing, generation fails and the layout is rejected rather than papered over.

Junction size is a function, not a constant. How far a junction pushes its roads back is the number most likely to ruin a generated layout. Too small and the turns bend tighter than a car can steer, so the filters delete them silently. Too large and the junction eats the roads on both sides. A generated layout with a single global junction size will lose turns wherever its roads are wider than average, without saying so, and the symptom appears as strange queueing three streets away. Sizes get computed from the roads that meet, not chosen once.

The network has to be checked as a graph, not looked at. Nobody can see that a left turn is missing. So there are graph level questions to ask after a bake: does every entry reach every exit, is every lane reachable at all, can this road still reach that road. A generated town that fails those is not a town, it is a set of disconnected fragments that happens to render.

The experiment that is parked, and why

One piece of work on generated networks was measured and then deliberately left on a branch, which makes it a good illustration of the cost of a change that seems obviously correct.

About one in seven generated junctions has only two arms. A junction of two arms decides nothing, so the natural idea is to stop making it a junction at all and instead let one road bend through the point. Fewer junctions, fewer connectors, simpler town.

It works, and the branch is green on the main sweep. The problems are the ones that show up around the edges.

A road bends along a curve, and the whole cross section turns with it, so the corner radius has to stay wider than the road itself. A road four lanes wide reaches about seven metres from its centre line, so past a turn of roughly forty five degrees the outer lanes begin to fold over each other. That gives a hard limit on which two arm junctions can become bends, and measuring the tightest corner across sixteen towns is what set it: a forty five degree limit leaves the tightest road corner at about fourteen and a half metres, fifty degrees drops it to ten, ninety degrees to five and a half.

Then a second thing broke, in a place with no obvious connection. One of the driving rules checks that oncoming traffic is always on the expected side, and it worked out the side from the line between two cars up to twenty metres apart. On a road that bends, that line turns too, so two cars each correctly in their own lane read as being on the wrong side of each other. It reported violations of under a metre, constantly, on traffic that was completely correct.

A change to how roads are shaped broke a check about which side people drive on. That coupling cannot be predicted, only measured, and catching it is what part eight is for.

Most decisions happen on the graph. Connectivity and importance choose lane counts, road classes and junction control before the final geometry exists. Reusing the noise field also keeps density, importance and elevation related without another coordination step.

The ugly layouts are the useful output. They have exposed bad turns, missing connections and checks that only worked on straight roads. A hand-built test map would probably have avoided all of them.

---

The next article leaves the sandbox: what happens when this simulation has to run inside a game engine that already has its own opinion about where every car is.