16
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You might want to look at the procedural city generator by Introversion Software which they made for Subversion. While the game itself got canceled, there is plenty of footage around from their generator. \$\endgroup\$ – Philipp May 27 '16 at 8:14
  • \$\begingroup\$ Do you have an example of what you do want (real life example from your target time period, example from another game, sketch, etc)? There's a lot of options between 'not a grid' & 'not a complete labyrithn'. \$\endgroup\$ – Pikalek May 27 '16 at 17:41
  • \$\begingroup\$ @Pikalek I don't give more precision because I don't have it. I'm not looking for something very specific, any example of generation which doesn't generate neither a maze nor a grid plan could satisfy me. \$\endgroup\$ – Aracthor May 28 '16 at 4:56
21
\$\begingroup\$

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: enter image description here But if you need something big, you may have trouble; here's a result with a segment limit of 500: enter image description here

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: enter image description here

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: enter image description here

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.

\$\endgroup\$
6
\$\begingroup\$

If you look for medieval/old city plans on Google you'll find many different variations, mostly based on city origins (e.g. random settlement vs. organized military position).

I assume you're looking for a more naturally grown/chaotic settlement.

For these I'd try an approach like this:

  • Start out with a main road going from one end to the other (and ideally connecting some other settlements. If you want, create a third road so you get a junction on which to start your settlement.
  • Place some houses along the road (on one side only).
  • Now widen that road along the houses and add a major landmark on the other side (typically a church, but this could also be some mill or similar). This is going to be your center/marketplace.
  • Now pick two positions outside the area with the houses and create a new road enclosing the houses.
  • Optionally create some smaller allies between houses connecting the old and new road.
  • Now repeat until you're happy with your "core":
    • Add a few more houses.
    • Add another road enclosing them.
    • Add back alleys connecting the roads.
  • Once you're happy with that, you're done. If it's supposed to be a town, surround it with walls and repeat the last steps a few more times, adding additional houses outside the walls.
\$\endgroup\$
3
\$\begingroup\$

First of all, there are loooooot of ways to do procedural generation and none of them is easy at all, i will make kind of approach to how you could make it work, is up to you take it, modify it or discard it.

Will pseudo-code in JS as it's easier to understand.

1º define an entry point, as you want to build a medieval city we gonna start with a square, so lets say your town will have 300 squared units and the square will be in the middle of it (represented with an X).

       300
________________
|               |
|               |
|               | 300
|       X       |
|               |
|               |
|_______________|

const square = [ 150, 150 ];

2º now we will the avenues, there will be a random number of them, they will be straight and will start from the middle square or from other avenues

let avenues = [] // will contain start and end [[sx,sy],[ex,ey]]
const n_avenues = RANDOM(4, 8); // number of avenues
const n_av_from_square = RANDOM(0, avenues); // starting in the square

for av in av_from_square
  avenues.push(square, [RANDOM(0, 200) + 100, RANDOM(0, 200) + 100])
  // we want avenues to have, at least 100 units length, thats why we randomize just te last 200 units of the whole town size

This should give you a square and couple main streets

       300
________________
|   \\          |
|    \\         |
|     \\        | 300
|       X=====  |
|               |
|               |
|_______________|

Now we have to set the avenues that doesn't start in the main square, they will intersect the other avenues

for av in (n_avenues - av_from_square){
  const av_to_intersect = avenues[RANDOM(0,avenues.length)];

  //check av_to... and get a perpendicular vector (explained bellow)
  av[0] = [ av_to_intersect[0][1], - av_to_intersect[0][0] ];
  av[1] = [ av_to_intersect[1][1], - av_to_intersect[1][0] ];

}

To get perpendicular vectors you have to swap the x,y cords and negate the new y:

swiped == x: noswiped.y, y: -1 * (noswiped.x)

Right now you should have something similar to this, doesnt it look like a town? :P

       300
________________
|   \\  //      |
|    \\//  ||   |
|     \\   ||   | 300
|    //\X=====  |
|   //     ||   |
|          ||   |
|_______________|

3º now you only have to interconnect the avenues with short streets, also, you could spawn random squares all along the town and make the same as above for all of them, or just spawn small streets from some secundary squares, it's up to you.

Remember, the shortest your streets are, the chaotic the town looks like.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.