procedural generation - How to generate a city street network?

I would like to create a city generator for a game, but I am facing a problem at the very start of the generation: the road system.

As it is a medieval world, I don't want a grid plan like many modern cities. I would ideally prefer a pseudo-random generation of large avenues and smaller streets, where it could be possible to get lost, but with still some logic - not a complete labyrinth.
Something that would look like a naturally grown town.

In order to keep it simple, let's say my cities would be on flat and stable terrains, without any river-crossing or relief problems. I could try to integrate it to a solution after.

I didn't decide of a precise size or disposition for my cities, so if you have a solution that would work only with cities of a precise form (square, circle, rectangle etc), I would take it.

Answer

A good place to start with procedural city generation is Parish and Müller's Procedural Modeling of Cities. Their paper presents an L-System in which rules concerning population density & road patterns (rectangular grid, radial & least elevation change) are combined and then fixed to accommodate local constraints such as water fronts & road aesthetics. While the results of this system are impressive, it has been criticized as being unnecessarily complicated. Barrett's alternative solution is restated in Rudzicz's Spare Parts dev blog as follows:

• maintain a list of "proposed" roads


• evaluate them in some order


• if they are acceptable (with or without some minor modifications)


• store each accepted road while "proposing" a handful more branching from it

This approach removes most of the symbol rewrite housekeeping inherit in Parish and Müller's L-System. You can see an demo of this approach here.

A benefit of this approach is that it is city shape agnostic - you can add outline constraints as needed, so your city shape can be determined by your game design needs rather than the algorithm. Depending on your city size, this might be good enough as is. Here's a result from the above demo with a segment limit of 100: But if you need something big, you may have trouble; here's a result with a segment limit of 500:

In part, you can adjust this by changing the road branching rules, avoiding 90 degree angles, etc. If your layout is still too regular, here's my correction:

Transform your city grid into a graph where each street is an edge & each intersection is a node. Next, use whatever algorithm you prefer to convert the graph into a maze. Here's the last example turned into a maze:

Now the output has the opposite problem, it's too maze like. But now we can apply a couple of techniques from the Secret Workings of Jamis Buck's Dungeon Generator. First, increase the sparseness by removing some dead end corridors. Next, increase the connectivity by adding in roads that create loops (i.e. introduce cycles to the graph). Here's an example result:

Note: it is possible to achieve the same final result directly from the earlier grid oriented layout stage (before generating the maze), by only apply edge removals to the city grid. The problem with that approach is you must ensure removing an edge doesn't partition the city thereby making portions unreachable.