Generating dungeon floors in Python and checking every one
A first dungeon generator lays out a floor from a seed, and a checker with 13 hard rules and 15 scored ones decides which tries are kept.
Blobber has a first procedural dungeon generator. I give it a seed and a few parameters and it writes one floor in the same terms my phone dungeon designer uses, with rooms, links, locks, water and secret crawls. Every floor it keeps passes 13 hard checks and has been through the game’s own dungeon importer. That was the first three steps of a seven step plan. Steps 4 and 5, stocking the floors and drafting a floor from words on the designer page, came the same day and are at the end.
Why did I build the checker before the generator?
I had a knowledge base on dungeon design with a build order at the end, and it put the checker first. A generator with no way to judge its floors can’t be tuned, and I’d have no way to tell a bad seed from a bad rule. So dungeon_checks.py reads any sheet, drawn by hand or generated, and prints a report.
The hard checks all fail a sheet. Every open square has to be reachable from an entrance with the locks open, and the goal has to be reachable taking keys as they come. Every lock needs its key, switch or code reached first, and every lock has to sit on a bridge so there’s no way round it. Corner-only openings are out, rooms are at least 2 by 3, and secret panels have to be findable from a square beside them. Traps must show their tell along at least 2 straight squares. There has to be a way back from the goal, and every code has to be told somewhere on the sheet. The last check runs the game’s importer into a scratch folder and wants it to refuse nothing.
The walk is a port of the game’s own lock check, made stricter for codes. A code lock opens once the walk has reached an item, an NPC or a note holding its digits.
The 15 scored metrics each have a band. Loops should be 2 to 4, dead-end rooms 8 to 22 percent, and the critical path 30 to 50 percent of the rooms. A metric’s score is its weight times how close it is to the band, and a floor’s score is the sum. Two of them, content shares and difficulty by distance, wait until floors have monsters in them.
How does the generator lay out a floor?
A seed picks one of four cycles. The first puts the goal behind a locked door off one arc of a loop, with the key on the other arc. The second is a hub with spokes, the goal behind a code door and the code in a far spoke. The third is a loop with one arc flooded to the ankle and slow to cross, and the other arc dry and longer. The fourth is plain two ways to the goal.
My first idea was to give the rooms to the sheet layout tool and let it place them. It couldn’t lay a cycle as the main structure of a floor, so I wrote the ring myself. The generator sets the cycle’s rooms down on an ellipse and the layout tool routes the links between them first. Branch rooms then come from the dungeon kind’s room mix, followed by minor loops and covered secret crawls. Minor loops are optional, so if the layout tool can’t place one it’s dropped.
Each try takes about 10 ms, so the generator makes 40 and keeps the best-scoring one that passes every hard check. The same seed gives the same floor whatever Python’s hash seed is, and there’s a test for that.
Maps and the checker’s report at the top, then the party walking the three floors.
What went wrong along the way?
Sweeps over many seeds failed in two ways. Some floors had corner-only openings, so I added a corner test to the router. Others had an entrance blocked by the straight way out, so the router now has a fallback for the entrance.
The last problem was the importer. While there’s only one floor, a lift has no partner, and the importer refuses a lift with no partner. So the generator turns that lift into an exit in the nook, and that exit is the goal. A dry run of the importer can’t take a second floor either, which is why the import check does a real import into scratch.
Does the designer page know about new kinds of fixture?
It does now. Each row of the game’s fixture table has a designer block with a letter, a group and its editable fields. A small tool turns the rows into the palette document the page reads, and the page merges in the kinds it doesn’t know. A kind it can’t draw shows as a grey question mark instead of breaking. The palette currently comes from 8 fixture kinds, with 11 monsters and 162 items in the catalogue.
What are the numbers?
A sweep of 20 seeds gave 20 passes in 17 seconds. The first floor in the film, the lock on the other arc, is 30 by 46 squares with 15 rooms and scores 12.1 of 17. It has 2 loops, 3 dead-end rooms and one secret crawl. It misses the band on a few metrics, such as how much of the floor the critical path covers and how many landmarks it has. I’m not bothered by that yet, since stocking and tuning come later. The tests are 28 for the checker, 20 for the catalogue tool and 21 for the generator with the importer on.
The generator only writes drafts and never touches the shipped dungeon folder. I’ve filed 24 items for what the generator still lacks.
How does a floor get stocked?
Later the same day, steps 4 and 5 landed. dungeon_stock.py runs on the layout the generator keeps and adds packs, traps, chests, notes and a light level for each room. The worked example floor has 7 packs, 2 traps, 4 chests and 3 notes.
The budget is scaled from the knowledge base’s floor of 20 rooms. Packs go in 35 percent of rooms, except the start room, with a share per room kind times depth, where depth is the walk from the entrance over the farthest walk. A pack has 1 to 5 monsters and gets bigger and higher in tier with depth and difficulty, with noise so that difficulty tracks distance without being a straight line. The goal room always gets the strongest pack as its guard. Flyers and the three meter meat monster only go in tall rooms.
Traps go in 15 percent of rooms and each one has a tell. Tripwires and lasers go on straight corridor squares, where the party has to pass. Plates and overhead traps go on the square in front of the best chest. A plate trap is one floor plate of a different metal, scuffed bright at the edges, and a laser is a faint line in the drifting steam with an emitter humming at the wall. The checker’s H10 makes sure each tell is visible from at least 2 squares away.
Chests number a room in four with at least 2. Each room gets a reward score of 2 times its depth, plus 1.5 for a dead end, 2 for being behind a lock, 2.5 for the far end of a secret crawl, and the room kind’s chest chance. The best rooms get a chest and the best of them gets tier 2. Notes go in 20 percent of rooms as dry lines by room kind.
A floor can hold up to two factions, “the Meat” and “the Line”. It’s split by walk between two far rooms and each pack names its faction in its note. The generator tries 12 stockings per floor and keeps the best by the density budget and by how well difficulty follows distance.
The game can’t do a few of these things yet, so I didn’t fake them. It has no faction field, no wanderers, no pits, no way to keep a room dark from a sheet, and no way to build a readable note from a sheet’s text. Each is written into the draft for later and filed. Pits are rare, so one floor in four gets a “pit wanted” note with its tell, and wanderers are set to a low rate. Those were my answers to the open questions that morning.
How does a floor I describe on my phone come back?
dungeon_page.py reads a sheet I’ve saved from the designer page as a description. It turns the words into generator parameters: size words give a room count, with tiny at 6 and huge at 35, and there are words for difficulty, loops, secrets, light, flooding, factions and wanderers. Named rooms, a locked or flooded room and a lair are picked up too. A word it can’t place is kept as an idea and never guessed at. The tool generates and stocks a floor, then writes the draft’s fields: tiles, heights, things, a manifest of what the game has and lacks, a note on how each word was read, and a revision one higher than the sheet’s so the phone’s copy doesn’t overwrite it. It prints the database update for the main session to send and never writes to the page or the shipped dungeon folder. A sheet that already has squares drawn is refused, because growing a floor around drawn squares is the next step.
Generated files are now also written in the field order the importer writes, so importing one again gives the same bytes.
The stocked map, a pack, the trap, the chest, the drafted floor as drawn and as handed back, and the drafted floor walked.
The tests are 32 for the generator with the importer, 39 for the page tool, and 122 checks in the import fields test. What’s left is growing a floor around pins I draw and several floors in one dungeon. Two more items are filed: notes need to become readable items, and the goal is rarely seen early on the ring floors, which a short spur to a window into the goal room might fix.