Hope I'm not too late to catch this train. I've been fascinated with dungeon generation since I watched the talk the creator of brogue gave at roguelike-dev. Seems like no matter what, I always find myself for some reason making a dungeon generator. This is my latest iteration of that. I wanted to post and encourage anyone working on generation: Visualize your outputs. I have spent a ridiculous amount of hours comparing values in a print() log. It's awful, and can lead to some pain staking bugs. Especially if you don't have any custom error handling methods.
Also, try offloading your generation onto love threads. It's a great way to not have Big O Notation ruin your plan of generating beautiful maps. I have found that if I want to avoid the Big O demon, it's almost mandatory to use hash maps or some kind of linked list versus iteration. Especially when it comes to algorithms like flood fill, bfs, or anything that relies on recursion for that matter. Below is a visualization, and a good example of why it's helpful. Hope you guys enjoy.
https://jmp.sh/Z9CZ1Vq6 <- Jumpshare (Gyazo alternative) video of current generation.
I'm using a "room accretion" method, which I think maybe brogue popularized. It's a little more botched though. I could not get hallways to work without some awful O^n / efficiency issues. The method I'm using is as simple as follows:
- Generate a "room" of random size.
- "Throw" this room at the dungeon to see if it sticks.
- If the room sticks, add it to the dungeons table of valid rooms.
- Do this until certain parameters like room ratio % or # of rooms is met.
- Since rooms overlap, we process those overlapping wall tiles to determine door locations
- Pick a random "best" door, and resolve the other overlapping conflicts (Just make them walls instead)
- Analyze the map by instantiating a dijkstra source at the starting room, and building out.
I paraphrased the "generate a random room" because that alone is quite a lot to explain. But essentially I just create a shape (square, rectangle, circle, Cellular Automata blob, etc) then maybe combine it with another (Merge tile data together at center, and sometimes use offsets for something like "T rooms").
The reason I believe visualization, or step-visualization is important later on in generation is because your codebase is inevitably going to grow exponentially, and something as small as a nil reference error can cause some nasty bugs. Especially..
especially if you're using hash maps (or multiple in my case.) Here is an example:
In this photo, the visualization of my dijkstra pathing ends abruptly on the X-axis (visually y axis). The error was a nil reference to the distance property of a node... one of 3000+ nodes. I could have looked at a lot of things for that, and probably have to step through the recursion to fix it. But because of the visualization, it was quite obvious that the hash map I was referencing did not carry values past a certain amount. This was due to a small math mistake I made when changing generation size. I have a lot more examples of this.
Another reason visualization is nice, is in my video, you can visualize a lot of elements of generation that would be impossible otherwise. As mentioned previously, I offloaded generation onto a thread so that I could keep the main thread from hanging when I run into recursion issues, or other errors that don't seem to crash the main thread. (This has it's perks, and disadvantages). As a result, (if you've seen the video) You can see in the room generation that my larger rooms "favor" the right side of the screen. This could just be how random works, or there could be an underlying issue (which there is). Likewise, I can also visualize how the player would traverse the map naturally using the dijkstra visualization. Also, I can see how rooms are being attached to other rooms in case I want to tweak parameters for how often certain rooms appear. The list goes on. But some of these things would be impossible if the generation happens immediately.
This does come at the price of maybe implementing threads, but definitely implementing some method of reading changes to the map incrementally. Using spritebatches, it is actually super easy to read changes from a map -> apply only those changes to the spritebatch -> and then further reference those changes for visualization. Here is one function I have that handles most of it:
Code: Select all
-- Iterate over list of previous changes, and change tile color one at a time.
if #self.previousChanges > 0 then
for i = 1, #self.previousChanges / 10 + 2 do
local change = self.previousChanges[i]
table.remove(self.previousChanges, i)
if change then
self.spriteBatch:setColor(1,1,1,1)
if change.tile.distance then
local distance = change.tile.distance
local r,g,b,a = _HSV((distance*2)/255, 1, 1)
self.spriteBatch:setColor(r,g,b,a)
end
self.spriteBatch:set(change.id, change.quad, change.tile.wx*64, change.tile.wy*64)
end
end
end
I wouldn't recommend using this by any means, but it serves as just an example. I actually haven't put much effort into systems that handle map changes, right now it's just hard coded into the map class. But in this code (inside a love.update() call). I simply observe a stack (self.previousChanges) for any newly added changes. Newly added changes are added to the stack when I :pop() data from my generation thread. Once changes are found, I "pop" them and then set the corresponding spriteBatch quad to it's new information. In my case, I :add quads to the spritebatch at a lower alpha than 0. Then I store the `identifier` :add gives me as `change.id` as well as the `quad` and `tile` information. This is pushed into the self.previousChanges stack. That's really all there is to say about that right now because although this is a method, it's probably not the best.
Anyways, hopefully my post gets approved and you all can see this and maybe it will help in your own project! I am more than excited to answer any questions anyone has about this as I plug away. Next on my list is lakes, chasms, and then what I call "flavormachines".
