Westward dev log #2: procedural terrain generation

In the previous log, I discussed a way to manage a very large map, and raised the concern of having to actually populate such a big map. In this entry I’ll discuss a possible solution in the form of procedural terrain generation.

Procedural terrain generation

Procedural content creation is often used at run-time, to generate content on the fly, which is different for each player and each time a player plays the game. But it can also be used at “make-time”, that is, as a help to generate content, that will subsequently be fixed and the same for all players all the time. This second scenario is the one that corresponds to what I’ll be discussing here.

Let me be clear, I have absolutely zero experience with procedural stuff. Given my background in AI, I simply have a tendency to want to automate things, including creating the world of my game (note: I am not using machine learning or any other branch of AI at the moment for this, but there is definitely room for it). Therefore I started thinking about what aspects of the game environment can be particularly annoying to make by hand and could possibly be generated by the computer.

Looking at the demo map of the game below (made by hand in Tiled), I find it striking how the “cliffs” bring life to the scene and make the terrain more interesting. However, they are time-consuming to make, as they involve many tiles that need to be arranged properly to produce a visually appealing result. So I endeavored to make them procedurally.

I first considered using Perlin noise, which is a very common algorithm in procedural content generation. However, I was not satisfied with the kind of shapes I obtained and found that it didn’t fit well with the constraints of the tileset I’m using (these issues may have been alleviated if I had more experience with the technique). So I set up a very ad hoc solution for this, described below.

Recipe for cliffs/terrain elevations in Westward (v1):
– Pick a location to place the elevation.
– Generate n rectangles of random dimensions (I had good results with n = 3) and random positions around the initial location. These rectangles are represented by arrays of four vertices.
– Merge these n rectangles into one single concave shape. This requires to identify which vertices of each rectangle will ultimately be within that shape, and which ones will be on its edges. Those within the shape have to be discarded. New vertices have to be added where two edges intersect. In the end, the shape is represented as one array of vertices.
– Compute the centroid of the shape.
– Sort the vertices of the concave shape clockwise around the centroid of the shape (or anti-clockwise, doesn’t matter, but they need to be sorted).
– Perform two passes of smoothing, to remove some aberrations in the shape and create additional angles if needed (most smoothing operations involve swapping vertices in the ordered list).
– So far, the list of vertices only represent the angles in the shape. In order to ultimately be able to draw the cliff, we need a list of all the tiles that will be along the path of the shape. The next step is therefore to interpolate between the vertices to create a final list of tiles.
– For each point in the list, determine which part of the tileset it corresponds to, based on neighboring tiles.
– Draw (this includes minor adaptations to accommodate for the specifics of the tileset that will be used).

Below are a few examples of the results. The white lines represent the shape that has been created, superimposed over the actual drawings derived from these shapes. The colored dots are debugging markers.

The process is quite involved, and it is possible that the same result could be achieved in a more elegant way. In any case, coming up with this was a good exercise in 2D geometry and algorithms, and yielded a score of methods that should prove useful in the future (for debugging purposes, pathfinding-related computations, or other procedural tasks). The same process could be used to generate other angular, concave shapes.

This approach allows to create irregular shapes to produce terrain elevation. By adjusting some parameters (number and dimensions of the seed rectangles), elevations of different sizes can be obtained, which could be layered on top of each other to make it more interesting. This should be accompanied with other terrain elements, such as water, trees, etc. These may require different approaches and will involve some fiddling about.

At the end of the day, no matter how complex and integrated the approach, the creation of a truly appealing world for the players can’t be only procedural. Algorithms such as the one exposed here can be time-saving and useful to generate a basis, but some amount of manual tuning should follow to give a soul to the environment.

What’s next

What I describe in this entry is still relatively basic and will need to be expanded upon, which might be the topic of the next dev log. Alternatively, I might start working on player movement and pathfinding, or on setting up the networking. At this point of the project, the development can go in many directions at the same time, we’ll see what happens next!

Eventually (sooner than later), I’ll have to decide on a schedule based on the design document of the project, and will be able to forecast better the content of the next logs.

About the tileset

The tileset I’m using is not the final one, but a visually appealing placeholder for the development phase. I didn’t make it myself. I found it on opengameart.org, and it was made for a defunct game called Whispers of Avalon.

Jerome Renaux

I'm an independent game developer, working mainly on browser-based multiplayer online game (HTML5 & Javascript). I love to discuss about all aspects of game development so don't hesitate to get in touch!

More Posts

Follow Me:

Jerome Renaux

I'm an independent game developer, working mainly on browser-based multiplayer online game (HTML5 & Javascript). I love to discuss about all aspects of game development so don't hesitate to get in touch!