Hex-Tile Procedural City Generation

Introduction

I am presenting a different take on Nate Fox’s 2010 GDC talk “Building an Open-World Game Without Hiring an Army”. In his talk Nate Fox hinted at a city generation system that powered most of the map in Infamous. The hints were things like: using hex tiles, giving edges types, and making a small amount of prefabricated objects that can look different when populating a whole city.

Data

This method is just one way you could generate a unique city based on hex tiles. What makes it unique is its use of height maps and a multi-staged placement of terrain and objects.

This method was made in unity and coded in C#, and requires a tile script, map script, and a road script. The data the tile script holds is: its tile’s position in the map, references to all its neighbor tiles, and all of its edge types (so for a hex, 6 edge types; conversely a square would have 4 edge types). The data the map script holds is: the width and height of the map, a 2D-array of hex tile objects, two 2D-arrays that hold integers, vector’s (or List’s in Unity) for building and park objects, and references to all road objects (in Unity for instantiation). The road script’s data is it’s: height, “going to” and “coming from” directions, hex tile that it’s attached to, and its ramp status (e.g. is it a ramp, ramp up or ramp down).

Edge types are used on the hex tiles to specify what each triangle (or edge) is. Examples of edge types in my implementation are: none, building, road, and park. You could use an integers to keep track of the edge types, but for readabilities sake I used an enum.

The two 2D-arrays held by the map are used for height maps. The first is used for an initial height map that the hills, building, and parks use for placement. The next 2D-array initializes its data with the first 2D-array, and is used and changed by the roads.

When building the objects that will be placed in the building and parks lists you should orient and place the objects into a single triangle on the hex tile. You should use the same triangle for all of your objects, in my implementation I used the south-east triangle. The reason to do this is so that you can rotate the object to whatever edge (or triangle) in the hex tile easily, and not have to have special placement cases for every object. An example of this is shown in Figure 1.

Figure 1 The circles are building that are fitted to the Southeast triangle. If the pivot for rotation is at the tip of the triangle pointing inward towards the hexagon, then rotating the building configuration will be easy.

In this implementation you need at least four types of road objects: straight, ramp straight, turn left, and ramp turn left. In my implementation I rotated and scaled each of these roads to get their up, down, and right counterparts. I would recommend using different objects instead because my way took me hours to get the scales and orientations for all the different road cases to look right.

Terrain

For the first step, I allocate all the memory for the hex tile map and height maps. I then create each tile and place it within the map and game world. After that I initialize all the data in the tiles; first setting all the edge types to none and then getting and setting the tiles neighbors. Lastly, I generate the initial height map using Perlin Noise.

In the second step, I start placing the terrain on the map. I begin by looping through the map, then for each map position creating new hex tiles based on the initial height map. Initially, I created multiple hex tiles that would stack up from zero to the height in the height map, and then store the top hex tile into the map. I realized that this was wasteful because I was creating more objects than what was needed. So to remedy this, instead of creating multiple middle hex tiles in a stack, I made one hex tile, which was scaled in the up direction, to fit between the bottom hex tile and the top. As an example, say that the height in the height map was three, I would then create a hex tile that was scaled up by two and place it on top of the initial hex tile. After that I would create a regular hex tile and place it on top of the scaled hex tile; I would then place the top most hex tile back into the map. The result of this optimization made it so I could have bigger height map values along with larger map widths and heights. Then after all the new hex tiles are made I loop through the hex tile map again, and re-assign each hex tiles new neighbors.

Finally, I loop through the initial height map and see if that positions height is less than or equal to the water threshold. I calculate the water threshold beforehand by finding the max height in the height map and dividing it by three. If the height at that position in the height map is less than or equal to the threshold, I find its corresponding hex tile and set all of it edge types to parks and color it blue. This gives the effect of lakes forming in between the hills.

Roads

In the third step, I start placing all the roads. This was the hardest step in my opinion. I think the difficulty came from trying to correctly match and orient roads, and dealing with the height changes that the roads had to adhere to.

To clarify, a road is an object that starts at one edge of a hex tile and ends on a different edge on the same hex tile (e.g. a road starting from the west edge and ending on the east edge). In my implementation, I put restraints on what type of roads could appear for two reasons: one, so I didn’t have to make a lot of road meshes, and two, so that the amount of checks and logic I had to do to place roads was much smaller. So my restraints were that there were no sharp turns. For example, if a road was “coming from” the West edge (in the hex tile), it had three “going to” edge choices to pick from: East, Northeast, and Southeast. An example can be seen in Figure 2.

Figure 2 “Coming From” is the red arrow and “Going To” is the blue arrow,the black arrows are other possible “Going To” directions.

