# Procedural Hexagon World Map Generation

## Table of contents

- Introduction
- Inspiration
- Requirements

- Hex Map Generation
- Hexagons
- The Hexagon Shape
- Hexagons in a Grid
- Finding Neighbours among Hexagons
- Interacting with Hexagons: Converting from Hex to Pixel and Vice Versa

- Building the First Hexagonal Map
- Adding Multiple Cell Types
- Implementing Elevation

- Hexagons
- Procedural Content Generation for Hexagonal Maps
- Perlin Noise
- Important Concepts
- How Does Perlin Noise Work?

- Creating Elevation Differences Using Perlin Noise
- Creating a Noise Map
- Creating a Colour Map
- Rendering a Mesh Over the Maps

- Perlin Noise
- Combining the Perlin Noise With the Hexagonal Map
- Result
- Conclusion
- Future Development
- Sources

## 1. Introduction

Source code can be found at: https://github.com/Mathijs-Marks/3D-Hexagonal-Grid-Map-Generator

The tabletop role-playing game Dungeons & Dragons (also known as D&D) is known for its in-depth battle -and world maps. These maps set the stage of the world you’ll be playing in. Dungeon Masters pour their creativity in making this world come to life. This gives the players a glimpse of all the places they can go, all the adventures they can experience. It incites a feeling of curiosity, making you wonder what kind of things you’ll find out there. The sky is the limit!

Cartography, a skill used in the real world, can also be used to document the imaginary D&D worlds! On the internet you’ll find a lot of people, Dungeon Master or hobbyist, passionately creating maps of imaginary places. These maps can then be used in someone’s D&D campaign, or for any other use they desire.

I can spend hours just admiring the beautiful maps created by people on the internet; the Reddit forum is full of them. It makes the experience of being in a fantasy world all the more immersing. It also helps when you’re either setting up your campaign, or thinking of your character’s backstory. Take gander at the world you’ll be working with and pick a place that piques your interest. That is now your character’s home. From there, the ideas easily start flowing for me.

Although the making of maps is a joyous thing to do, it also takes up vast amounts of your time. What if I could use my technical knowledge to easily create maps that are still meaningful and unique? Can I make these maps form as a grid in 3D, so that you can also use them as battle-maps? What if I can procedurally generate these maps and make them available to use for everyone? With this Game Lab R&D, I intend to do just that. Let’s start!

For this Research & Development project, I will try to answer the following question: “*How can Procedural Content Generation be used to create a map editor tool that generates a 3D Hexagonal Grid Map, containing varying elements that are calculated by a rule-set in the map generating algorithm?”*

### 1.1. Inspiration

There are many map generators already in existence, so I will have to narrow down what I would like to build upon. During my search for inspiration I decided to base my map generator on the 3D Hex map featured by Jasper Flick at __CatlikeCoding__

This means I will be using a grid-like structure for the map. Luckily, there are a lot of sources of inspiration for these! For instance, Briganti just released a game where you can procedurally generate Dungeon maps. At the click of a button, you’re presented with a room that is fully furnished.

Another beautiful example is the Medieval Fantasy City Generator from Watabou on __itch.io__

Here you can fully customize what your city should look like including infrastructure, fortifications, styles, colour themes, city names, etc.

### 1.2. Requirements

As mentioned in the introduction, there are a few requirements that need to be met for the map generator to be finished. When is my map generator “complete”? What kind of features does it need to have? These will be listed below:

- The map generator should procedurally generate a map at the start, and whenever the user clicks on the “generate” button.
- The map generator should have an UI element where the user can change the ruleset of the generation algorithm, and also be able to choose tile colours and elevation for manually changing the map.
- The user should be able to “paint” the map by clicking and dragging over the map, changing tile type and/or elevation according to selected values from the UI element.
- The map generator should contain at least 4 tile types:
- Water
- Sand
- Plains
- Mountain

- The map generator should contain differences in elevation and include a seed to randomly generate a unique map each time.

If possible, I also want to include cities (with infrastructure) and rivers. I won’t focus on performance, as this would go beyond the scope of a 5 week project. Instead I will note possible improvements where appropriate during this project.

## 2. Hex Map Generation

