A list of map, dungeon, and terrain generation techniques. Multiple techniques are often combined together to form a complete system.
Complexity: Simple
A simple algorithm that randomly "walks" cell-by-cell until either all cells are filled, or a finish condition is met. Many implementations use a stack-based approach that allows backtracking if the "walker" has no valid moves.
Wikipedia: Random walk
Programming Mazes (video) - javidx9 (2017)
Complexity: Simple
A number of rectangles with random size and location are generated and plotted on a grid of cells. The overlapping portions either become "rooms", or they are discarded (depending on the implementation). Afterwards, "corridors" are generated by choosing a start room and iterating through all other rooms until they are all connected (sometimes the Random Walk or DLA algorithm is employed for this portion)
Complexity: Simple
Complexity: Simple (if using a library)
Takes a series of PRNG numbers, then based on various input parameters to the chosen alogirthm, creates an image that has local coherence (in other words, changes between nearby pixels are minimized). Many algorithms use multiple steps (called octaves) that allow an increasing amount of changes between pixels, which manifests as higher detail/noise.
Most algorithms will work in at least 3 dimensions. Most algorithms output a single floating-point value (greyscale, if it were to be interpreted as a color). We could also generate an RGB "color" value by offsetting each color component by a specific z (3D) or w (4D) offset (eg. r = f(z=0.0), g = f(z=0.5), b = f(z=1.0)).
While you can implement these yourself, there are many freely-available implementations.
Example operations that can be done on a per-pixel basis to adjust the output:
8 would produce output values between 0 and 7). Will likely need pre-scaling in order to retain local coherence, otherwise the output would be similar to a continuous step function.Wikipedia: OpenSimplex noise
Wikipedia: Simplex noise
Complexity: Moderately Simple
An area is recursively divided ("partitioned") into smaller areas, forming a tree of cells. After a certain number of iterations, partitioning stops, and a randomly-sized "room" is placed in each cell. Corridors can be generated by crawling the tree structure and connecting each room to its sibling, then connecting a sibling in each tree to its "cousin" from another parent.
The areas generated can either be axis-aligned (eg. partitions align in X, Y, or Z directions), or convex hulls. Axis-aligned is much easier to generate, and may be more desirable for room/dungeon generation. Convex hulls have partitions drawn in optimal locations depending on the problem that is being solved, eg. by calculating the vector/"line" between two objects, then drawing a perpendicular partition on the line's midpoint.
Wikipedia: Binary space partitioning
RogueBasin: Basic BSP Dungeon generation
Binary Trees (video) - Richard Fleming Jr. (2013)
Complexity: Moderately Simple
Takes a series of points on a 2D plane and produces a diagram containing regions that are closest to each point, given a particular distance metric (most commonly, Euclidean distance, but Manhattan is also used).
Calculating a Voronoi diagram via brute-force search can be very slow. Fortune's sweepline algorithm is an optimized implementation that drastically speeds up the process.
As a post-processing step, Lloyd's relaxation algorithm can be implemented to achieve cells that are more evenly-spaced.
Complexity: Moderate ~ Advanced
Wikipedia: Graph rewriting
Complexity: Moderate
A simulation of cells where the creator/programmer provides the start state for each cell and a set of rules defining how each cell interacts with its neighbors. The classic example is Conway's Game of Life-- a simple 1-bit synchronous simulation with only three rules and the initial state is typically randomly generated.
There are two major types of CA systems: synchronous (parallel) and asynchoronous (serial).
Synchronous (or parallel) systems operate by maintaining a current state and a next state. This allows all cells in a single simulation cycle to operate atomically on the same set of data. Once all cells have finished updating, the next state data is copied into the current state, and the next round can begin.
Asynchoronous (or serial) systems allow each cell to update their state immediately. The next cell to execute will then be operating on state information modified by the previous cells. This type of system can be beneficial if the system is expected to converge on a final "solution", as the number of rounds required to find the solution could be reduced.
Complexity: Advanced
Complexity: Moderate
Produces an output image that has local similarity to an input image. Differing results can be obtained by adjusting the input image, tile/search size (n), symmetry, and seed value. WFC has two primary modes of operation: Overlapping and Tiled.
Takes a set of input data (typically an image), then uses that data to build a list of kernels based on the tile/search size (n).
This method is relatively easy to implement, since it only requires passing in a list of values (image), along with a set of parameters. However, it can be difficult to achieve results with complex/high-frequency input data-- the input image and n size need to be carefully crafted and tested to achieve good results. As the input and output sizes increase, the algorithm time increases significantly, and there may be a very high failure ratio (no solution available) for complex inputs and large n values.
Rather than using an input image (or list of values), the Tiled method takes a set of tiles as input data, along with constraint and hint metadata for each tile combination. Each "tile" is an identifier used to construct a more complex model, such as an image, 3D model, etc. The algorithm does not need to be aware of what each of the tiles contains, and only relies upon the metadata to provide a solution.
This method is much faster than the Overlapping method, since it does not need to search for and compute a list of kernels. The Tiled method requires significantly more setup time to prepare each problem-- need to prepare each "tile" (image, 3D geometry, etc.), and write extensive relationship definitions. However, it allows for much greater complexity since the constraints can be exactly defined.
GitHub: WaveFunctionCollapse
Procedural Generation with WaveFunctionCollapse - Stephen Sherratt (2019)
Markov Chain based Wave Function Collapse -
Pronay Peddiraju (2020) - gives a good overview and explanation on how both the overlapping and tile-based WFC algorithms work
Complexity: Advanced