Tales n’ Tactics map generation and (simplex) noise

I’ll start by saying that Tales n’ Tactics is a turn-based strategy game in a top-down perspective, which is under development by Henrik Forsman and myself.

In this post I’ll go through some of the challenges, methods and experiences I’ve accumulated while working on the map generation of Tales n’ Tactics.

When I started writing the first lines of codes, on what is (hopefully) going to be a full-fledged strategy game, I was faced with numerous challenges…How do I deal with fog of war, path-finding, smart AI and many other things. These were all things I’d get a larger insight to.

In one of the earliest versions of the game I just went through each cell in the grid and filled it with a random object. It could be a forest, mountain, ocean, whatever. There were no complexity or logic in the actual generation just randomly plotted land, which resulted in a dreadful map…

In some later versions, after I’d implemented some other features like; towns, battlefields and a simple game menu, I went back to the level generation with a goal to make it better. After some iterations and a lot of rewritten code, I had a decent map. Now it generated all the grass as a base, and on top of that forests, mountains and lakes in sets from seven to about twelve objects, The maps where at least traversable…unless you ware unlucky to generate a map which trapped you in between two mountains…I now had a decent generation code on which to improve upon.

Later down the line we decided upon having more types of terrain. Instead of the regular forests, mountains and lakes, we wanted to have deserts, swamps and canyons with rocky ground etc.etc. Which obviously introduced some problems. I now had to cram more things on the same amount of space as before, and now there were a bigger chance of getting unplayable maps which only trapped you in a small area.

Around this time, I started using the A-star algorithm for the path-finding of both AI-players and human-players. I could use that algorithm to find out if all player settlements are able to get to, and change the landscape to fit the search algorithms path. But i feel there must be a better way of doing things. I still haven’t figured it out though.

The next thing I did was to change the ground layer from grass objects to a plain dirt-background in order to give the maps some feeling of depth. Around this time I also implemented shadows beneath objects. And in case of the oceans, I placed them above. When changing from grass to dirt, I experienced a huge performance increase because I was now using backgrounds (which have no function calls) for all the dirt instead of objects.

Now a year after I started with this game, I’ve learn’t a lot of different methods of doing things. Both on the programming side of things, and the mathematical. This project have been of great value to me and it keeps giving me challenges each day.

Now on to the more interesting part!

As I mentioned I’ve been doing things in a sorta brute-force way when it comes to the map generation. I’ve been just throwing in items on the map on random places hoping they don’t end up on dumb places, and modifying it thereafter. This was a bad way of doing things…

In the past two months I’ve been reading up on different methods of generation maps for games, and I’ve been deep down in the code of different noise functions. I’ve looked on everything from Perlin to Value noise, but I’ve finally settled on using Simplex noise.

Simplex noise is like a faster version of the Perlin noise algorithm. While Perlin have O(N * 2N) computations for each cell, simplex only have O(N2) (if I’m to trust Wikipedia…) computations for each cell, which means that Simplex is much faster in higher dimensions like 4D and only slightly faster in 2D. The downside is that simplex is much harder to understand (I still don’t understand much of it…). But I’ve implemented it and it works!

The way the generation currently works is that I create a grid and on each grid I set it to a value between zero and one (0-1) using the simplex algorithm. After that I create objects on each grid based on the value which I generated before. E.g, a value of zero result in deep oceans and a value of 0.5 becomes grass and the higher values become mountains.

And by creating multiple grids with different input parameters I’m able to create real-looking maps.

 In the figure below I show the output of the generation-code with different complexity values below.

Image

The way I plan on using different maps is by combining e.g. the first one with a complexity value of two with the rest of them, to get an averaged value on each cell in the grid.

The reason for doing this is that I want to have different biomes which is decided by the complexity two map, and elevation based of the map with complexity six. The one with complexity value three isn’t of any use as of yet and is only used as an example in this case. Later on, I’ll maybe generate some other map features, like temperature and hostile areas and first then, more noise maps will be of value.

Something I could have done better in the development is not trying to reinvent the wheel…There are plenty of good methods of generating maps. And instead of struggling in the beginning I should have done some more research instead of diving head-first into something I’m not invested in.

But for now I’m quite happy with the current state of the game when it comes to the generation part.

Now I’ll just need to spend some more time with the actual gameplay-features, and we’ll soon have a playable beta!

Advertisements

2 thoughts on “Tales n’ Tactics map generation and (simplex) noise

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s