Before we can start working on the grid where we are going to procedurally generate our map, we first need to consider that we’re not using a regular square-shaped grid. We are using a hexagonal grid, which imposes some challenges. At the same time it also helps in finding neighbours in the grid. The distance between each neighbour in all directions is the same with hexagons, where this is not the case with square grids in the diagonal axis.

### 2.1. Hexagons

What even is a hexagon? When we talk about a hexagon, we mean the 6-sided polygons that look like a cell of a beehive. Hexagons can come in a lot of different shapes, but the one I’ll be focussing on is the regular hexagon.

**The hexagon shape:**

Each hexagon consists of 6 sides (hex) and 6 corners. When put in a grid, hexagons share sides and corners with one another. Each side shares 2 hexagons, each corner shares 3 hexagons. A regular hexagon comes in two orientations: ‘Flat topped’ and ‘Pointy topped’.

What is beautiful about regular hexagons, is that they share the same interior angles for each corner, which is 120°. When dividing this angle by two and drawing a line towards the centre of the hexagon for two corners, you get a triangle! This triangle’s angle is 60° for all three corners. Six of these in a circular fashion, in turn, form a Hexagon! A Hexagon has a maximal and a minimal diameter. The maximal diameter is the distance from the centre towards a corner. The minimal diameter is the distance from the centre towards a side. When trying to determine the width and height of a hexagon, you can use the maximal diameter. The width is determined using: w = sqrt(3) * maximum diameter. The height is determined using: h = 2 * maximum diameter. This is important when trying to align hexagons in a grid.

#### 2.1.1. Hexagons in a grid

Putting squares in a grid is quite obvious for many. You have an N amount of squares in the vertical and horizontal direction. With hexagons, putting them in a grid works a bit different. There are multiple approaches for this:

**Offset coordinates**

Hexagons don’t align properly on either the X or Y axis of a grid like a square does. To work around that, you can offset every other column (X axis) or row (Y axis) to still get a grid of hexagons.

**Cube coordinates**

Hexagonal grids can also make use of three axes instead of two, as is done with 3D shapes. When using cube coordinates, you basically make use of the x,y,z coordinates used in 3D vectors. In a hexagonal grid we use q,r,s. Each direction on the grid represents a line. Where you’d have the x axis on a 3D shape, you have the q line on the hex grid. for the y axis you have the r line, and for the z axis you have the s line. Now, each hex cell consists of three coordinates, just like a vector. This opens up a variety of possibilities because there are a lot of operations that we can take advantage of from vectors, such as: distances, rotation, reflection, line drawing, conversion from world to local space, add/subtract, multiply/divide, and scalar. an important thing to note is that a constraint is needed in order for each hex cell to have a canonical coordinate. In this case the constraint is that q + r + s should always be 0.

**Axial coordinates**

Axial coordinates are the same as cube coordinates, the only difference being that the s coordinate is not stored. Although the s is not stored, the constraint remains the same. to determine the s value, use the following: s = -q-r

**Doubled coordinates**

Instead of offsetting coordinates like in offset coordinates, double the step size for either the vertical or horizontal axis. The Doubled coordinates system also works with a constraint, which is (col + row) % 2.

I decided to stick with cube coordinates, since you can take advantage of Unity’s Vector3 variable to assign coordinates for the hexagonals.

#### 2.1.2. Finding neighbours with hexagons

At any given time, a hexagonal in a grid can have 6 neighbours, depending on whether the hexagonal is not at an edge or corner.

When moving towards one of the neighbours, keep in mind that the sum of all coordinates must remain zero, according to the constraint. So when moving, you add +1 to one coordinate and subtract -1 to another. You can change either q, r, or s by +1. After that you have 2 remaining coordinates that you need to change by -1. This results in 6 possible movements. That is great, since we have 6 neighbours to choose from! So when you want to move to the north-east, for example, do the following: add +1 towards q, subtract -1 towards r, keep s the same.

Another thing that might be good to know is the “true“ diagonal of a hexagon. So not a neighbour, but a hexagon that is directly diagonal from the current hexagon. Instead of adding +1 to one coordinate and subtracting -1 from another, do the following:

Change one of the coordinates with ± 2, change the other two by ∓ 1. The ± and ∓ indicate that the first part of the expression becomes +, while the last part of the expression becomes -, and vice versa, as long as the sum remains 0.

