There’s a lot of content online about procedural generation in game development, especially as applied to roguelikes and top down games, so I wanted to do a short breakdown of my most recent projects strategy and the algorithms used.

Requirements

First, a list of things that are required from my solution.

1. Spaces which are organic and mostly open
2. A dense set of points primarily used for enemy spawn locations
3. A sparse set of points for rarer rewards, objectives, or key areas
4. A set of parameters that can be used to meaningfully shape the generated level

Carving out the Terrain

The core of the level is created using a cellular automaton inspired by Conway’s Game of Life. Each cell of the grid is in an alive or dead state (floor or wall) and will change based on the state of neighboring cells.

Starting Shape

To give some level of control, noise is applied in the approximate shape the stage should take. The percentage of cells that are alive vs dead controls how dense it is, i.e increasing the alive percentage opens the map up while decreasing it creates more internal terrain and dead ends. As of now I just generate the noise in circles / squares, but more advanced starting shapes could create more unique maps.

Iterations

The grid performs several iterations of transforming cells based on neighbors. I settled on randomly doing 5-8 iterations, as more than this tends to over smooth and empty the inside of the stage. For each iteration, the following rules are applied:

• Cells that are alive
  • die with 3 or fewer alive neighbors
  • stay alive with 4 or more alive neighbors
• Cells that are dead
  • stay dead with 4 or fewer alive neighbors
  • come alive with 5 or more alive neighbors

Cleanup

This process can sometimes produce unreachable sections. To remove these, each island of floor cells is floodfilled and only the largest is kept. Additionally, I remove any islands of wall that are smaller than 5 cells.

Representing Openness

With the finalized geometry, it’s useful to have an idea of where relatively open areas are. Key objects can be placed in the center of large and open areas rather than smushed into terrain. A distance map is built such that cells with value 0 are adjacent to walls, with larger values representing larger distances from walls and thus more open areas.

Selecting Points

Poisson disk sampling is used to randomly select sets of points that are a minimum distance from each other. These points use the distance map described above to shift points towards more open areas. A dense field of points is created with a minimum distance of 2, while a sparse field of points is created with a minimum distance of 10. Another set of points is created for placing decorations and props.

The dense field (blue) will be used for possible enemy spawn locations while the sparse field (cyan) will be used for more influential placements like objectives or rewards. Additionally, the players spawn point (pink) is selected from a dense point far away from the center of the map.

Object & Tile Placement

Finally, the stage can be populated. The grid is used to place the floor & wall tiles, decoration tiles, or interactable props. Different systems will use the map data for the placement of their objects. Depending on the perspective of your game, it’s also likely that you’ll have to do some magic with layers, e.g. in my case I have tile layers with no collisions for walls the player can walk infront of and behind.

Final Thoughts

This approach definitely has room for improvement. I plan to experiment with more diverse noise placements, as stage silhouettes can be very samey when always starting from a circle/square. For the time being though it provides a solid foundation to build other core systems onto.