As stated in the last article, this time I'll be looking at what went into the MK I map generator for my eternally work-in-progress game, DeathDawn.
 
Specifically, I'll be looking at the implementation and evolution of the following components of the generator:

• City block placement. This is arguably the most important stage as it defines the overall layout of the city.
• Edge and node linking. A housekeeping stage that prepares the data structures for the road weighting stage.
• Road weighting. A city with roads which all have the same number of lanes isn't very realistic, so this stage uses an algorithm to determine the number of lanes each road should have.
• Road and building painting. With the city structure generated, all that's left is to translate it into the format used by the engine during actual gameplay.

City block placement

Choice of algorithm

If I wanted the city to look like a city, the choice of algorithm for laying out the city blocks is undoubtedly one of the most important choices to be made. At the time, I had several options available:

1. The previously-described algorithm used in maze game GAIO, where one large room is recursively split into smaller rooms along either the horizontal or vertical axis. Except in the case of DeathDawn the rooms would be buildings and the walls would be roads.
2. A solution borrowed from elsewhere, for example that used by Team Black Sheep's Robocup Rescue city generator. In the above-named example roads are placed onto the lines of an irregularly-spaced grid, then some roads are removed at random to enlarge the size of some city blocks, and then random offsets are applied to the node coordinates in order to add more bends and hide the fact that the roads are based around a rigid grid structure. All except the last step would be applicable for DeathDawn, due to the near impossibility of representing roads that don't run along the 4 cardinal directions.
3. An entirely new algorithm developed with DeathDawn in mind

In the end, the decision was made to develop a new algorithm. The GAIO algorithm was deemed inappropriate due to its tendency to generate one long road running from one edge of the city to another, making the output feel too artificial. The Black Sheep Robocup Rescue generator was also deemed inappropriate, since it relied too much on the random displacement of nodes (and thus support for diagonal roads) in order to generate the desired effect.
 
Other useful food for thought during this development process included Nikos A. Salingaros's keynote speech "Connecting the Fractal City", presented at the 5th Biennial of towns and town planners in Europe.

Implementation

I was essentially back at square one - how do I create a realistic looking city block structure? Some roads need to be long and straight, others need to be narrow and twisty. Some buildings need to be big, others need to be small. Some need to be regular, some need to be irregular.
 
Although I could try building a complex fractal-based generator, I decided to go with the simplest approach possible and build from there. Starting in the top-left corner of the map, the confusingly-named magic_road_algorithm() function would fill the map with city blocks (cblocks), laying them down one at a time next to each other. Each block would be rectangular in shape (for now, at least), and would be a random size (within certain limits). With a little tweaking, this algorithm worked surprisingly well.

Initial problems

Although the first version worked, it did suffer from problems. Mainly that everything had a habit of shrinking and shifting to the left as it went further down the map, and there were many instances of city blocks which are either too small or non-existent (i.e. two roads placed directly next to each other). When you take into account the fact that roads shown in figures 1 and 2 are single-lane roads, you can see how this could cause problems when the roads are widened by later stages of the generator.

Tweak #1 - cblock size selection

The first tweak was to the cblock size selection. In the initial code, the algorithm would scan the map to work out the largest cblock that could be placed, and then select a block that fits within that area (and also obeys the min/max block size). However this fails to take into account the requirements of the next block to be placed, and frequently results in situations where the next block is forced to be smaller than the minimum size. Due to the top-to-bottom, left-to-right scanning and filling of the map this results in the large number of thin yet tall blocks seen in figure 1, particularly along the right hand edge of the map.
 
By altering the algorithm to take into account the minimum size constraint of the next block (both in the X and Y axes), avoiding a split if the next block would be too small, the number of too-small blocks was reduced significantly.
 

Tweak #2 - Generate longer straight roads

The output of the first generator suffered from a problem where the average length of the vertical roads was higher than the average length of the horizontal roads. This is another artifact that's the result of the top-to-bottom, left-to-right scanning order. As you can see from figure 3, the uneven heights of blocks 2, 3 and 4 places width constraints on blocks 6 and 7. Unless those constraints are broken, the vertical road running between 2 and 3 (and 3 and 4) will stretch to the bottom of the map, and there will never be a horizontal road below block 3 that's wider than block 3. The only way to break the constraints is to make two adjacent blocks have their bottom edges in line with each other, like with blocks 7 and 4.
 