#### 2.1.3. Interacting with hexagons: converting from hex to pixel and vice versa

After having created our hexagon map, we will want to interact with them. But how do you determine their position based on a coordinate in a Unity world space? We use vectors for that but our hexagon coordinates are not stored in this way. fortunately, we are able to convert our hexagon coordinates to a vector position using a matrix multiply. For the matrix multiplication, we will only use the q and r coordinates, as we only need the x and y coordinates for the vector.

To determine the basic vector movement for q: (0,0) -> (1,0) we use (x = sqrt(3), y = 0)

To determine the basic vector movement for r: (0,0) -> (0,1) we use (x = sqrt(3) / 2, y = 3 / 2

To determine the pixel coordinate we combine the basic vector for q with the basic vector for r: q_basis * q + r_basis * r.

When we visualise this as a matrix multiplication, we get the following:

Now we have the pixel coordinate converted from a hex coordinate. With this we can also convert back to a hex coordinate from a pixel coordinate, by inverting the matrix multiplication:

This matrix will return the fractional coordinates in floats for q and r. Because you often save your hexagonal coordinates in integers, you will need to round the coordinates to the nearest integer in order to get a valid hexagonal coordinate.

In the next chapter I will cover how I implemented this knowledge to create my own hexagonal map.

### 2.2. Building the first Hexagonal map

I followed along with the tutorial featured on Catlikecoding, as figuring out how to create a hexagonal map on my own was out of scope for this project. Full credits for the excellent implementation of a hexagonal grid map with in-depth explanation by Jasper Flick. You can find his work __here__.

First we need to create a grid of hexagons. Because hexagons are shaped differently than squares, we also need to account for a different grid structure. Create a grid of squares, separate them from each other to leave some space in between. Now remember that hexagons cannot be positioned directly above one another. To account for this, we first need to offset each row along the X axis. This will create a Rhombus formation. Next, undo a part of the offset. All cells need to move back one additional step on every second row. Now that we have setup the hexagonal grid structure, let’s fill the grid with hexagons. We do this by rendering 6 triangles in a circular fashion to create a hexagon. Make the shape a bit bigger than the squares to fill the empty spaces in between. Now we have a working hexagonal grid! As mentioned in the previous chapter, I will be working with cube coordinates to take advantage of Unity’s Vector3 variable.

#### 2.2.1. Adding multiple cell types

We also want to interact with the map. How do we add some colour to it? This is done by converting a pixel coordinate to a Hexagonal coordinate, as mentioned in the last chapter. We can send a raycast to an object with a mouse click. As soon as this raycast hits the object, in this case the hexagon, we can manipulate the object. In this case the manipulation will edit the cell’s colour. We add an UI component so we can choose some colours, then click on a cell and voila! We have different cell types.

Now the colouring of these cells looks very boring. By interpolating between the edges of neighbouring cells we can create a blending effect when two different colours collide. For this we need to divide our hexagons into two parts. One inner hexagon that will always retain it’s original colour, and one outer ‘circle’ that can interact with other outer circles for colour blending. This outer circle consists of quads and triangles.

When implementing this colour blending effect, you get a much more natural looking grid when adding different colours.

#### 2.2.2. Implementing Elevation

Now that we have the cell types covered, we can focus on implementing elevation. Every time we click a cell, we want it to change colour, but also change in elevation. To do this, we need to change the Y value of the cell. After that we refresh the cell so that it is rendered again with the new values. Add triangles in between the neighbouring cells with elevation differences so that the cells stay connected. This creates some slopes in between the cells.

To add some nice visuals to the elevation, let’s create a terracing effect between the cells. When the difference between height is an increment of 1, we want to see a terrace. When we’re dealing with a height difference of more than 1, we want to see a slope.

If you look closely at the figure below, you can see in the wireframe that for each kind of elevation, the triangles at the edges are triangulated differently. How do you achieve these kinds of triangulations? Jasper Flick has a really interesting take on this. We can make use of the outer circles that we defined at the colouring part of the cells to triangulate the edges of each cell with elevation differences. For the quads that are situated at the straight edges of a cell, this is relatively easy; you only need 3 configurations: flat, slope, and cliff. The slope will receive the terrace effect which is achieved by defining the amount of steps the terrace needs, followed by interpolating between each step. Each quad needs two colours because the quad is only connected to two cells.

For triangles, we get a more complex situation, since these are at the corners of a cell. These triangles will need to blend three colours. There are also a lot of different configurations for the corner connections, as see in the figure above.

Below you can see all the possible corner configurations.

From left to right: Slope-Slope-Flat, Slope-Flat-Slope, Flat-Slope-Slope, Slope-Cliff-Slope, Slope-Cliff-Cliff, Cliff-Slope-Slope, Cliff-Slope-Cliff, Cliff-Cliff-Slope-Right, Cliff-Cliff-Slope-Left, Flat-Flat-Flat, Cliff-Cliff-Flat, Cliff-Cliff-Cliff-Right, and Cliff-Cliff-Cliff-Left.

Now that we have all the connection cases covered, we get a terrain structure that looks much more pleasing to the eye!

## 3. Procedural Content Generation for Hexagonal Maps

During the research period I have had multiple methods for procedurally generating a hexagonal map that piqued my interest. I will list these below, along with a short overview of why I found these fitting for my project and whether I have/haven’t used them:

- Voronoi Diagrams

My first idea for procedurally generating my map. I was intrigued by the cellular looking results you could get with using this method. A nice thing about Voronoi is that you can save them in a Graph, which is great for pathfinding. Because of the cellular look you get from Voronoi, you can often get a more natural looking map than when just using hexagons. At the time of researching, I could not find as much information about Voronoi as I’d have hoped, also I had already started creating my hexagonal map using Jasper Flick’s tutorial. Therefore I decided to postpone a Voronoi implementation for a later date.

- Binary Space Partitioning
- I had used this, among with Depth-First-Search in my prior assignment for Procedural Content Generation. It is a fun and interesting way of determining dungeon rooms by populating a Binary Tree. Although I quickly realised that for a hexagonal map without rooms, this would not be a very fitting method. So I decided not to go further with this.

- Cellular Automata

This method would’ve been great to research on further, because this method already works with a grid of cells. At the time of researching I did not know for sure if this was also applicable on hexagonal cells, and I had already made up my mind for working with Perlin noise. Therefore I chose not to research this further, but it might be interesting to research this as an alternative in the future.

- Perlin Noise

What’s great about Perlin Noise is that it is incredibly versatile. You can use it for a lot of different use cases and you are able to implement it in already existing projects. This was especially fortunate in my case, since I had already created a hexagonal map when researching for a procedural generation method. Because I could implement this in my existing project, and also because of time constraints, I decided to use Perlin Noise to achieve my end-result.

In the next chapter I will cover how Perlin noise works, whereafter I will cover how I implemented Perlin noise in my own project.

### 3.1. Perlin noise

Perlin noise is a type of coherent noise, meaning that changes occur gradually. A kind of Pseudo-random number generator is used to fill a two-dimensional array, which forms a semi-random heightmap. This generated heightmap can be used to create all kinds of Procedurally Generated Content.

#### 3.1.1. Important concepts

- Amplitude: the maximum value of the offset or change of the variable from the average value.
- Frequency: the characteristic of a period process is equal to the number of repetitions or occurrence of events (operations) per unit time.
- Lacunarity: controls the change in frequency.
- Persistence: controls the change in amplitude.
- Octave: samples with different frequencies.

#### 3.1.2. How does Perlin noise work?

When taking a Perlin noise map, cutting it in half, and looking at the cut of the map, one can see a structure with elevation differences (e.g. mountains & lakes, see picture above). The Amplitude controls the Y axis offset, while the Frequency controls the amount of noise occurrences on the X axis. Using one noise iteration will result in a geography that is way too smooth. To improve this, you need several iterations of noise maps layered on top of one another, also known as Octaves. Each subsequent Octave used in a Perlin noise map increases the detail of the map. The occurrence of Octaves can be controlled using Lacunarity. Because subsequent layers of noise add a lot of detail, the noise map can quickly become very chaotic and no longer resemble any geographic form. To remedy this, we can make use of another variable called Persistence. This variable controls the decrease in amplitude of Octaves. So, for each subsequent Octave, we can decrease the Persistence so that each layer of noise adds detail to the existing ‘main outline’.

The result of applying Perlin Noise to a 2D texture will look something like this:

This is a good start, but if we want to implement this in a use-case, like the hexagonal map, then we need to define things like region colours and elevation. In the next chapter I will discuss how I created a terrain mesh with different region types and elevation, using a Perlin Noise map.

### 3.2. Creating elevation differences using Perlin Noise

For the process of implementing the elevation differences using Perlin Noise, I followed along with Sebastian Lague in his tutorial about Procedural Landmass Generation. So full credits to him for creating my first noise maps! You can find his tutorial series __here__.

The noise map implementation will go through three stages. First we will create a black/white noise map using Perlin Noise. Then we will create a colour map on top of it, using the existing noise map. Lastly, we render a mesh over the two maps that will change in elevation, based on the noise values of the noise map and will change colour, based on the colours of the colour map.

#### 3.2.1. Creating a Noise Map

The creation and display of a noise map boils down to three components: A PerlinNoise class responsible for generating the noise map, a NoiseMapGenerator class responsible for taking the Perlin Noise map and creating a heightmap from it, and a NoiseMapRenderer which renders the noise map on the screen.

Unity contains a built-in Perlin noise method we can use to generate our noise map. The only things we need are the modifiers that come with Perlin noise. As mentioned earlier in this chapter, these are:

- Amplitude (also known as Scale in the project)
- Frequency
- Lacunarity
- Persistence
- Octaves

We also need to define a size, a seed, and an offset so that we can move the noise in the X and Y axis. The noise map is saved in a 2D float array, so that we can make use of the X and Y values more easily. We’ll enable the object to be edited in Edit mode so that we don’t have to press play each time we want to manipulate the noise map.

#### 3.2.2. Creating a Colour Map

Next is the colour map. Because we will be working with multiple “maps”, we will define an enumerator to switch between map views for Noisemap, Colourmap, and Mesh. We will predefine some regions with corresponding heights to compare with the noise map. To define the colour map, we can make use of the existing noise map. We loop over the noise map and for each position of the noise map, we sample the current height. We compare this height with the predefined regions. If the height is smaller and/or equal than a region height, we assign that colour to that position. This is saved in a colour map array. This map is then rendered over the noise map.

#### 3.2.3. Rendering a Mesh over the Maps

Lastly, we will render a mesh over the map, and manipulate it’s vertices in the Y axis to create differences in height. We will create a separate class for this called MeshGenerator. Here we take the noisemap as heightmap and loop over the coordinates. For each coordinate in the mehs, we will multiply noisemap position at the Y axis with a height multiplier, and apply this to the vector3 position of each vertex of the mesh. This will push up/down the mesh at different height positions, creating a landmass.

Now that we have a generated landmass based on Perlin Noise, the next chapter will cover how to combine the Perlin Noise with the existing hexagonal map to create an elevated hexagonal landmass.

## 4. Combining the Perlin Noise with the Hex Map

Normally I generate my hexagonal grid in the HexGrid class, but because I now need to take the existing grid and change all the values, I will need to create a new class to provide for this. I set out to create the HexMapGenerator class. This class would fetch current hex grid cell and the noise map from the PerlinNoise class. Then I would compare the hex grid cell position with the position of the noise map and change the hex cell elevation according to the noise map region it currently sits on.

I also added a custom editor for the Hex map generator so that I could manipulate the noise map in Edit mode. In the HexMapEditor class I also added the GenerateMap method and added an UI button component so that I could click to create the procedurally generated hex map.

Sadly, I didn’t get any further than this. I ran into some bugs and issues during the implementation and I couldn’t find out what was happening. Due to the time constraints, I was not able to fix these before the deadline.

## 5. Result

My current progress in combining the two components still contains some bugs and is probably still missing some important parts. So far I’ve been able to render a noise map underneath the lower left position of the hex map. But because the hex map is a grid of multiple hex cells, the noise map will not be rendered fully underneath the hex map. Furthermore, because the hex map is way bigger than the noise map, the noise map does not get rendered with the same detail as in its own implementation. This causes a very pixelated effect for the noise map. This could in hindsight be better for the hex map, since I only need to assign one colour per hex cell. So more detail in the noise map would only create more complexity when rounding the colour values per hex cell. Also, the hex map only changes some cells in *one* elevation and *one* colour. I don’t think this is an issue with rendering the noise map perfectly beneath the hex map, as this is only a visual aid. Instead, I think this is probably because I didn’t get the loop right where I loop through the hex map and change the elevation according to the noise map. So far I haven’t figured that out yet.

## 6. Conclusion

As mentioned in the introduction, in this project I set out to answer the following question:

*“How can Procedural Content Generation be used to create a map editor tool that generates a 3D Hexagonal Grid Map, containing varying elements that are calculated by a rule-set in the map generating algorithm?”*

So far, I can conclude that I cannot answer this question as of yet, because I have not been able to successfully implement a procedural generation method in the hexagonal map.

But looking back at this question, even though I have not created a finished prototype yet, I did get pretty far in answering this question. I think I’m pretty close!

I have covered multiple Procedural Content Generation methods, with Perlin Noise in detail, that can be used to procedurally generate the hexagonal map. I think, with some extra research on another one or two of the generation methods followed by a successful prototype, I can test which method is more suitable for my project. With this test I can include the Application Domain by creating an A/B test that will be sent as a questionnaire. With the A/B test I will also have clearly completed the CHECK phase of the TMC cycle. The varying elements so far are the different tile types and the elevation differences. This can still be expanded upon, I will talk more about this in the next chapter.

## 7. Future Development

There was more work than I anticipated so the backlog for future development is therefore also bigger. I wanted to add Cities (with infrastructure between them) and Rivers to my first prototype, but sadly I wasn’t able to do so. I also wanted to try more than one procedural generation algorithm to see which method works best for my project. This will be for future work. After this is done, other possible improvements are:

- Biome generation based on different climates
- Weather system
- Civilisations
- Provinces
- Procedurally generating geographical names
- Optimizing the game by dividing the grid into chunks
- Optimizing the game by implementing LODs for the hexagon mesh(es)

## 8. Sources

Aversa, D. (2014, 14 november). *Random Maps with Cellular Automata*. Davideaversa.It. Geraadpleegd op 12 april 2022, van https://www.davideaversa.it/blog/random-maps-with-cellular-automata/

Flafla2. (2014, 9 augustus). *Understanding Perlin Noise*. Adrianb.io. Geraadpleegd op 12 april 2022, van http://adrianb.io/2014/08/09/perlinnoise.html

*Generating tile map*. (2014, 21 juni). Game Development Stack Exchange. Geraadpleegd op 12 april 2022, van https://gamedev.stackexchange.com/questions/79049/generating-tile-map

Kyzrati, K. (2014, 9 september). *Procedural Map Generation – Cogmind /*. Grid Sage Games. Geraadpleegd op 12 april 2022, van https://www.gridsagegames.com/blog/2014/06/procedural-map-generation/

Lague, S. (2019). *Procedural Terrain Generation*. YouTube. Geraadpleegd op 12 april 2022, van https://www.youtube.com/playlist?list=PLFt_AvWsXl0eBW2EiBtl_sxmDtSgZBxB3

Nicebyte. (2015). *Using Perlin Noise to Generate 2D Terrain and Water*. Gpfault. Geraadpleegd op 12 april 2022, van https://gpfault.net/posts/perlin-noise.txt.html

Patel, A. (2010, 4 september). *Polygonal Map Generation for Games*. Redblobgames. Geraadpleegd op 12 april 2022, van http://www-cs-students.stanford.edu/%7Eamitp/game-programming/polygon-map-generation/

Patel, A. (2013, maart). *Red Blob Games: Hexagonal Grids*. Redblobgames. Geraadpleegd op 12 april 2022, van https://www.redblobgames.com/grids/hexagons/

Patel, A. (2015, 6 mei). *Implementation of Hex Grids*. Redblobgames. Geraadpleegd op 12 april 2022, van https://www.redblobgames.com/grids/hexagons/implementation.html

Tulenber. (2020, 17 april). *Procedural generation and Perlin noise in Unity*. Kihontekina. Geraadpleegd op 12 april 2022, van https://kihontekina.dev/posts/perlin_noise_part_one/

Patel, A. (2013, maart). *Red Blob Games: Hexagonal Grids*. Redblobgames. Geraadpleegd op 12 april 2022, van https://www.redblobgames.com/grids/hexagons/