A year ago, I knew nothing of how the procedural generating of maps (or any other content) works. I first tried my hand at this with Key, Shovel, Treasure, our small pirate game for kids. And with the help of Michiel, that game now generates maps that are fun to play on and visually interesting enough.

Key, Shovel Treasure generates maps in this relatively simple way:

• Assign land or sea to each tile at random.
• Remove land tiles that touch another land tile on a corner without being connected in any other way.
• Assign sea to the four tiles in each corner.
• Check whether the number of land tiles is within the limits for that map size. If not, restart the prcess.
• Check whether all sea tiles are reachable. If not, restart the process.

Not the most elegant or advanced procedural generation system ever, but it gets the job done:

For the current prototype (name needed), I had to dig a little deeper. There are currently three types of terrain; water, grassland and mountains that have to be put on the map. Also, as I wrote last week, there are all kinds of resources that have to be spread on the map.

For both of these, I use Perlin noise. The general consensus seems to be that Perlin noise isn't enough to generate good maps, but as a start it works fine for my purposes. As I understand it, Perlin noise works as follows (in 2 dimensions):

• The basis is an infinite 'sheet' of waves stacked on top of each other. Every point on the sheet has a value between 0 and 1. This sheet is always the same.
• In order to create variation, you can use a different part of the sheet. So in order to 'randomise' your Perlin noise, you don't change the waves, but you change the position on the sheet from which you read.
• To change the frequency of the noise, you zoom in and out on the 'sheet'. You don't do this directly, but by varying the size of the steps you take. To do so, you can apply a modifier to the x and y you feed into the function; less than one to zoom in (and get larger waves)  and higher than one to zoom out (and get smaller waves). I'll call this modifier frequency here and hope this isn't too confusing :).
• So basically, Perlin noise gives you a value between zero and one in return for an x and a y coordinate.

In order to generate the tile types on the map, I assign a height to each tile with Perlin noise (with a frequency of 0.1). Any tile with a height of 0.25 or less becomes water and a tile with a height of 0.75 or more becomes a mountain tile. All other tiles are grassland.

​I then place the resources on the map, using Perlin noise for forests and rocks and simple random placement for the other resources. For forests, the frequency I use is 0.15, so slightly more zoomed out than for the map generation. Each grassland tile for which the value lies below 0.3 become forest.

For rocks, I use a much higher frequency, 0.7, which means there is much more variation at small scale than for the tile types and forests. The chance that a grassland tile has rock on it is 0.2 (below which the tiles has rock). For mountain tiles, this chance is multiplied by 2.5.

As a side note, I arrived at these values through selecting a likely one and then tweaking until I had a value that worked for the game :). After placing everything, a full map looks like this:

This works pretty well for the game. The only thing is that I don't like the artificial border that the edge of the map represents. There are multiple ways to solve this issue. One is to build the map in chunks and load extra chunks as needed. While that's something I'll want to (and have to) dive in eventually, I don't think that's the most productive use of my time at the moment.

Another way to solve this is by turning the map into an island, which is much easier and which I was planning on doing anyway. So that's what I've been tinkering with. My initial idea was to simply add a paraboloid in the middle of the map and subtract those values from the heightmap. I say simply, since the function for a paraboloid turns out to be not very difficult:

Here, z is the height above point (x, y). The constants a and b indicate how much the paraboloid is stretched in respectively the x and the y direction. If both are 1, you get the 3d version of the standard parabola, y = x^2.

To translate it to the middle of the map, I just had to subtract half the map size from x and y. Figuring out what a and b had to be took a bit more thought, but I decided to set them to half the map size (after some tweaking). This makes the island scale when I generate a larger or smaller map, which suits my purposes for now.

What gave me more trouble was that simply subtracting this value from the height gave me maps with too few mountains. Simply increasing the chance a tile is a mountain would add mountains mainly in the middle of the map, which would both be boring and not good for game play. Another option, only subtracting this value if it was above a certain threshold didn't work either. It gave me maps with enough mountains, but that were too circular (not completely, but too obviously round for my taste).

Eventually, I settled on only subtracting the modifier if it's larger than the height value from the Perlin noise. This produces maps I'm quite happy with:

On these maps, the occasional (lonely) mountain will pop up from the sea. I'm not yet sure whether to see that as a bug or a feature :P. Also, the percentage of land tiles is obviously much lower on the new maps. So I went from a standard size of 55 x 55 to 85 x 85 to keep the land surface roughly the same as before. Eventually, the size of the map and other game variables will become tweakable.

