Random Map Generation

Generating 2D height maps the easy way

by Matt "dxprog" Hackmann

Introduction

Generating random terrain for games like Civilization or Age of Empires has always intrigued me. How could they make a map that was random yet not a bunch of specs all over the place? Now, there’s probably as many ways to produce a good random map as there are grains of sand. Many of these include using fancy physics simulations, cellular automation, etc. These methods work well, but take time to program and time to produce. I’m not saying that these are bad as they offer more control of the terrain generated than my method, but if you just want something simple for a strategy game or basic terrain for a 3D game that’s easy to program and fairly quick for the computer to create then keep reading.

The Theory

My method for producing maps is pretty straight forward, no fancy math or AI to program. The whole system is based on averages. But enough of the talking, we'll get straight down to how it's done. It all starts out as a 2D array that is filled with random numbers (you could use a 1D array, but since this tutorial is about simplicity we'll go 2D). The dimensions are the size of your map. For our example I'll use a 5x5 map. The first step is to fill the entire array with random numbers. I prefer to use numbers between 1 and 255, but you could go as high as you want (if you are producing a height map image, stay within those limits). 179 136 147 73 76 197 3 193 207 180 11 105 219 201 95 245 222 14 242 92 133 195 13 151 119 Now comes the meat of the whole thing: For each cell we replace its value with the average value of all the cells around it. In the example the cell in question is in dark gray and all its neighboring cells are light gray: 179 136 147 73 76 197 3 193 207 180 11 105 219 201 95 245 222 14 242 92 133 195 13 151 119 So we average out the values in the light gray cells, which is 112 in this case, and replace the value in the dark gray cell with that value. We do this for every cell until the entire map is done. 112 130 121 155 181 72 120 157 164 159 153 150 159 135 158 171 124 146 122 137 163 123 133 131 130 And that's the hard part :-)! If you're just making a height map to be used in a 3D game, we're pretty much done, but if we're doing a 2D map continue reading (3D people should continue reading as a couple of extra tips that apply to you will be presented later). I should note that it would be wise to keep a running tally of the average for each cell. We will then average out this number to get the average number of all the cells (CellsAvg = TotalAvgs / (MapWidth * MapHeight)). This will be used to determine the land type which, in my example, consists of land and water. Basically we run through each cell again and if it's less than the cell average the cell is water, greater or equal to, land. 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 Now you could stop here and use what you've got, but by running the map through the routine a few more times you can get different (probably better) results. In the 3D realm this will result in less hilly terrain. 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 The more you run it through, the flatter the terrain gets making bigger islands in the 2D case. Now of course, you aren't limited to just land and water. With a little tweaking you can do mountains, deserts, etc. Essentially all you need to do is change the conditions that choose what's what. For example, in the example map below less than the CellAvg is water, grater or equal to this but less than (CellAvg + 20) is land, and everything above are mountains. 0 0 1 2 2 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0

Tips

3D Terrain Minimums and Maximums - For 3D terrain you can impose some minumums and maximums by adding or subtracting to the random value in each cell. Another Array - Using seperate arrays for the noise map and averaged map will lead to different, possibly better results. Play With It - What I have shown here barely scratches the surface of what you could do with this algorithm. Just try playing around with it and see what you come up with :-).

Conclusion

I hope that you've learned something in this tutorial and that it will be useful for you. I have a ready-to-go example with VB source code so you can see this in action [Download]. If you have any comments, suggestions, etc. you can reach me at: Matt.Hackmann@gmail.com. Until next time, may the force of programming be with you :-).