This post explains how I coded a city map generator for a project that never made it to full production. Some of the techniques involved are similar to the Fantasy Map Generator I worked on, but this project was much more in-depth in terms of how regions of cells relate to each other and their final contents.

My main ambition with this project was to be able to generate a city map with sensible zoning, navigation and plot generation for housing etc.

Choosing a graph structure

For the basic data structure I tried two different graph formats. The first attempt used a warped quad grid, as seen in games like Townscaper. There is a good explainer of the process for generating such grids here.

This format has the major advantage of every graph-cell being a quad and therefore always having 4 neighbours. This in turn leads to the possibility of generating objects within the cells that can make use of connective bitmasked tiling - a method of composing graphical tiles out of parts based on connections to their neighbours. you see this approach used frequently in 2d tile based games to allow for walls and paths to maintain sensible visual connections form one tile to the next (here is a good explainer)

Obviously knowing that each cell can have four walls helps enormously if you want to create continuous building structures (see Townscaper).

The image below shows how I split this warped quad grid into different city 'districts' (biomes). I also assign a margin of cells at the edges to be either 'ocean' or 'mountain' in order to give the city some definable edges.

These districts include a river which is defined more deliberately than the other districts (as it has to connect to the ocean and span across the majority of the map. 

After the districts have been defined I link the cells within them together to create "blocks" that function a like interconnected apartment complexes etc. This 'joing up' pass was in preparation for a bitmasked style 3d or sprite based decorating phase.

Pathing

In a similar approach to my Fantasy Map Generator, I place a loose grid of Key Road destinations (the white squares) across the graph and then connect those points with A* pathfinding. I remove some locations at random to make the result less grid-like .The roads follow cell edges and are naturally perturbed even if the underlying structure has no inbuilt penalties. I did however add a light amount of 2d noise to the pathfinding nodes in order to make the roads a bit more variable.

At this point that I became dissatisfied with the townscaper map approach. Unless the graph was very relaxed during generation, the cells could end up arranged with very acute edges (see some of the roads on the left of the map as an example). The other limitation of the approach is that all the cells remain roughly the same size (even more so if the graph is more relaxed), so all the basic cell plots are similar in size. 

These limitations can be overcome with more work on relaxing the grid and merging cells, but I decided to try my old favourite alternative. The Voronoi Graph.

Voronoi Approach

The graph generation process is broadly similar to the warped quad mesh, except in a voronoi graph the cells are not restricted to being quads and the resulting mesh is less regular. This leads to more variance in the cell shapes and sizes across the map.

By placing the seed voronoi cell points in different configurations I could also create different styles of emergent layout; gridded, radial etc.

Roads are calculated in the same way as before, but after pathing is finished I run a function to add margins along every cell edge that bordered a path. In the image above you can see an issue where the end of roads taper to a single point, this isn't too hard to fix, I just didn't get around to it!

Housing

To create housing plots I take each cell and bisect it a number of times. These divisions are set to split the cells evenly (to avoid making slivers of geometry). I repeat the process several times - based on the initial size of the cell and a lower limit for the number/size of child plots produced> This results in the creation of sub-plots and alley-ways within the original cell. 

After the plots and subplots are defined I perform a basic square packing routine to see how many buildings I can fit into the remaining plot. This has an element of randomness included to ensure a nice range of building sizes (green plots become gardens) and any plots that are too narrow are eliminated (shown in red int he image above)

Once the data structure is complete I render the map by placing building sprites and other decorations within the plots themselves. There are a range of rules to select the sprites based on biome/district type, frequency of building type, size of plot and proximity to other cell types etc. Each sprite is aligned to the plot direction and scaled to fit within. I then generate a network of meshes for the road networks and place the occasional lamppost at intersections. The results were pretty nice and certainly workable for any sort of medieval type city layout.

Finally, for fun I assigned some randomly generated names to the districts and add a bit of relevant typography.

I had to put this project on the back-burner due to financial constraints, but I'd love to return to it some day!