It’s time to work on one of the main features of the game — the dungeon generator. I’m sure there will be many posts on this alone. I already made the very basic framework and have a plan of expansion.
Now, I cannot spend weeks and months on the dungeon generation algorithms (even if I want to). So the generator is a mix of hard-coded rules, presets and certain procedural randomness. As I mentioned before, a level is a collection of rooms in a grid. Each room has a grid of tiles. This means rooms are all the same size. Rooms are just templates/presets of tiles. So the generator builds a map of rooms and then places tiles for each room. The resulting “dungeon” is all tiles, but it’s quite obvious it was made from pieces (at this point, anyway; I will likely touch on this later). Another reason is that I want a simple minimap, so a grid is great, but I will talk about that later.
Here’s the first “real” version of the dungeon generation (if you can call it that already):
The generator would run in steps. A single step is what I call a “branch”. A branch is not necessarily an actual branch of corridors or anything, but more of an algorithm to generate a certain pattern of rooms. For example, the above is a “straight” branch, which just places rooms in a line. Could be circular, could be area, could be a single room, etc.
This approach is top-down design, more or less. The plan is that I decide on the layout in broad strokes, then append smaller strokes, then fill out details and polish it up. So may be I build 3 main corridors, then offshoot 10 small ones, then add 15 side rooms, then sneak in a couple secret treasure rooms.
Further expanding on this concept, here’s a “snake” branch:
This is basically a multi-branch branch, which is a branch that is internally several other branches. So a snake branch is several straight branches in alternating directions; here 3 segments of length 4.
At this point, I’m anticipating some serious debugging and testing of algorithms, so I’m getting ready early by having all the outputs nicely (to me, anyway) presented:
Moving forward, I need to start assigning room designations correctly. I can already specify regular, goal, and start rooms, so I am expanding that to primary, secondary and tertiary rooms as well as primary and secondary hubs — these are just nomenclature for building branching paths.
So here is a “dungeon” with correctly specified and selected rooms — start to hub, to another hub, to end goal:
And more debugs with better specific branch knowledge and room selections:
I guess I have flashbacks to my early programming days where I spent more time stepping through code than actually coding. So now I really respect good debug tools and the ability to quickly follow through a certain algorithm/process.
At this point I worked on room layouts (covered in the next blog post) that I needed to adjust to continue with dungeon generation.
Now to add more steps to the dungeon generation. For this particular layout, I would keep track of hubs and then spawn extra branches from there:
I am able to add branches like this, because the step that generates the dungeon layout is more or less abstract — it creates a node grid map and these nodes are mutable. Not until the whole layout is generated, do I start selecting rooms to match. This nicely separates and encapsulates the generation. (The nodes could be even more abstract, basically a node graph, but I want to avoid algorithms that need many iterations and are “noisy”.)
Extending the above to keep track of directions and choose random directions (the rooms with dots are secondary):
So let’s add some secondary branches and a some tertiary offshoots (the rooms with even bigger dots are tertiary):
Now we’re looking more like a dungeon! At this point, I can go wild with creating branches with just the few tools I already have. The top level code for this is very straight-forward. Of course, this needs a whole lot more tweaking and de-randoming to allow more organic layouts. I am not quite sure how to achieve the sort of results I’m looking for, but I’m confident I can get at least part way there with certain generation rules and options. For example, keeping scores for each room — how many connections it has, how many further rooms, how far it’s from the start or goal, etc. That way I can “randomly” choose dungeon areas in need of additional branching and features.
I know I’m reinventing the wheel with some of this. But at the same time, I doubt a complete dungeon generation solution will fit my needs and will likely take longer to learn and integrate.