There is one more thing I want to add to the map generation before I call it good enough for now: ocean tiles. As it is, you could build a bridge all the way to the edge of the map. Besides potentially leading players into a one way street in the name of exploration, there's something quite illogical about building long bridges to nowhere. Surrounding the island with ocean tiles, on which you won't be able to build bridges, should prevent that. I'm not yet sure how I'll do that, but I'm looking forward to building, tweaking and testing it.

I hope you enjoyed my little foray into procedural generation. There certainly is a lot more to learn for me about procedural generation. But what I have already learned is that I'm having fun putting this together :).

- Willem -

Last week, I wrote about our projects, focusing on the prototype I'm building. From now on, I'll be keeping you up to date about what I'm doing through this blog. Before I do so, I should probably tell you what this game actually is. It was present in the last post, but not very clearly.

The main idea is that you build up your town using the resources around you. Each building has a benefit for your town and the more advances buildings require that other buildings have been built first. By placing roads and outposts, you can explore the land around you, uncovering more resources. You can only harvest a resource if you have a road connection to it. Also, there are no moving units in this game (where have I seen that before?).

But just building your town and exploring the land isn't all. Sooner or later, you'll run into the blight. This corruption slowly spreads across the land, making buildings unusable and preventing you from harvesting resources. You can defend yourself by building special walls and blight-reducing towers, but eventually you'll have to venture out and remove the spots where the blight originated, the primal blight.

And that's the game in a nutshell. Now for some more detail.

This is the start of a test game I played yesterday. The maps are randomly generated and this start happened to have a lot of rocks close by. The two basic resources are stone and wood. Also visible are iron ore (dark grey), copper ore (brown) and Goop of Life (the bright green stuff). You need iron and copper pretty quickly and they can be gotten from their ores by building smelters. Goop of life comes into play later and can't be harvested before you build a goopstorage, a special building that requires quite a lot of copper.

In my test games, I found that sometimes the stone runs out. It then becomes really difficult to get more stone both because of the blight and because roads, like all other buildings, require stone. In the game pictured above, I didn't have that problem, but eventually the stone nearby my town ran out and I had to venture farther afield to get more.

Obvious solutions to this problem are to either add more rocks to the map or to increase the amount of stone from each rock. But since resources block roads, this spawns other problems such as getting hemmed in. Also, if adding enough stone for a worst case scenario makes it too easy to get in a normal game, the game becomes less fun. So I've been mulling this over for a while.

The solution came to me somewhere over the holidays. As you can see in the picture below, it's possible to construct mines on mountain tiles:

These are used to extract copper ore, iron ore and crystal (the red stuff, and a resource I hadn't mentioned yet). It occurred to me that it's silly to have a shortage of stone even though you're digging mines into mountains. So the solution I'm implementing now is that you can use a depleted mine to gather stone indefinitely, basically giving you an unlimited amount of stone. The catch is that it takes much more work to find good quality stone and bring it up from a mine; normally, harvesting stone occupies 5 people, but in this case, it will take 25.

Sometimes I drive myself crazy because I can have trouble accepting a less-than-elegant solution for a problem. At times like this though, I'm happy that my mind won't let go of this until I've found something that really fits and preferably does work on multiple fronts. I guess that what I'm trying to say is that I like this solution :).

I'm also considering whether I should add the possibility to plant new forests, making it less likely that you'll run out of wood. But I'm not really sure yet about that. The main thing stopping me there is that it takes a very long time for a forest to mature enough to have produced a significant amount of wood. I'll probably have to test this to see whether there's a sweet spot for the amount of time this should take in the game.

Back to the game from the first picture. In the picture above you can see that I managed to wall off quite a large area around my town before the blight came too close. I also built towers along the perimeter to make sure the blight stayed out.

It was about this point in the game that I realized that I was enjoying myself. I think this is a good sign. At the very least, there's one person who has fun with this game ;). And since I don't consider myself to be particularly unique, there's a chance others will like it too. (I think. Perhaps.)

This did make it all the more annoying when I 'found' a bug which crashed the game. I wasn't sure whether to be happy that I found a game breaking bug or cranky that my fun was brutally cut short. Although I must say that having the possibility to fix something like that yourself is a pretty good antidote for the crankiness :).

Anyway, that's it for now. I'll keep on tinkering and showing that here.

- Willem -