Procedural Terrain Painting Using Noise Map Stencils in Chalo Chalo

We've changed to a different system for generating terrain. The new approach is to use noise maps (combined and modified in interesting ways) as 'stencils' for painting the different surface types onto an existing screen full of Voronoi cells. It's a far more powerful approach, allowing us to create all kinds of maps that weren't possible before. Like the one shown in the picture below.



In our previous map generation code each cell decided for itself what surface to take on, a decision it made independently from its neighbours. This meant that if clusters/patches of cells of a given surface type appeared, they did so entirely by chance - we had to power to create distinct patches deliberately. The result was fragmented looking race maps containing no high level order/patterning. Like the following one:



The new system uses a port of the LibNoise library for Unity. LibNoise is a library for creating coherent noise. In the gif below you can see a visualisation of how grass (the green surface) is 'painted' onto our map cells. The noise patterns are shown as red and blue images. Blue areas represent values below 0 (the darker the color the lower the value) and red areas are values of 0 or above (the closer to white the higher the value).

First Perlin noise is created, i'll call that p1. To p1 is added a noise pattern with a horizontal stripe of low values, and higher values at the top and bottom. I'll call the result p2. p2 has no red shapes in its vertical center anymore, and bigger red shapes at the top and bottom. To p2 is added a patten with low values on the left hand side of the screen. This gives p3, which now has no red shapes in the leftmost area of the image.

For each cell of the race map we retrieve the value of p3 at the cell's center point. If the value is 0 or higher, we 'paint' that cell with the grass surface. Optionally we can increase the 'sensitivity' of the sampling process, by sampling more points nearby and compare the maximum value returned from all those samples against 0 instead. This helps if we want more of the red areas in p3 to translate to grass cells in our race map. 

We combine noise in different ways to create stencils for different surface types. Often we want more tar in the middle of the map for instance. Here's a map from the 'Regular' biome that's been created with this approach.

The image to the left is another representation of the map building process. Thumbnails A to D show the process of creating a grid of points, randomly nudging them around, and then deleting points using a noise map, C,  to control the likelihood of any given point being removed.

Bright areas of the C image correspond to areas where fewer points will be removed, which will translate to areas of the final Voronoi diagram (G) that are more densely populated with smaller cells.

Previously we had to be careful about allowing too much lava to show up in a race map. We had no test in place to ensure that the race map could be completed. If the goal was surrounded by lava the players couldn't exit the race. Now we're using the A* Pathfinding Project to fix this problem.

After all cells have been painted, the map creation routine checks to see if there are enough lava cells to potentially block the exit. If there are, we use pathfinding. First a grid of pathfinding nodes is created, each node connected to its eight neighbours. For each node, the terrain type for that location is retrieved. The node is given a 'cost to pass' value corresponding to the surface type. If the node is on lava we assign a very high 'cost to pass' value and add to that a (potentially) large random number. We then ask the pathfinder to find the cheapest/shortest path from to the start zone to the goal. Once the path is returned, we step through it doing a spherecast from each node to the next one. We 'zap' any lava cells that the spherecast touches, reverting them to the most recent non-deadly surface they were previously set to (each cell has a memory of its previous surfaces for this purpose).

Because of the high 'cost to pass' assigned to lava node, the pathfinder will avoid lava if at all possible. If it does have to go through lava, the route it takes is made unpredictable thanks to the random component of the lava nodes' 'cost to pass' value. Here's a visualisation of the pathfinding. Green circles are points at which lava cells were neutralised. 

One of the nice things about this system is that by re-using the same noise maps (with different thresholds) to paint different surfaces you can very easily have a patch of one surface show up inside an area of a different surface. In the following example the grass painting routine uses the same noise module as the ice painting routine, but demands a higher noise value before it will lay down any grass. This gives narrow seams of grass within, and following the direction of, the larger flows of ice.



Here's one of Richard's biomes. He's combined noise modules to cut away more of the lava on the left hand side of the map, creating some dead ends that players need to watch out for. The closer to the goal we get the more grass and ice are introduced, making things more risky. The lava cutter routine guarantees that the goal is always accessible.



Our original Post It notes style terrain allowed large areas of one surface type to contain smaller ones of another, but the overlapping squares created an uncomfortable (to me) suggestion of foreground/background on a surface that should read as being flat.

Our next iteration, the cell-centric Voronoi maps, solved the figure/ground problem by visually flattening the race maps, but the algorithmic isolation of each 'dumb' cell also meant we no longer had patches within other patches and other interesting patterns.

Our new noise-based map generation approach combines the best parts of both our previous systems, and allows us to design spatial relationships between compound surface shapes, giving us many new possibilities for world-building.