Generating random maps


Code for this tutorial is on this git branch:

git clone -b Base_project https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


This game isn’t going to have fixed ‘levels’ – each time you play a new random map will be created. This is exactly how our released game Dinowar works. We even let the user regenerate the maps until they find one they are interested in playing – the maps generate in a fraction of a second.

If you are interested to see how quickly it generates on a mobile device, download the game and have a play (if you are on Android).

Every time the player clicks the ‘refresh’ button on the right hand side, the following happens:

  • New map is generated
  • Bases are allocated (notice the lighter purple border lines)
  • Paths are generated between each base
  • The player and AI players are created and each allocated a base, depending on difficulty level.

For the Zombie game we are creating in this tutorial series, we will be looking at the first of those – creating a random map.

Representing a map in code

Our maps are rectangles, with a width and a height, and is basically broken up into lots of little cells. This might start to sound familiar…

2dArray

This is a 2-dimensional array, and the highlighted field can be referenced with map[5][8].

Now imagine if you filled this array with 1s and 0s. 0s can represent water, and 1s can represent land. Or you could fill it with any numbers you want – 0s can represent water, 1s represent coastlines, 10s represent mountainous regions, 2-9 represents somewhere in between the two extremes. Then when you draw your map, whenever you see a 10 you draw a mountain colour and so on.

In fact, early versions of Dinowar did exactly that:

early_map

Very different from the first screenshot in this post! But the core mechanics behind it are the same.


An aside: why did we choose to go with more simple maps, rather than ones with gradients? In the end, the biggest factor was speed of path-finding. Our path-finding uses Jump Point Search, an adaptation of A* search algorithms, which is faster but loses the ability to take into account different gradations of node – each node is either passable or it is not, unlike a graded map where it might be ‘expensive’ to cross a mountain.


So, all you need is a 2-D array of ints – this is a simple structure to work with. Have a look in World. We have written our own wrapper class for an int, so that we can add additional functionality to it – the ability to tell a node to draw itself, the ability to ask if it is land or water. This might seem a little pointless at the moment, but further down the line we will find it easier to work with than ints. But we have still got the 2-D array declared in World:

protected Pair[][] map

Now all you need to do is decide which Pairs should be water, and which should be land.

Noise

What you want is an algorithm which you can pass some desired width/height parameters and get back an array filled with noise. As mentioned above, we want this to be fast. There are a few different choices of algorithm that we researched, but settled on Simplex Noise. Simplex Noise is computationally cheap compared to other algorithms. For more information read the wiki:

https://en.wikipedia.org/wiki/Simplex_noise

In the best spirit of open-source software development, we are going to use code someone else wrote so that we don’t have to get too bogged down in the detail. This code comes from Richard Tingle on Stack Overflow, who in turn used code in the public domain from Stefan Gustavson.

http://stackoverflow.com/questions/18279456/any-simplex-noise-tutorials-or-resources

I’m not going to repeat his lesson here – if you are interested in the technical detail of how it works, read the answer on Stack Overflow.

Simplex Noise works well for maps because it has a continuous gradient throughout, so you can get ‘blocks’ of land.

We also have to provide this algorithm with some frequencies and amplitudes (again, read Stack Overflow for details) so that it has some random ‘seeds’ to work from. This logic is in WorldGenerator, take a look at the generateMap method.

You’ve essentially got hold of an array of noise, of the correct size for your map. Each time you call it, you pass in some differently generated freqs and amps, and get back a 2-D array full of floats.

The final stage to get your actual map data is to convert these floats into ints of 0 or 1, representing land/water. In our case, every Pair (or node) represents either water or land. We have set a threshold (still in WorldGenerator) – anything below this threshold is water, anything above it (or equal to it) is land. Try fiddling with this threshold if you want to increase/decrease the amount of water.


Aside: if you do want to have proper detail on your maps (with mountains etc), check out this excellent tutorial here: http://javagamexyz.blogspot.co.uk/2013/03/terrain-generation.html

The idea is the same, you just have various thresholds for different levels of land instead of only one.


There you have it! An 2-D array which looks like a not-too-terrible representation of a 2-D map.

All that’s left is to draw it.

Rendering the map

Open up the GameScreenRenderer and take a look at the only thing it is drawing. It makes use of a SpriteBatch (which we’ll come to in a tutorial more focused on graphics).

We loop over the Pairs in the map, and tell each one to draw itself. Each Pair holds a reference to its own Sprite, which in this case is just a white square which we will set the colour of to either blue or green depending on whether it is water or land. This might seem like overkill for drawing coloured squares – but when you want to do more complicated stuff (in Dinowar, some of the tiles are borders and have to draw different images), this is very handy.

And there you have it!

Screen Shot 2016-07-17 at 15.17.31
A map generated with Simplex Noise

Update!

I’ve written a new tutorial, where you can make your maps look a lot nicer. Check it out here: http://tutorials.boondog.xyz/2017/02/19/prettier-maps/



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

One thought on “Generating random maps”

Leave a Reply