Generate Too Much, Then Delete
My second engine shipped a dungeon crawler, and its level generator is the only place in twenty years of my code where the abbreviation appears in the identifiers:
void Dungeon::pcg();
void Dungeon::pcgRooms();
void Dungeon::pcgDoors();
void Dungeon::pcgRoomCull();
void Dungeon::pcgDoorCull();Five passes and about thirteen hundred lines. What it shows is that not one of those passes tries to produce a correct dungeon. Every guarantee the finished level has comes from something being deleted while a test watched.
This continues the series taking one system at a time out of my custom engines.
The Outer Loop Throws Away Whole Dungeons
The driver is four lines of intent:
while((currentDepth < minDepth || currentRooms < minRooms) && dungeonTries++ < 100){Build an entire dungeon. Measure how deep it got and how many rooms survived. If either falls short of the minimum, discard all of it and build another. Give up after a hundred attempts and ship whatever the last one produced.
Writing a room placer that always yields a dungeon at least six rooms deep is hard, because depth is a property of the finished graph and the placer works one room at a time. Writing a placer that usually gets there and then checking is easy, and the check is code that has to exist anyway, since the game needs to know how deep each room is regardless.
The cap is the part that separates this from a student version. Constraints that interact can be jointly unsatisfiable for a given bounding box, and an unbounded loop meets that condition on somebody else's machine, at generation time, with no output and no error. A hundred tries converts an unbounded hang into a dungeon that's slightly smaller than requested. The failure mode is a disappointment rather than a crash, which is the correct place to land.
Rooms Are Placed Like Space Invaders
Each candidate room gets a random size drawn until it satisfies an area constraint:
while(tmpRoom.size.x*tmpRoom.size.y<minRoomArea || tmpRoom.size.x*tmpRoom.size.y>maxRoomArea || noCorridor){
tmpRoom.size.x = Random::range(1,chunkRatio)*minRoomSize;
tmpRoom.size.y = Random::range(1,chunkRatio)*minRoomSize;Sizes are multiples of minRoomSize rather than arbitrary, so every room lands on a grid and tiles line up without any snapping logic.
The noCorridor term is a taste rule expressed as a filter. A room whose aspect ratio exceeds three to one reads as a corridor rather than a room, and corridors are allowed through only occasionally:
if(tmpRoom.size.x / tmpRoom.size.y >= corridorThresh || tmpRoom.size.y / tmpRoom.size.x >= corridorThresh){
if(rand() % 100 < 5){
//percentage chance to let it in
}
else{
noCorridor = true;
}
}Rejecting ninety-five percent of long thin rooms makes them rare without making them impossible, which is a better result than banning them. A generator that can't produce a corridor produces a level made entirely of boxes, and the occasional long room is what stops the layout reading as a grid of cells.
Placement itself is described by its own comment:
slide left until either no longer intersects with bounding box or does not intersect with other rooms, then slide right, then slide up, space invaders style
The room starts at the top center and walks. It's not a partitioning scheme and it isn't trying to be optimal. It's a packing heuristic that terminates, and combined with random sizes it produces layouts that look placed rather than tiled.
Every Possible Door, Then Fewer
The door pass connects every pair of rooms whose door-safe regions overlap. Not a spanning tree, not a chosen subset. All of them.
Door-safe regions are authored, not derived. They're metadata volumes drawn on a room in the editor, marking where a doorway may be cut. A room author decides that a doorway is acceptable along this wall and not that one, and the generator only ever proposes connections that a person already approved.
The result after this pass is a maximally connected dungeon, which is unplayable. Every room touches every neighbor it possibly can, so there's no route to find and nothing is ever behind anything else.
Then the door cull runs, and it's the pass I'd take to another project unchanged:
if(rand() % 100 < 10){
itd->active = false;
...
itd2->active = false;
if(pathfindAll()){
rooms[itd->roomId].doors.erase(itd2);
itd = it->doors.erase(itd);
}
else{
itd->active = true;
itd2->active = true;
}
}Consider ten percent of doors. For each one, deactivate both sides, run the pathfinder from the entrance to every room, and if everything is still reachable, commit the deletion. If not, put it back.
That's maze generation by edge removal, and it has a property that's hard to get any other way: every intermediate state of the dungeon is valid. There's no moment during generation where the level is broken and a later pass is relied upon to fix it. A removal either preserves the invariant and is kept, or violates it and never happened.
It's also the only formulation of this that stays correct when the connection graph is arbitrary. Carving a maze from a grid can lean on the grid's structure. These rooms are irregular, differently sized, and connected wherever two authored volumes happened to overlap, so there's no structure to lean on. Testing each removal against the actual pathfinder makes the graph's structure irrelevant.
The pathfinder used for the test is the same A* the game uses to move monsters around. One implementation, two purposes, and the level generator gets its correctness guarantee from code that was going to be written and debugged anyway.
Unreachable Rooms Are Deleted Rather Than Connected
The room cull runs the same test without the revert:
for(int i=1;i<rooms.size();i++){
if(path_success[rooms[i].roomId]!=1){
rooms.erase(rooms.begin()+i);
culled = true;Pathfind to every room, delete the first one that couldn't be reached, and start over. Repeat until a full pass removes nothing.
Connecting an isolated room is a design problem. It means choosing where a corridor should run, whether it crosses anything, and whether the new connection ruins the pacing that the door cull just produced. Deleting the room is one line and cannot introduce a new failure. The generator already overproduces, so losing a few rooms costs nothing, and the outer retry loop catches the case where it lost too many.
That's the whole philosophy stated in one pass. When a generator can overproduce cheaply, repair is a worse tool than deletion.
Authored and Generated in the Same Dungeon
One line in the driver decides where a room's interior comes from:
if(rooms[i].filename.size()) rooms[i].load(rooms[i].filename);
else rooms[i].pcgContents();A room either loads a file somebody made in the dungeon editor, or generates its own contents. Both kinds go through the same placement, the same door generation, and the same culling, because by that point a room is a size, a position, and a list of door-safe volumes regardless of where its insides came from.
This is the answer that fully procedural dungeon crawlers usually arrive at eventually. Handmade set pieces carry the parts that need authorship, generated filler carries the volume, and the layout algorithm doesn't know which is which. Getting the interface right, so that an authored room is interchangeable with a generated one, is most of the work, and it's right here because both kinds have to answer the same three questions.
The Generator Draws Itself
Between every pass, the driver does this:
window.update();
manicEngine.update();
client.render();
manicEngine.swapBuffers();The dungeon renders after room placement, after doors, after the room cull, and after the door cull. Generation is visible while it happens.
The window keeps pumping messages, so a generation that takes a few seconds doesn't make the application look frozen to the operating system. And the developer can watch the algorithm work, which is the difference between debugging a level generator and guessing at one. A room cull that removes too much is obvious in one run and nearly invisible in a log.
There's a separate pcgRender for this, so the intermediate visualization is a real feature rather than a leftover.
Difficulty Comes From the Graph
Room contents are seeded per room, and what spawns depends on how deep the room is:
srand(seed);
...
if(depth < 2){ chanceSlime = 10; }
else if(depth < 4){ chanceSlime = 5; }
else{ chanceSlime = 5; }depth is distance from the entrance along the room graph, which the pathfinder computed during culling. Using graph distance rather than physical distance is the right call. A room fifty meters from the entrance behind one door is not deep. A room ten meters away behind six doors is, and what the player experiences is the number of doors.
The weights are placeholders. Three of the four enemy types are set to zero at every depth, and the one that isn't gets rarer further in, which is backwards. The mechanism is finished and the tuning never happened, which is what a system built ahead of its content looks like.
What I'd Change
Both cull passes restart from the beginning after every single deletion, re-running the pathfinder across all rooms each time. On dungeons of this size it doesn't matter. It is still wrong, and collecting the unreachable set in one pass before deleting would be both faster and easier to read.
Room identifiers are array indices, so deleting a room requires walking every remaining room and every door to decrement any identifier above the deleted one. That hand-written renumbering is exactly the kind of loop that develops an off-by-one under maintenance. Stable identifiers with a lookup would remove the whole category.
The seed is a literal with its predecessor commented out beside it:
seed = 8;//5Fixed during development so the dungeon is reproducible, which is correct, and never given a path to being set from anywhere, which means shipping it required editing and rebuilding.
The enemy spawn loop had no iteration bound, so a room that couldn't fit its quota of enemies would spin forever. Placement inside it was bounded to ten attempts, so the author clearly knew the failure was possible and guarded the inner loop while leaving the outer one open. I fixed that while reading the code for this post, which felt more useful than describing it.
What Transfers
When a generator can overproduce cheaply, stop trying to make each step correct. Produce too much, then remove things one at a time while a test confirms each removal is safe. The invariant holds at every intermediate state, no pass depends on a later pass to clean up after it, and the test is usually something the program needed anyway.
Prefer deleting a failure to repairing one. Repair introduces new decisions and therefore new ways to be wrong. Deletion cannot, as long as something upstream produced a surplus.
And bound every loop that waits on a random process to succeed. Rejection sampling is a good technique with one failure mode, and the fix is a counter.