A collection of interesting dungeon-related algorithms

I encountered/created all of these while implementing my JS roguelike game, js-like. Please note that a reasonably fast computer might be necessary for viewing this page, as it contains quite a lot of Javascript.

1. Dungeon generation

Creating a suitable dungeon layout is one of the primary roguelike tasks. Some dunegeons resemble mazes, while other look like a cavernous system, dugged out by a group of goblin dwellers. The brown slash sign (present on some of the maps below) represents (open) doors.

Uniform dungeon generator (refresh)

This algorithm works in two phases:

  1. A set of randomly sized and positioned rooms is generated
  2. These rooms are connected with corridors of varying shapes (L-shaped, I-shaped and S-shaped)

Digger dungeon generator (refresh)

The main goal of this algorithm is to mimic a living digger, who creates a system of interconnected tunnels and rooms. I use many ideas from an excellent article Dungeon-Building Algorithm, written by Mike Anderson.

Divided maze dungeon generator (refresh)

A fast and simple way to create a maze is to use a Recursive division algorithm. It is best suited square mazes, but works pretty well with any rectangle.

Icey's maze dungeon generator (refresh)

Cool mazes with configurable regularity can be created using this algorithm, taken from a Rogue Basin wiki.

Perfect maze dungeon generator (refresh)

For a full explanation of this wonderful Eller's algorithm, please see http://homepages.cwi.nl/~tromp/maze.html. Not only it generates a Perfect maze (every two cells are connected by exactly one path), but it only requires 2*N memory to generate a maze of N*N size!

2. Field of view

Click on any non-empty cell in the map above to highlight the region visible from a given point. This area is computed using the Discrete Shadowcasting Algorithm.

3. Timing (refresh)

While roguelike games are not played in real-time, proper timing also must be taken care of. Individual beings, or actors, take turns in their actions. Every actor has a speed rating – a dimensionless relative value, which determines how frequently can the actor perform his duties. A speed of 200 means twice the amount of turns, when compared with speed of 100.