After writing my first article about random map generators, I said I was going to write a city generator. Well now I have, and I'm here to tell you about it over the course of the next few Building the Dream articles.

Blow your own trumpet much?

Although this article could just be dismissed as me blowing my own trumpet, I'm hoping that it will serve a somewhat more useful purpose. Before, during, and after working on the map generator I've searched the Internet for examples of similar generators and failed to find any. Sure, there are odd bits and pieces - descriptions of simpler generators that have given me ideas on some techniques to use, or screenshots of sexy work-in-progress realtime generators, but no actual algorithms or code samples from generators that come close to the required complexity of my generator.
 
So hopefully this article will become a useful reference point for anyone else wanting to undertake the task of writing a city generator, whether they're targeting a grid-based world representation like mine or a vector-based one.
 
Apart from discussing the algorithms used in the generator (and why they're used) I'll also talk about the data structures that are used - so even if you're not interested in random map generators you should be able to find plenty of examples of uses for the data structures covered in the first Building the Dream article, as requested quite some time ago.
 

Why random?

This is the first question I asked myself - and the first question you should ask yourself if you're planning a random map generator (or any other kind of procedural content, really).

For me, the answer was fairly simple. DeathDawn development had reached the limits of what the diminutive test map could offer. If I wanted to continue working, I had to create a new, full-size map for use in the game. I could either create the map by hand (after first writing a map editor), or get a random map generator to create it for me.
 
Although writing a map editor would probably take less time and effort than writing a map generator, I decided to go down the generator route. This is because I've tried creating a city by hand before, for GTA 1, and know that it's a lot of hard work. I'd be constantly scrutinising the map, wondering if two adjacent buildings are too similar to each other, or whether the road layout of the map feels right, or whether there's too much or too little detail in a certain area. And every time I need a new unique building for a mission I'd have to go back and rip an existing generic building out - potentially changing the layout of large areas of the map in order to make it fit correctly. So although writing an editor would be quick and easy, creating the maps would likely be not.
 
However a map generator, although it would take a certain amount of time and effort to get working right, could potentially spawn millions of detailed maps just at the click of a button, with minimal effort on my part to feed the generator with input parameters. This would be particularly useful since at the time I started I also had no idea exactly how many maps I wanted the game to have.
 
As an added bonus, writing a random map generator would also be a hell of a lot more interesting than a boring old level editor.

The goal

The goal of the map generator is to create city maps for DeathDawn. But how big do they need to be, and what format should they be in?
 
In the interests of keeping things simple and not reinventing the wheel, the DeathDawn map structure is based around that of GTA 1. GTA 1 was capable of providing large cities (about 1km square) to the player, using under 500K of storage for the map itself. Each city consisted of a set of cubes arranged in a 256x256x6 grid. In real-world terms the length of the side of each cube is around 4m (or at least that's the length I've based DeathDawn around). The cubes were fairly limited in what they could do - you could specify the textures of the 5 visible sides, and the slope of the top surface - but that's about it as far as architectural details go. In addition to the visible features of the map there were also certain invisible features - such as the content type of the block (solid, air, or water), and how the AI should behave (whether it's pavement and should have pedestrians walking on it, or whether it's road and should have cars drive along it - and in which direction). Uncompressed this data could easily be 6 or more megabytes in size, but by relying on the fact that most blocks are identical, and many vertical stacks of blocks are identical, the size can easily be reduced to under 500K, leaving much more space for textures and sound effects.
 
Although DeathDawn's map format is slightly more advanced than that of GTA 1, the goals are pretty much the same - for the map generator to produce a map typically 256x256 block-stacks in size, with as much building detail as possible, and with the right AI flags to allow for pedestrians and cars to spawn and find their way around the map. The generator should also be capable of producing any secondary data needed - such as the locations of traffic lights, train tracks, and the territories of the different facitons. It should also be able to add specific buildings to the map at the demand of the mission script, so that missions can use unique buildings if they want.

Evolutionary development

The map generator has gone through roughly three distinct stages of development. The first stage (the MK 1 generator) was capable of placing roads and buildings, as well as splitting the map into different zones (The zone information is used to dictate which faction owns the territory, as well as provide place names for the player as he drives around). But the buildings were just simple textured boxes, and the roads were buggy - apart from visual problems (bad road markings at intersections) there were also situations where the navigation flags the AI uses had been placed wrong, resulting in cars driving off the road and onto the pavement or into walls. The generator was also severely limited, with no support for extra city features like hills, bridges, train tracks, or traffic lights. There was also no system in place to allow for mission-specific buildings to be added.
 
The MK 2 generator was designed as a partial restructuring, partial rewrite of the MK 1 generator, in order to solve all of the major bugs as well as provide scope for the addition of new features - such as hills, bridges, train tracks, and the mission buildings. Although the MK 2 generator managed to fulfil most of these goals, several design flaws became apparent during its implementation, the most important of which was that there was no way of guaranteeing that the mission buildings that were requested actually made it into the map.
 
And so the MK 3 generator was devised - a reordering of the stages the MK 2 generator goes through, in order to ensure as best as possible that the mission buildings will actually be placed. Plans are also being made to improve the MK 3 generator further, in particular to improve the level of detail and placement of regular buildings.
 
Note that the DeathDawn source code currently available on my site contains the source for the MK 2 version of the generator; however by the time this set of map generator articles is complete I'm planning on having the latest version available for your viewing (dis)pleasure.

Overview

The generator, as it currently stands, performs the following operations, in the order detailed below. Each article will be covering one or more of the stages.

1. Zoning #1. This stage splits the empty map into zones, and assigns each zone a style, dependent upon which factions have been chosen to inhabit the map. The size of each zone is determined based upon how many mission buildings must be spawned there (and how large they are), in an attempt to ensure that enough space is available when it comes to placing them.
2. City block placement. This fills the map with a series of rectangles, in a grid-like pattern. Each rectangle will later contain a building, and the edges of the rectangles will become roads. The zone location data that was generated in the first stage is used to apply different road and building styles to each city block.
3. Edge and node linking. This doesn't add any new features to the map; it's just a housekeeping stage to correctly link together all the structures created by the city block stage.
4. Road weighting. This stage decides how wide each road should be, by simulating a large number of trips through the city using an algorithm similar to the one a real-world computer route planner would use. After the trips have been simulated, the most-used roads will be chosen to be the widest roads (i.e. motorways), and the least-used will be downgraded to footpaths.
5. Zoning #2. This stage examines the map to find the true size and shape of each zone (the earlier zoning stage just gives estimated bounds). It also assigns names to each zone, which will be seen by the player as he drives around the city.
6. Mission building placement. Using the city block and zone information generated in the previous stages, this stage searches for suitable locations to place the mission script buildings that have been demanded by the mission script.
7. Layer splitting. Added in the MK 2 generator, layers allow the generator to support hills, by storing the data for different altitudes in different structures. The current layer splitting code merely splits the map from one layer into two, by randomly placing hills throughout the map and moving all the buildings that lie inside a hill up onto the second layer. Eventually the layering code may be expanded to allow for more complex structures (notably bridges), or it may be discarded altogether in favour of a more streamlined approach.
8. Road prepainting. The final map structure, as used by the game, is wholly incompatible with the data structures used by the generator. The map painting (and pre-painting) stages are therefore concerned with translating the map generator data into the final map data structure. In the case of road pre-painting, this involves marking into a temporary 2D array the location of each road.
9. Road and building painting. This is a fairly complex stage. Not only does it paint each building into the main 3D map structure, but it also paints the surrounding road and ground blocks. In particular it contains code for placing the correct road textures on the surface of each block, as well as the navigation flags used by the AI.
10. Hill side painting. A more correct name for this stage may be 'cliff face painting'; it involves a brute-force examination of the map to look for gaps in the joins between the upper and lower layers of the map, and places wall textures at the appropriate places to ensure that the player can't see through to the void underneath the map.
11. Traffic light placement. Now that all the roads and buildings have been painted, each road intersection is examined to see if it is suitable for hosting a set of traffic lights. Although this stage could probably be performed before the road and building painting, it's easier to do it after, as it provides a much more robust method of verifying that the traffic lights won't be placed incorrectly.
12. Train track placement. The map generator is capable of generating elevated train tracks for inner-city and inter-city rail travel. Similar to the hill side and traffic light placement code, a brute-force approach is used to examine the finished map, to ensure that the train track weaves around buildings instead of ploughing straight through them.

In detail

For this first article about the map generator, I'm going to be talking solely about the data structures that are used. Understanding the data structures is vital to understanding the flow of the generator as a whole. Later articles will go into more detail about each stage of the map generation.
 
If you're put off by all these wordy descriptions, don't worry, because there's a few diagrams at the end showing how everything fits together.

The layer structure

First off there is the layer structure. This was introduced in the MK 2 generator as a way of tieing together various variables and structures that the generator uses.

typedef struct _layer {
  rect r;
  int z;
  gdll *cblocks;
  cblock **cbmap;
  fbll *corners;
  int *surfmap;
} layer;

• The r member of the structure, a 'rect', contains the minimum and maximum X and Y bounds of the layer, measured in blocks. Currently this is just set to the bounds of the map, but in the future it may be used to limit development to certain areas (e.g. if there is water at the edge of the map the layer would be restricted to just the island of land in the middle).
• The z member gives the layer its height above ground, measured in blocks.
• The cblocks member is a pointer to a gdll - a linked list structure that I often use in my code to make handling linked lists slightly easier. The linked list will contain a list of all the city blocks that are contained in the layer.
• The cbmap member points to a 2D array of pointers to cblocks, allowing rapid lookup of which city block falls on which map block. The cblocks pointed to by the cbmap are the same cblocks that are contained in the gdll list.
• The corners member is another of my linked list structures, but a different type - a frame-based linked list, which is basically just a linked list of arrays. A frame-based linked list allows you to quickly and easily look up the Nth element of the list, at the cost of much slower insertion/removal of items in the middle of the list. In the case of the map generator, this speed trade off was deemed worthwhile to ensure the speedy operation of the road weighting algorithm. As the name suggests, the data contained in the corners linked list is a list of all the corners of the city blocks; or more correctly, a list of all the end points of the edges which join city blocks. More about this later.
• The surfmap member is similar to the cbmap, in that it points to a 2D array. But instead of indicating which city block each location belongs to, it instead indicates which surface type (road, pavement, grass, water, etc.) each location is. This is mainly used by the road painting code to ensure that roads aren't painted where they shouldn't be. Although the final map structure contains similar data, it works out easier for the map generator to store it in a temporary array as well.

The cblock structure

Each cblock represents a city block; i.e. a plot of land with one or more buildings inside it, and surrounded by pavements and roads. Currently only one building is placed in each cblock, but this will likely change with the MK 3+ generator - take a look at figure 4 and you'll see how much empty space there currently is inside each city block.
 
typedef struct _cblock {
  rect r;
  rect br;
  gdll *neighbours;
  gdll_item *i;
  zonedef *z;
  struct _layer *l;
  builddef *b;
  int msi;
} cblock;

• The r member provides the bounding box of the block. This box stretches from the middle lane of the road one one side to the middle lane of the road on the other side. This represents the maximal area that the painting stages will paint grass or pavement into, to fill in the gaps between the building and the road.
• The br is another bounding box, but this time provides the bounding box of the building that sits inside the block. This is computed by looking at the widths of the roads that surround the block.
• neighbours is a linked list of edges that surround the block. edge structures are created whenever two cblocks touch, and are used to generate the roads and paths that run through the city.
• z points to a zonedef - a structure that dictates which building, pavement and road styles to use when painting the cblock. The z field is also used by the 'Zoning #2' stage to calculate the true bounds of each of the named map zones and faction territories.
• l points to the layer that the city block belongs to. During map generation certain information (most notably the Z coordinate) of the city block is needed, so a reference back to the parent layer is the easiest way of providing that information.
• b points to a builddef, i.e. a building definition. It indicates the type of building that's been selected to spawn at the location. Currently this field is only used for the mission buildings; for all other city blocks a random building is selected at painting time, using the list given in the zonedef.
• If a mission building is being used, the msi field will be set to the index in the master mission building list. If no mission building is being placed in this block then the index will be -1. The msi field is crucial to allow the building location to be fed back to the mission script.

Edges

The edge structure is used to link neighbouring cblocks together, and dictates the locations of the roads and paths that run through the city.
 
typedef struct _edge {
  gdll_item *a,*b;
  corner *c,*d;
  int type;
  int weight;
  short clip,dlip;
} edge;

• a and b are two gdll_item pointers; gdll_items are used to reference individual entries in gdll lists. There are two of them because the edge is shared between two cblocks, each of which has a different list of neighbouring edges.
• c and d are two corner pointers, dictating the two end points of the edge.
• type is the type of edge - road, pavement, cliff, etc.
• weight has a dual meaning. During the road weighting stage it's a counter of how many times the edge has been used, and after the stage it's the number of lanes in the road (assuming it is a road).
• clip and dlip are the distances from c and d at which the straight part of the road exists; i.e. it's how large any crossroads or T-junctions are. This information is mostly redundant with information stored in the corners themselves, but for the moment it stays where it is. shorts are used to try and keep memory usage down, although in reality there are still many other memory optimisations I could apply if I wanted.

Note that an edge can cross from one layer into another, e.g. to create the slope of a hillside or bridge. This is why there's no layer pointer in the edge, and each layer doesn't have a list of edges.

Corners

As their names suggest, corners are the places where edges meet.
 
typedef struct {
  struct _edge *edges[4];
  short x,y;
  int visited;
  short w,h;
  struct _layer *l;
  int type;
} corner;

• edges is a small array listing the edges that the corner is connected to. Since edges only run horizontally or vertically, there's no chance of there being more than 4 edges connected to a specific corner.
• x and y are the coordinates of the corner within the layer.
• visited is a flag used by the road weighting algorithm.
• w and h are the dimensions of the corner, in terms of the total number of lanes (map blocks).
• l is a reference to the layer that this corner belongs to.
• surftype is the surface type of the corner (road, pavement, etc.) This could be calculated just by looking at the surface types of the connected edges, but storing it locally helps keep things simple.

What?

If all those data structures are confusing you, then perhaps these diagrams will help. Figure 5 shows how the different data structures fit together to represent different parts of the city. Figure 6 shows the actual relationships between the different structures, from the datas point of view (i.e. what pointers point to what).

Next time...

The next article, due shortly after judgement day, will take a look at what constituted the MK 1 map generator - i.e. the city block placement, edge and node linking, and road weighting stages of the generator. If there's space I may also describe the algorithm used to paint the road navigation flags for the intersections.