Drunkard Walk

The Drunkard Walk is a type of random walk that is one of the most simple dungeon generation algorithms. It gets its name from the staggering patterns it makes.

The algorithm is as follows:

  1. Pick a random point on a filled grid and mark it empty.
  2. Choose a random cardinal direction (N, E, S, W).
  3. Move in that direction, and mark it empty unless it already was.
  4. Repeat steps 2-3, until you have emptied as many grids as desired.

The Drunkard Walk guarantees connectivity from the first grid picked, and you can also guarantee that a set percentage of the grid has been carved out. Unless the grid is large, you should bias the direction chosen towards the centre of the grid as the drunkard walk may end up butting up against the edges unnaturally. You may also choose to bias the drunkard walk to choose the last direction it travelled to create longer corridors.

Code Example

PCG Wiki References

External Links

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License