The problem with the original generator was that because the widths and heights of the blocks are both random, the chances of a situation like 7 and 4 occuring are relatively slim - only 1 in N, where N is the maximum block height.
 
A simple solution to this problem was discovered; a uniformity parameter was added to the function. This parameter gives the random chance of the new cblock having its bottom edge in line with the bottom edge of the block to the left. If the uniformity says not to place the two in line, then a random height will be chosen as usual. By tweaking this value (current generators use the value of 30%) a satisfactory result was produced, where the city appears to have an equal number/length of long horizontal and vertical roads.

Edge and node linking

Although the magic_road_algorithm() function creates a list of cblocks, and those cblocks are linked into the cbmap, the blocks don't have any direct way of enumerating their neighbours. And more importantly for the road weighting code, there are no edge or corner structures for the road code to manipulate.
 
The build_edges_and_nodes() function fixes this by using the cbmap to scan the area surrounding each cblock, creating edge structures between each pair of neighbouring blocks. The edge list is then used along with the cbmap again to work out what cblocks are at the end of each edge, to create and link the corner structures.
 
The end result is a fully interlinked network of cblocks, edges and corners, as seen in figures 5 and 6 from the preceding article. Remember to have a quick look back at that article if none of this is making any sense!

Road weighting

The edge structures are treated by the map generator as being individual segments of road. But a city that contains roads that are all the same width isn't very realistic, so a 'weighting' algorithm is used to decide how popular (and therefore how wide) each road should be. This algorithm (in the weight_road_algorithm() function) uses an idea borrowed from The Black Sheep's Robocup entry, whereby a number of simulated journeys through the city are made and statistics gathered for what the most popular roads are. These journeys are simulated using an A* algorithm to find the 'best' route between two random points in the city (i.e. two corner structs). By performing several thousand journeys and counting how many times each road is used, the most popular roads can be identified, and they can be upgraded to the widest width possible (for DeathDawn, this is 6 lanes). Other, lesser popular roads are given 4 lanes, while the majority are left with 2 lanes. Finally the least popular roads are downgraded to footpaths, to add some more variety to the city.

Implementation details

Like all A* implementations, the one used by the road weighting algorithm relies on a priority queue data structure to store all the partial paths and decide which to process next. In the case of the road weighting algorithm, the priority queue contains pointers to road_path structures:
 
typedef struct _road_path {
  int l;
  struct _road_path *next;
  corner *c;
  struct _road_path *lnext;
} road_path;

• The l member contains the current total length of the path. This is used as part of the priority queue sorting function to decide which road_path to expand next.
• The next member points to the road_path's predecessor along the travel route. A more logical name would probably be prev, but next is the name that's stuck.
• The c member points to the corner which this path stops at.
• The lnext member is used to manage a linked list of all the road_paths, to allow them all to be deleted at the end of each journey simulation. It has no bearing upon the A* algorithm itself.

At the start of each journey simulation, a single road_path is inserted into the priority queue. This has a route length of 0, a null next pointer, and points to the 'start' corner in the journey. Then, for each iteration of the A* algorithm, the head element is removed from the priority queue, and the weight_road_add() function is called to expand the partial path in every possible direction (i.e. along the four edges pointed to by the edges member of the corner that the path links to). Once a road_path is generated which lies ontop of the 'end' corner, the process stops.
 
But how does this help us find the quickest route?
 
Simple: The next pointer of each new road_path is made to point towards the parent road_path. This means that, for the road_path which lies ontop of the 'end' corner, if you followed the next pointers you would travel along the quickest route back to the 'start' corner. With a little bit of extra logic to translate corner pairs into edges, you can therefore work out which edges are used in the journey and increase their use counts.
 
