Hack Dungeon Generator
Hack’s (1982) dungeon map generator.
Dungeons
Dungeons are one of the key elements of CRPGs; its right there in the name “Dungeons & Dragons”, the progenitor of all these games.
The earliest CRPGs hand authored their dungeons but around the time of Rogue, we started to see more experiments with how to have the computer design the dungeon design.
The Dungeon generator featured on this page is from the game Hack from 1982. A game that looked at Rogue and wanted to do better - less grid like rooms, more variance in the dungeon layout.
Hack was modeled on Rogue and used | and - for walls - I’ve swapped these out for the more “modern” # glyph for walls. . is the floor and + and doors all pretty standard Roguelike iconography.
You can use these generated dungeons in your own games - video or tabletop.
How Hacks Dungeon Generation Works
Here’s a brief high level overview of how this all works.
- For each corner of the map try to place a randomly sized room.
- Sweep from left to right dropping in extra rooms where ever they fit. Repeat until there are at least six rooms total.
- Sort the rooms left to right. Then connect each room to its neighbour in the sorted list.
- Draw corridors from room to room, adding doors at the start and end points, where the corridors intersect the rooms.
- Dig additional corridors between random rooms. These may dead-end.
That’s the high level flow, next we’ll look at a pseudo code implementation of the algorithm that roughly matches that of the original game.
0. Setup the Level
Hack was a terminal-based game so it’s level size matches the terminal output an 80 by 20 grid. Every cell in the level starts as solid rock. All randomness comes from one seeded generator, so the same seed will generate the same level.
CSHARP
1Level Generate(int seed)2{3 var rng = new Random(seed);4 var map = new Map(width: 80, height: 22);1. Place the Corner Rooms
Now we’ve set up the level area, time to add the corner rooms.
Place four corner rooms. The corner edge is fixed; the room grows inward to a random size. Since these rooms are placed first and the map is large enough, they cannot overlap.
CSHARP
1 map.AddRoomInCorner(2 TopLeft, wide: rng.Range(3, 7), tall: rng.Range(4, 8));34 map.AddRoomInCorner(5 TopRight, wide: rng.Range(3, 7), tall: rng.Range(4, 8));67 map.AddRoomInCorner(8 BottomLeft, wide: rng.Range(3, 7), tall: rng.Range(4, 8));910 map.AddRoomInCorner(11 BottomRight, wide: rng.Range(3, 7), tall: rng.Range(4, 8));2. Fill in the Middle
Place rooms in the middle of the level. Sweep the middle of the map from left to right, attempting to place extra rooms at regular intervals where there is enough empty space. Keep going until there are at least 6 rooms and stop if there are 14. In theory this loop could run endlessly but in practice that’s very unlikely. Something you might to fix in your own implementation. Note: AddRoom can fail (TryAddRoom might have been a better name choice but I need to conserve line space!).
CSHARP
1 while (map.Rooms.Count < 6)2 {3 bool reachedLimit = false;45 int row = rng.Range(3, 5);6 while (row < 15 && !reachedLimit)7 {8 int col = rng.Range(4, 6);9 while (col < 70)10 {11 var anchor = new Point(col, row + rng.Range(-2, 2));1213 if (map.IsRock(anchor))14 map.AddRoom(anchor,15 wide: rng.Range(3, 12),16 tall: rng.Range(3, 6));1718 if (map.Rooms.Count >= 14)19 {20 reachedLimit = true;21 break;22 }2324 col += rng.Range(7, 8);25 }2627 row += rng.Range(4, 5);28 }29 }3. Sort Rooms and Connect with Corridors
Sort the rooms from left to right and connect each to the next, forming a single chain that reaches every room.
CSHARP
1 var roomChain = map.Rooms.OrderBy(room => room.Left).ToList();Connect each room with a corridor. If a corridor runs off the edge of the map, the entire process just repeats from the start!
CSHARP
1 for (int i = 0; i < roomChain.Count - 1; i++)2 if (!CarveCorridor(map, rng, 3 from: roomChain[i], to: roomChain[i + 1]))4 { 5 return Generate(seed + 1);6 }78 // Add extra corridors between random pairs of rooms.9 // Up to roughly extra corridor one per room.10 // They may dead-end.11 foreach (var (from, to) in RandomDistinctRoomPairs(rng, map.Rooms))12 CarveCorridor(map, rng, from, to, allowDeadEnd: true);1314 return map.ToLevel();15}1617// Dig a corridor between two rooms, one cell at a time.18// Cut a door at each end.19// The digger tracks position, heading, and a target.20// The target is a cell on the destination room's wall.21bool CarveCorridor(Map map, Random rng, Room from, Room to, 22 bool allowDeadEnd = false)23{24 var d = map.StartDiggerOnWallOf(from, facing: to);25 CutDoor(map, rng, d.Position);2627 while (d.Position != d.Target)28 {29 if (allowDeadEnd && rng.OneIn(35))30 return true;3132 // Turn only after passing the target on the current axis. 33 // This gives the corridors their `L` and `Z` shapes.34 if (d.OvershotTargetOnHeading())35 d.TurnTowardTarget();3637 var next = d.CellAhead();3839 if (map.IsEdge(next))40 return allowDeadEnd;4142 if (map.IsRock(next))43 d.CarveInto(next);44 else if (map.IsCorridor(next))45 d.StepOnto(next);46 else47 d.SlipAlongside(next);48 }4950 CutDoor(map, rng, d.Position);51 return true;52}5354// Place a door a corridor reaches a room wall. 55// ~1 in 8 doors are secret.56// Skip placement if another door is within a cell.57void CutDoor(Map map, Random rng, Cell wall)58{59 if (!map.IsWall(wall) || map.HasAdjacentDoor(wall))60 return;6162 map.Set(wall, rng.OneIn(8) ? DoorKind.Secret : DoorKind.Open);63}Generator Details
- Corridors can overlap - This couldn’t happen in Rogue. Leads to more interesting dungeon paths including junctions and loops. There’s no intentionality behind the design though, it’s all quite random.
- Dead Ends - Corridors can dead end by design.
- Generation Jank - there’s no hard guarantee the sweep part of the algorithm will end - though in practice it pretty much always will. Also if a corridor goes out the bounds of the level, everything is thrown away and we start again from scratch!
Generated Dungeon Levels
Some of the possible levels generated by this algorithm.
###### ######### #....# ............................... #.......# #....# .############# .############. . ############## #.......# #....#...#...........#..#..........#......... #............#.+.......# #....+...#...........#. #..........+. ######..#............#.#.......# #....# .+...........+..+..........#. #....#..+............#.#.......# #....# #...........# #..........#..#....#..#............#.##+###### #....# ############# ############ .#....#. ##########+###.. .... ###### #....#. ................... #....+...#########+####. ###+## #....# .#............+. #....# ###### .+............# #....# #............# #....# ############## #....# ######
########## ####### ###### #........# ######### #.....# #....+. ######## #........# .+.......# #.....+....#....#. ######## #......+. #........# .#.......# #.....# .#....#. #......+......#......#. #........+..#.......# #.....# .+....+. #......# .#......#. #........# #.......# #.....+....#....#. #......# .+......#. #........# #.......# #.....# ######. #+###### #......#. ####+##### ######### #.....# .... .. #......#... ........ . ####### .####+### ######## .##+######### .. .+......# .+..........# #+#### #......# #..........# #....# #......# #..........# #....# #......# ############ #....# #......# #....# ######## ######
......... ##### ##############.......... ########### #...# #............#........######### ######### .#.........# #...# #............+.######.+.......# #.......# .#.........# #...# .+............#.#....#.#.......+. .+.......# ...#.........# #...# .#............#.#....#.#.......#. .#.......# . #.........# #...# ...#............#.#....+.#+#######. .####+####... #.........# #...# . #............#.+....# .. ... . . . ###+####### #...+.. ############## #....# #+####.#####. . . .... #...# #....# #....+.#...#. . . .. ##### ###### #....#.+...+. ... . ##+### #....# #...# #####+##. #....# #....# ##### #......+. #....# #....# #......#........ #....# #....# #......# #....# ###### ######## ######
######## ############# #......# #...........# #......# .+...........# #......# ###### .#...........# #......# #....# ########### .#...........# #+###### .+....#.+.........+. ######### .#+########### . ..#....#.#.........#. .+.......+.... ........... . . #+#+##.#.........#...##### .#.......#......#####. .. .. ... ... .########### .#...#...#.......# ...#...#. #####+## ##+## . ... .... .+...#. ######### .#...# #......# #...+.. ... . #...+. .+...# #......# #...# ... . #...# #...# #......# #...# ######+##. #...# #...# #......# #...# #.......#. #...# ##### #......# ##### #.......#. ##### ######## #.......# #########
###### ......................####### ####### #....+...############## .+.....+.... ..................+.....# #....# .+............# ..#.....# . #.....# #....+...#............#.......#.....# ... ###### .+.....# #....# #............+.......#.....# . #....# .#.....# #....# #............# ####### ..#....# .#.....# #....# #............# .#....+.. .####### #....# ############## #....# . .. . ###### #+####....... . .. ...... .##+######.#+#### .+.......#.#....# #.......+.#....# #.......# #....# #.......# #....# #.......# ###### #########
####### ############# ############ #.....#.+...........# #..........# #.....#.#...........# #..........# #.....#.#...........# ..... #..........# #.....#.#...........# ########............................#..........# #.....#.#...........#.#......# #####.+..........# #.....#.#######+#####.#......# ...... #...#.#..........# ###+###. . .#......# #######+##### #...+.#..........# .. ... ... .#......+.......+...........# #...#.######+##### ##+##. . ...#......# #...........+..+...#. .... #...#. ... . #......# #...........#..#...#. . #...# .. ... ######## #############. #####............. #...# #+######. ... ##+##### #...# #......#. . #......# ##### #......#................................ #......# #......# #......# ######## ########
############# ############## ####### #...........# #............# ########## #.....# #...........# .+............# ###### #........# #.....# .+...........# .#............# .+....# .+........# #.....#..#...........#...#............# .#....# .#........# #.....#. #####+#######. ##+#####+##### ...#....# ...#........# #######. ... ... ..................... ##+### . #........# . . .. . .##+#####......................... #........# . . #########... .#......#..... . #+#####. #........# ... . #.......#. .#......+.......... #.....#. #+######## ####+##. #.......#. .#......# #.....+. ..... #.....#. #.......#. .#......# #.....#.............. #.....#. #.......#. .#......# ####### ##+#+##### #.....+. #.......#.......#......# #........# #.....# #.......# ######## #........# ####### ######### #........# #........# ##########