Island Generation

Today, we are going to talk about a generation method, which focuses equally on making believable terrain, and on making gameplay-centered maps. To this end, several different methods are combined. In not so many words, this .gif shows off most of what I'll be describing:

Overall, the generation steps can be summarized into three parts:

1. Generate initial terrain
2. Connect nodes, building paths
3. Translate paths into obstacles

Let's talk about each step, and I'll try to comment on why I chose to do things this way, as well as what I mean by "gameplay-centered".

GENERATING INITIAL TERRAIN

The program is, on one hand, tile-based, and on the other, node-based. Translating between the two, we have a big grid of tiles seperated into chunks. 

Currently, I am working with chunks of 64x64 tiles, since this is what worked best gameplay-wise. Each tile should represent its own area, so it should be big enough to feel substantial. Having a full grid of 375x250 tiles, and wanting some blank space along the border leaves us with a 5x3 chunk world. 

Though it is not shown in the animation, terrain has already been decided. Most of these chunks are made to be land, though a random (non-Perlin) number of them are turned into water. This is enough for each map to feel characteristically different, especially in the case of islands.

The biggest problem with square chunks is that they have these ugly four-way intersections at their corners. This looks terrible once the tiles are translated into terrain. For this, and some other reasons, the second row is offset horizontally. In this new constellation, though still very much squares, the chunks sit in the same pattern known from hexagon-tiling.

To save our world from being square and predictable, a Perlin distortion is added. For each tile, its corresponding chunk is found - just like above - but here its X and Y coordinates are offset by two Perlin noise values. This goes a long way to ensure the terrain borders seem more natural and interesting. This is more of an aesthetic than gameplay thing, though certainly, randomness ensures one does not play the same map again and again.



CONNECT NODES, BUILDING PATHS

Another benefit of using chunks is that it is easy to create nodes that feel related to the surrounding terrain. Here, each chunk has its own node, first placed at the centre of the square, and then offset by Perlin noise.

Nodes are connected at random until all nodes are connected to each-other. Sometimes you have highly connected areas like the reds and green, and other times you have close nodes, like yellow and pink, which have no connection.

The gameplay that I am for here is exploration of the island with light combat. Considering exploration, the paths makes the terrain feel more important, since you cannot just go anywhere. In a way, it creates a more directed experience as you explore the island - it makes it more straightforward to ensure that the player will find all the requisite objects instead of wandering past them just out of view.

Considering combat, if the paths were not there, one could simply run around enemies. Later on, I will do as much as I can to make the paths generate interesting crevasses and contortions that make for interesting arenas for combat, offering cover from attacks.

But straight lines won't do at all. For several reasons. One is that it looks unrealistic and makes the generation algorithm very obvious to the person playing the game, breaking immersion. For gameplay reasons, we would also prefer a varied terrain with outcroppings usable for cover, and paths where you need to maneuver instead of just holding down the movement buttons.

On top of the paths themselves, we are adding a Perlin noise layer. This layer determines how many tiles away from the original path should be cleared - that is, in simple terms, how wide the path is. However, as you can see, it feels very different from a simple "path wideness" measure. Instead it creates open areas where you can explore and tight, dangerous paths other places.


TRANSLATE PATHS INTO OBSTACLES

So now that we have a map of where the player should be able to go and where they should not, the naïve approach might be to just fill up the impassable areas with a tile-blocker. However, this would look unrealistic and a bit too visually chaotic.

Instead, we can say that only the borders of the impassable areas should be blocked off. This creates the thick black outlines around the dark areas. Deeper within the field are more sparse obstacles

To make the explorable areas a bit more interesting, whenever a passable area has been generated that is far enough from a path, there is a random chance to place an obstacle. This is the explanation of the black dots spread around some areas. The density has been picked so that the player can almost always pass through, but still dense enough to necessitate interesting maneuvering.

With how the game is set up, we don't actually need to place obstacles side-by-side. The player character is wide enough to be unable to pass through one-tile gaps. This means that we can replace the thick black borders with single dots, as shwon above.

The reasoning behind this is that side-by-side obstacles look terrible. With the same, square offset, fitting too neatly into an obvious tile structure. Personally, I can't stand it. Perhaps it is fine visually, and also from a gameplay perspective since one sort of wall is as good as another sort of wall, but it just breaks realism and shows the weakness of the terrain generator.

But I mean, I probably should go back on the belief described above, because this map looks terrible compared to all that we have seen before. A lot of care and attention has gone into how each biome looks and how the obstacles are picked, but in this bird's eye view, it looks really jarring.

However, the above picture is at 50% zoom while the game itself is designed to be played at 400% zoom - a difference-factor of eight. Playing the game, this is more like what the player will see:

Well, that's a bit more believable. Still, I really could use a better tileset. There is quite a bit of story to this one. It comes from a project I was originally working on, well, about five years ago. Since then, I have added more tiles to it, but never actually gone and fixed the flat-shaded artstyle.

You might also notice some sprites overlapping. Well, that's a bug that does not exist in the game, only in this example specifically programmed for this blog. The actual game looks quite a bit different, all in all (3D WIP):

Anyway, I think that has been quite a thorough introduction to how to generate islands like these. I guess I gave some pointers as to how to make algorithms with consideration to gameplay. So that's that.


PERSPECTIVES

It is interesting to compare this to the classic pixel-by-pixel Perlin noise way of generating terrain - see, for instance, my post on country terrains. I believe the latter has distinct advantages in generating interesting and visually pleasing terrain - however, I cannot even start to wrap my head around how you could change the algorithms to be more gameplay-centred. There seems to be a trade-off - or perhaps I will return in a couple of months with an even better understanding of Perlin noise and have come up with an answer.

Overall, I lean towards preferring tile-based, not pixel-based, terrain generation, though it changes a lot from project to project. For instance, my hexagon-based terrain generator is able to create convincing coast-lines by applying random distortions to the geometry. The downside is not that great. And the upside is pretty big, saving on computing resources and offering a more approachable scale on which to implement gameplay.

One day, I'll find a better tileset and return to this and see what happens.