Introduction

In this article I shall present two ways of creating a random town I thought about while writing UR. Bear in mind, however, that there are other splendid town generation algorithms possible, some of them bearing far better results than the ones described here.

Algorithm 1: Division into cells

Let's start with an algorithm that I first thought of, but found the final results unsatisfactory.

The idea is to divide the map into square cells (in case of UR, there were 14x11 cells, 8x8 tiles each). Then, in each cell we generate a building (or not).
The good side of the algorithm is that we can define exactly how many cells need to be populated with a building, resulting in an exact number of buildings in the generated town. The size and shape of the buildings may vary, of course.

On the other hand, the generated towns look somewhat artificial due to the forced geometry.
There is also a similar method, where instead of identical rectangular cells we've a little bit more randomness. The map area can be divided using a BSP tree, where buildings are placed on its leaves and roads on its branches. I won't comment further on this method since I'm not totally familiar with its details. For further information, read the article about BSP dungeons by Jice.

Algorithm 2: Total randomness

The other algorithm gives more satisfactory results. For each building, a random point on the map is chosen and all potential tiles that potentially will be occupied by the building must be checked whether they are accupied. If they are empty, the building is placed. If they intersect another structure, be it a building or anything else, a new random point is chosen. This is repeated until no new buildings can be placed (specified building limit reached or no room left for more).

Each building needs at least one door, and possibly some windows. Their placement is fairly simple for rectangular buildings: just pick a random point on the building's outer wall and convert it to a door or window.

The good side of the algorithm is its randomness. The generated towns building placement is completely irregular and thus more fun to explore. Its downside is the unpredictable number of buildings. It can be limited, but it even may result impossible to reach that limit if you wish to create a densely populated settlement. On my 112x90 map, between 50 and 60 buildings are usually generated (that is, when no other features are placed, further limiting the number of buildings).

Road generation

What would a town be without a road! Generating one is a very simple task as well. The catch is that roads may turn. To correctly implement this feature, I parted from a simple assumption: if two roads going into the town, say, from the north and from the east, need to meet exactly in the same point, it is necessary to start generating them from that point and not from the map's edges towards the centre.

The other problem with the typical approach to making roads (and rivers and whatever) is that they are normally drawn line by line or column by column. In other words, one "for" loop progresses through the x coordinate and at each step another "for" draws a vertical/horizontal line. Or, said in simpler words, it's drawn with a line brush.
I chose the following: instead of using two "for" loops, one for vertical and one for horizontal displacement, I only used one. At each step made by the loop, a square brush is used to draw the road section. This way, the roads look more convincing.

Comment

Note that even after adding extra features like trees, perimeter walls, a coastline or whatever, the towns still have a tendency to look a little bit uniform. This is due to the shape of the generated buildings: they are all rectangular! There is a way of dealing with this as well, although it's a little bit more complicated. It's covered in the article Generation of random buildings with more detail.