Algorithms

[cxong]

Some existing algos to try:

• Random walk
• C-Dogs room/wall/square
• Rogue
• Angband
• Nethack
• Cellular automata
• BSP tree
• Tyrant
• House with rooms by Shadows In Rain

[cxong]

Rogue page down; reproduce archived version here:

By Mark Damon Hughes <[email protected]>

   The original Rogue algorithm is pretty nifty. Any time you need a random dungeon, give this a try:

1. Divide the map into a grid (Rogue uses 3x3, but any size will work).
2. Give each grid a flag indicating if it's "connected" or not, and an array of which grid numbers it's connected to.
3. Pick a random room to start with, and mark it "connected".
4. While there are unconnected neighbor rooms, connect to one of them, make that the current room, mark it "connected", and repeat.
5. While there are unconnected rooms, try to connect them to a random connected neighbor (if a room has no connected neighbors yet, just keep cycling, you'll fill out to it eventually).
6. All rooms are now connected at least once.
7. Make 0 or more random connections to taste; I find rnd(grid_width) random connections looks good.
8. Draw the rooms onto the map, and draw a corridor from the center of each room to the center of each connected room, changing wall blocks into corridors. If your rooms fill most or all of the space of the grid, your corridors will very short - just holes in the wall.
9. Scan the map for corridor squares with 2 bordering walls, 1-2 bordering rooms, and 0-1 bordering corridor, and change those to doors.
10. Place your stairs up in the first room you chose, and your stairs down in the last room chosen in step 5. This will almost always be a LONG way away.
11. All done!

   Rogue also has "gone rooms", which just put a corridor space instead of the room, and draws L-shaped corridors instead of straight lines, but those are just flavor.

   This algorithm also has the virtues of being extremely fast (even on MUCH bigger grid arrays than 3x3), and guaranteed to succeed.

[cxong]

Other algos:

• Perlin terrain/island
• Building interior
• Geomorphs

[cxong]

• Rooms and mazes
• Randomly place rooms, fill the empty space with a maze, connect everything up, remove dead ends

[cxong]

• Overlapping rooms generator
• Somewhat inspired by a custom algo, start by generating rooms of random sizes, which will overlap; then choose random ones to place, from smallest to biggest, allowing overlaps, then connect up the different regions

[cxong]

• Evil Scientist's Cellular Automata

A very nice extension to normal CA, where selecting cells at random instead of doing the whole thing in phases allows for more flexibility. The corridor connection is also a great feature to have.

Also good to consider the extensions that Cogmind implemented, namely the "Mines" variant, with the addition of rectangular rooms

[cxong]

• Path of Exile generator

[cxong]

Some cool algorithms here: https://github.com/marukrap/Procedural-Map-Generator

[cxong]

• Zelda-style lock and key dungeon. The structure is tree-like with a main branch leading to the boss and treasure, but there are locks along the way which have keys on side branches. Great for linear gameplay

[cxong]

https://github.com/AtTheMatinee/dungeon-generation

[cxong]

• Snaking algorithm

[cxong]

• DLA