One important optimisation applied to the basic algorithm is that each corner is only processed once. This is implemented by the use of the visited flag of the corner structure. The flag is set the first time a road_path is generated for that corner, and any subsequent attempts to generate a path for that corner will fail. This optimisation is permissible because although there may be multiple paths towards each corner, we are only interested in the best (i.e. shortest) path to each corner - and due to the nature of A* the best path will always¹ be the first one generated. Without this optimisation the number of generated partial paths has the potential to increase exponentially, increasing both memory costs and execution time of the algorithm (and when you've got to perform several thousand route simulations to generate the road widths, execution time becomes very important). With the optimisation in place, you can be guaranteed to generate no more road_paths than there are corners. Care is taken to make sure the visited flag is cleared after each journey simulation - this is done in the loop that runs through the lnext pointer chain and deletes each path element.
 
One important thing to remember if you're implementing your own A* algorithm is that unless you implement a similar system to avoid generating redundant or looping paths, the algorithm may not terminate if there is no possible path between the two points. Well, it'll terminate when it runs out of memory, but that could easily take an unacceptably long time, or result in other bits of code failing.
 
Once the ten thousand or so simulated journeys have been made and the road use counts tallied, an array is produced containing pointers to each road edge. This array is then sorted in order of road popularity, from most popular to least. The first 10% of the array entries are upgraded to 6-lane roads; the next 20% to 4-lane, the next 60% to 2-lane, and the remaining 10% are downgraded to 1-lane footpaths.
 
¹ Actually this is probably false - particularly once the following algorithm tweaks are taken into account - but at the very least the first path generated for each corner is good enough as far as the road weighting algorithm is concerned.

Tweaking and improvements

Initially the evaluation function used by the A* algorithm to find the 'best' route was concerned with only finding the shortest route. However during testing this was seen to have two problems: Firstly the most popular roads were all in the city centre, which resulted in the widest roads being placed there in a big cluster. This is somewhat unrealistic since the city centre, due to its popularity, is likely to be the part of the city with the least space available for wide roads to be placed. The second problem observed was that the wider roads tended to zig-zag quite a bit, which is again rather unrealistic since wide roads are meant to simulate motorways, which are generally wide and straight to allow high speeds and reduced travel time.
 
Fixing these problems required some quite simple tweaks to the code: When adding a new section to the route path, the path length is increased by 1 if it runs through the center of the map. The path length is also increased by 1 if it involves turning a corner. Since the A* algorithm aims to find the route with the lowest distance travelled, these changes successfully discouraged the code from generating wide roads in the city center, and significantly reduced the number of twists and turns in wide roads (although there are still various problems left to fix with wide roads).
 
Later on, beyond the MK 1 city generator, a problem was also identified where wide roads were being placed next to small city blocks - in fact, the roads were so wide that they were taking over the entire surface of the block (or more). Despite choosing a minimum cblock size that should avoid this, this situation is still possible due to the city block placement code being unable to guarantee that overly-small blocks won't be generated. To counter this, the edge creation function identifies when the edge is next to a too-small cblock and sets a flag in the edge (actually just changing its type it to SURFTYPE_PATH). Then the road weighting algorithm detects when a SURFTYPE_PATH edge is being inserted as part of the route, and adds a penalty of 2 to the route length, to discourage use of such paths and thus reduce the chances of wide roads being placed there.
 
Another post-MK 1 addition was a post-processing stage. Once the road widths have been calculated, any roads which overlap the map edge are forcibly reduced to paths, and any roads which are too wide for the cblock they are next to will be reduced in width until they no longer overlap the center of the cblock (This is in addition to the much gentler tweak where 2 is added to path lengths). Also it was observed that maps frequently contained unrealistically short sections of wide road (often only one edge long), so to combat this another processing step was added where any wide roads that are one edge long will be reduced in width.

Road and building painting

Road and building painting in the MK 1 generator was very simple. Buildings were just large rectangular structures placed inside cblocks (preferably avodiing placing them ontop of roads, although that was often not the case), and roads were painted using a semi-intelligent algorithm designed to correctly place road markings (although it also failed rather poorly).
 
The only noteworthy feature of the MK 1 road and building painting was the use of the canvas system - although I've deliberately glossed over the structure of the final map representation, it's based around a simple compression system that doesn't lend itself well to modification. As a work around the canvas system was introduced, which allows sections of the map to be extracted in an uncompressed form, manipulated by the road/building painting code (including functions for rotating the canvas in 90 degree increments), and then inserted back into the map in its original position. Although the current implementation results in some redundant data being left behind in the compressed map, the canvas system has greatly simplified the task of generating the world.

Next time...

Next time I'll be taking a look at the stages added in the MK 2 generator, and any improvements made to existing stages which haven't been discussed above. In particular I'll go into detail about the method used to paint the road navigation flags, and into more detail about how the road and building painting works using its system of surface and building definitions.