8
\$\begingroup\$

In this RPG.SE post a long-lost page with several online generators is mentioned.

I'm particularly curious about the way towns were generated. Take this image for example:

A PCG town from the defunct Irony Games

Although a lot of things could be improved graphics-wise, it was very good considering the tools available at the time (mid to late 90s):

  • The road layout seems fairly organic (even considering all roads are placed in an orthogonal manner).
  • Not all roads are necessarily connected, but it feels right.
  • Buildings are placed in believable spots.
  • Even trees seem to be placed in logical spots.

I think it would be fun to give it a shot and try it myself. Especially since my previous attempts have been too "blocky":

My latest attempt at city generation

You'll notice that I'm describing many of the qualities with not-quite-measurable adjectives (seems, feels, believable, etc) so I'm having a hard time translating them to instructions and ultimately to an algorithm.

Are there any tried-and-true algorithms for town generation?

I understand this seems to be too broad, so consider this: If I asked for an algorithm for generating maps of continental land masses, I'd get references to Perlin and other noise algorithms right away; closely followed by Voronoi.

I've seen questions like this one but they seem to have a more concrete idea already in mind (ie: 2x2 houses, fixed number of houses, canal and road placement restrictions).

What I'd like to have is something less constrained. Except maybe for the grid layout, which should be a lot easier for a first attempt than, say, L-system.

\$\endgroup\$
  • \$\begingroup\$ Listing algorithms for a broad problem domain usually ends up too broad to answer well in our Q&A format. We generally have better luck with "How can I generate game content with these specific characteristics" - where you provide a number of criteria or positive/negative examples we can use to evaluate potential answers and rate the best proposal. Can you try editing your question to explain in more detail what makes a suitable town output versus a less suitable one? \$\endgroup\$ – DMGregory Aug 2 '18 at 19:22
  • \$\begingroup\$ too broad, especially since such generators are most likely composite ones (e.g. step 1 generate roads, step 2 generate houses, step 3 generate trees). If you can narrow things down to a specific generator, and what specific problems you're having with that, that would be less broad. \$\endgroup\$ – congusbongus Aug 3 '18 at 1:53
  • 1
    \$\begingroup\$ We also have this question on procedural city generation. It might help if you could articulate how your needs differ from that question. \$\endgroup\$ – Pikalek Aug 3 '18 at 2:32
  • 1
    \$\begingroup\$ No great answer here, but one thing I notice is that in the good example, every building is next to a road, whereas in your example, they are not. \$\endgroup\$ – user1118321 Aug 3 '18 at 4:49
  • \$\begingroup\$ @user1118321: Actually, houses are not always next to a road, but either the plots are (Modern approach) or at least there is a way to the next road (maybe older approach, not like a backyard house). So spaces are not that unnatural, as market places for example. \$\endgroup\$ – PSquall Aug 3 '18 at 9:44
9
\$\begingroup\$

Introversion Software made a really impressive city generator for their cancelled indefinitely suspended project Subversion:

Subversion City Generator

The algorithm is designed to generate large, modern metropoles. But the same techniques can be used to generate more rural settlements.

It is a top-down algorithm which generates the rough outlines first and then generates more and more details to fit into them (for the opposite bottom-up aproach to procedural generation, check the answer by uliwitness). Here is a video which visualizes the algorithm in progress.

The algorithm seems to work as follows (slightly simplified):

  1. City centers: Pick some points of the still empty map as main traffic nodes. They should be evenly distributed around the map
  2. Highways: Connect the main traffic nodes to their neighbors and to the outside world using major roads.
  3. Freeways: Subdivide the cells generated by the major roads by creating some minor roads.
  4. Streets: Repeat the subdivision process recursively with smaller and smaller roads until you've reached the desired building block size
  5. Blocks: Decide the purpose of each building block (residential, retail, corporate, industrial...). Relevant factors are the sizes of the neighboring roads and the distance from the center.
  6. Allotments: Divide the edges of all building blocks into lots (this means each lot has at least one edge which is connected to a road).
  7. Buildings: Generate a fitting building for each lot.

Regarding the placement of trees: My first approach would be to integrate those in the building generation algorithm. A building does not need to fill its lot completely. You can fill the free space with appropriate decorative objects.

The problem with the top-down approach is that while it might generate a plausible city, it might not generate a plausible city with everything you want. Let's say that every city in your game needs one weapon shop, one armor shop, one potion shop and one inn. The above algorithm picks buildings based on the requirements of the lot, so you might end up with 12 armor shops but not a single inn. I would approach that problem in the building generation phase. Before you start generating buildings randomly, go through your list of must-have buildings and select the most appropriate lot for each of them. Then fill the remaining lots with randomized buildings.

I'm looking forward to exploring the procedurally generated towns in your game.

\$\endgroup\$
  • \$\begingroup\$ I totally forgot to mention streets of various sizes, good point! \$\endgroup\$ – uliwitness Aug 3 '18 at 15:26
  • \$\begingroup\$ Thanks! Not sure if I'll try top-down or bottom-up next... but realizing I have two options got my brain jumpstarted again. ;) \$\endgroup\$ – Roflo Aug 3 '18 at 16:48