I begin the third step by defining a max road count, which tells the placing road function to stop once it’s placed more than the max roads. Max can be any number you want, but if it’s too high you will probably have a map full of roads and if it’s too low you’ll barely see any roads at all. To combat this, I came up with a decent equation, Equation 1, which gave a nice dispersal of roads for any map size. Max = (Map_Width / 2) * (Map_Height / 2) (1)

The next step is to pick a random starting place for the roads to come from. In my implementation, I choose from the outer bounds of the map so that a road doesn’t randomly start in the middle of the map. I also pick a start direction which sets the first road’s and hex tile’s “coming from” direction. Next, I allocate a road object vector (or List in Unity), this is used later at the end of making one full road set.

Now that the initial properties of the full road set are set up, I go into a road placing loop. I start by checking if the current hex tile that the road is on is valid, if it isn’t I leave the road placing loop. But if it is valid, the next thing I do is get a “going to” direction that is compatible with the current roads “coming from” direction. I choose the “going to” direction by using Rand() and picking from a valid direction list that’s generated from the “coming from” direction. Once I have the “coming from” and “going to” directions for a hex tile, I then set those corresponding edges on the hex tile to road edge types. For example, if the “coming from” direction is Northeast and the “going to” direction is Southwest, then the Northeast and Southwest edges are set to road edge types on the hex tile. After that, I get the next tile by following the current tiles “going to” direction.

I then get the heights (from the second height map) for the current tile and the next tile. I do this because if the next tile is greater in height than the current tile then I want the current tiles road to be a ramp up; vice versa if the next height is less that the current then the current road should be a ramp down.

So after the all road properties are figured out, it is then time to place it. I use the current tiles height to calculate an offset for placing the road. I then save that height value and add one to the second height map at the current tiles location within it. I do this because if any other roads come to that same tile they’ll be placed over the last road planted there as a result of the offset. After that I create the road object with all of its specifications and I initialize all of its data which includes setting its: height, hex tile it’s attached to, going to and coming from directions, and ramp status. After creating the road I add it to the vector of roads I created at the beginning of the place roads loop and add one to the road count.

Eventually a road will hit the edge of the map, which will terminate the road placing loop. At this point the road object vector will be filled with all the roads that were just created. So the next step is to normalize that full road set. By normalize, I mean making the road set so that every road within it has at most a one height difference with its neighbors. This was a constraint in my implementation because my road meshes only ramped up by one. But in the end, I think it was a strength because drastic changes in roads heights would’ve made for really weird and unconvincing looking roads. After the road has been normalized, I loop back to the beginning of the place road function. This is where I check to see if the road count is greater than the max roads. If it isn’t then I go through the placing roads loop again and make a whole new road object list. But if it is greater, then I have placed enough roads and I am done with this city generation step.

Buildings and Parks

The last step is to place the actual city which consists of the building and parks. This was probably the easiest and most gratifying part of the project.

I start off by doing a “place building” pass on the map. So I loop through the map, doing two checks. The first being if the hex tile is free, meaning that all of the edge types are none, and the second being a check for how many parks and roads are around that hex tile. If the hex tile is free, I leave that tile alone and move on. If the hex tile has a certain amount of parks (meaning lakes) or roads around it, it will then place buildings on all the available edges on that hex tile. Once it places the building on its edges it will then set those corresponding edge types in the hex tile to buildings.

Finally, I do a “place parks” pass on the map. The place parks pass also has two checks, but in a different orientation. I loop through the map again checking for free hex tiles. If the check passes then I check the hex tiles around the current tile to see how many roads, building, or parks are near it. In my implementation, if there is at least two building or parks around the current tile it will then place a park object and set all the edge types in the current tile to parks. Although data wise these parks have no difference to the terrain parks, aesthetics wise they differ by being fountains, trees, or gardens.

The “place parks” pass marks the end of the city generation. In my implementation, these constraints on the buildings and parks give the world map really interesting qualities. It makes it so the buildings become denser where there are a lot of roads, just like cities, and become sparser when there is just a singular road. The parks tend to give the small towns, with small amounts of building, more flavor because there’s more open spaces around them so there can be more parks. As opposed to the big cities that tend to only have some parks around the city outskirts.

Conclusion

I encourage you to look into topics such as Perlin noise for height maps, using Voronoi regions for mountain like areas, or using simplex noise to create caverns beneath your generated city.

References

Nate Fox. 2010. Building an Open-World Game Without Hiring an Army

Sucker Punch Productions. https://www.suckerpunch.com/

www.gdcvault.com%2Fplay%2F1012233%2FBuilding-an-Open-World-Game