Honours Project: Procedural Terrain Generation and Pathfinding

As part of my final year of University we were asked to design, create and document a large scale project using any programming language or technologies we desired. The project was first proposed as a Real Time Strategy / Simulation game featuring procedural terrain generation. The initial idea was that a task would be delegated i.e. building a house by the player, and then the NPC characters would intelligently queue other smaller tasks in order to achieve the overall goal together. In this case finishing construction on the house would be the end goal to complete. After a short period of analysing the feasibility of the proposal, I decided to focus on two aspects of the proposal; procedural terrain generation and pathfinding. Concentrating on these two areas meant that I could fully explore the topics individually, as well as how they interact with each other as game features.

The project was built using the Unity3D engine, the motivation behind this stems from research I had done prior to starting development on the project relating to custom game engines for solo projects. There are so many powerful and feature-rich game engines currently available for public use that creating a custom game engine from scratch doesn’t make much sense for a solo project. After spending a year working mainly with C# at Fujitsu in Germany I also thought it would be appropriate to put my experience with C# to use for the script files. An advantage of working with Unity is being able to prioritise gameplay mechanics over technical obstacles. Unity scripts allow for incredibly rapid prototyping which can streamline the life-cycle of the project, removing a lot of the debugging and testing demanded from in-house game engines.

Procedural terrain generation is done in the project by generating layers of Perlin noise known as ‘octaves’ and combining them together in what is known as ‘fractal noise’. Below are two real examples of fractal noise generated within the project, showing the differences between zero and many octaves of noise and the effect it has on the overall noise. As can be seen, more octaves increases the detail of the noise and is more pleasing to the eye. The figure on the left shows a section noise with 0 octaves, while the right figure shows a fractal noise with 8 octaves.


Sections of fractal noise are then interpreted as elevation data to shape the terrain. Areas of noise closer to white represent values closer to 1 while black indicates a value tending towards 0. With this information we can transform the vertices in a flat plane mesh to show the shape of the terrain. The result of this can be seen below.

wireframe terrain

Terrain mesh

A custom shader is then used to texture the terrain according to height with overlapping areas which allows for blending between textures. Resources are then placed at varying densities according to height including trees, rocks and grass. This system was designed in such a way that the user can add any number of game objects to the resource pool and they will be distributed throughout the landscape.

executable 2017-06-10 13-13-40-511

Texture blending and resource placement

Pathfinding is implemented using a grid based approach and diagonal distance heuristics. Diagonal movement was chosen because it gave more natural pathing to the entities in the scene – this also made sense from a design point of view since the game agents take the form of fantasy Wisps. In order for entities in the scene to properly navigate the terrain they need to be aware of what nodes in the grid network are traversable and which are not.

terrain traversable nodes

Non-traversable nodes shown in red

An algorithm based on the popular A* algorithm is used to determine a path for a game object to a given destination. The reason A* was used is due to its accuracy – given an admissible heuristic is used (a heuristic which does not overestimate cost) the A* algorithm will always give an optimal solution.

pathing

Multiple game agents showing their path to a shared destination

In order to demonstrate smooth turns and movement, a path smoothing technique is used. This is done by analysing the distance between each game object and its next waypoint on the path to its destination. Once the distance is within a specified threshold the game agent will begin to turn towards the next waypoint, providing a smooth turn.

pathsmoothing

Path smoothing

The pathfinding system uses a management system so that any number of paths can be requested from any amount of game agents and processed in a timely manner. This means that multiple game agents can be navigating the terrain at one time with no performance hit – this is largely due to the use of threading in the management system.

executable 2017-06-10 13-13-13-083

Several game agents pathing to separate destinations

The project was completed over a period of a year, including the design, implementation and documentation stages. The accompanying documentation consisted of over 50 pages and together with the implementation of the project was a considerable part of my overall degree. My final grade for the project was a high First, with a mark of 81.

executable 2017-06-10 13-09-54-381

Terrain generated

poster-a4

Project poster used as part of presentation material

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s