5
\$\begingroup\$

Get constraints from real life

Often the answer on how to find the right algorithm starts with looking at how these things happen in real life. Have you looked into that? Off the top of my head, I can think of the following:

  • Roads are there to connect buildings and other points of interest
  • Buildings are placed along existing roads, if possible
  • If there is no road, a building is placed in an empty spot and connected to a nearby road via its own road
  • Buildings are placed near other buildings that are of interest to their inhabitants: People move to live near their workplaces, food and clothing stores etc.
  • Buildings are placed near resources that are necessary for their intended use. E.g. a sawmill is placed near forests, or even in a forest clearing. people need water and food (plants, animals) to live somewhere.
  • Buildings are placed far away from other buildings that are detrimental to their intended use, or that they would be a detriment to. E.g. a dyer's shop smells horrible, so is usually not placed in a residential area. Similarly, taverns and restaurants are loud, so residents don't want to live on top of them, but need customers, so need to be near residential areas.
  • Some countries have zoning laws that also influence building placement. Usually these are a more formalized way of anticipating what kinds of buildings may be detrimental to each other, or what resources are unique to the area (like, high-quality soil is for fields, not for building parking lots on).
  • Buildings are for inhabitants, and their personal style and preferences are reflected in them. E.g. if a population is poor, they're much more likely to share ground (skyscrapers, apartment buildings), if they're more well off, they may get condominioms, if they're rich, they get a standalone villa. If certain groups do not like other groups, they will be less likely to co-habitate. If there is an affinity between certain groups, they may move into similar areas.

Apply them to your topography

Once you have these constraints, you can try to build an algorithm around it. E.g. generate your topography and distribute needed resources around the map (maybe keeping an eye on placing small deposits of the most important resources in the starting area, then larger deposits farther away and from each other). This is where your game's needs and mechanics come into play, of course, but you'll likely also add a random element.

Then build businesses (and their residential buildings) near those resources that use them. E.g. a quarry next to a large mountain. Then add infrastructure needed by them. E.g. a trading post with post office and tavern where they can do business and sell their product, a smithy to provide tools etc.

To decide what goes where, split the map into tiles where you calculate a number for each tile how desirable it is for a certain purpose, using a weighting function. Put the buildings in the most desirable tiles for that kind of building. Add rules like "one trading post can handle 50 businesses or 100 homes", which increase the likelihood of adding another trading post if a city reaches a certain size.

Once you have this, you should get some fairly decent maps. If you notice that maps all end up as unnatural shapes, add penalties to your weighting functions for those shapes, like "if my street ends up right next to another street, -100 desirability", or "if my street crosses itself, -100 desirability" etc. You can always add in a random element to allow this for a more quirky feel, or add other mechanics like "if a crossing has more than N buildings connected to its roads, turn it into a roundabout".

You can even use these constraints to give different maps a different feel, like make a certain country have more mountains in its topography, or have a certain culture build more winding roads, and another prefer straight roads etc. All just by modifying one of your weighting functions.

Simplify

Of course, this approach is too complex for games that aren't trade simulations, but work this out anyway, and see which kinds of buildings make sense for your game, and eliminate the unneeded ones. Then come up with simplified rules like "place cities near a river, a mountain or good soil. 1 building per 100 resources, businesses based on resource type, 10 residential buildings for each full set of food/crafting resource ... or just "1m of river/1sqm of soil can support 10 residential buildings ... whatever makes sense for a game. Still, once you know how much area you have (e.g. no buildings on steep mountain sides), and how many buildings the area can support, just place sets of buildings in that area until it is full (like, 1 business building, 10 residential, 3 infrastructure, or whatever) and connect them with roads.

\$\endgroup\$
  • 1
    \$\begingroup\$ This answer describes the bottom-up approach to procedural generation. It compliments very well with my answer which describes an example of the opposite top-down approach. Both approaches have advantages and disadvantages. The advantage of bottom-up is that you have a very good control over what objects you have in your generated city. The disadvantage is that you need a much more complex and fragile ruleset in order to generate a town which looks realistic as a whole. \$\endgroup\$ – Philipp Aug 3 '18 at 15:42
  • \$\begingroup\$ Yeah. Also depends a lot on the type of game and desired city layout. Bottom-up works better for smaller, medieval-style, naturally-grown cities, while top-down works better for US-style cities and metropolises. Similarly, if you have a game that involves functional buildings and resource management, bottom-up may give you finer control, whereas top-down is the best optimization for cities in racing games etc. where you really don't care about buildings' function. \$\endgroup\$ – uliwitness Aug 3 '18 at 16:17
  • \$\begingroup\$ Thanks for the answer. Have you looked into that? I have. Well, sort of (I couldn't think of many "real-life rules"). But this is quite an eye opener compared to my previous attempts: I was failing to recognize resources that I might not draw (ie: there's a forest to the east... regardless of whether I draw it or not). \$\endgroup\$ – Roflo Aug 3 '18 at 16:44

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.