Dungeon Excavation Using a Random Walk 🌄
UPDATE: The implementation for this project has changed, however this article's explanation is still valid. The update post can be found here: Landmass Generation using Random Walks.
Notice: The BT is currently on hold, but will be completed. This is a reminder to myself.
Currently getting back into a Dungeons and Dragons vibe by procedurally generating dungeon layouts using a random walk.
Excavation ⛏
I set out to map the overhead layout of a dungeon using a random walk where previously visited locations may be visited again. The walker is equally likely to move left, right, up and down (25% chance, I think). I implemented this solution in the terminal before tackling a graphical implementation using PyGame. Find the project on github here.
Walk the Walk 🚶
A m-by-n grid was constructed with all values initialized to zero, which indicate a wall or unexcavated cell. Once the random walk commences the middle cell at grid[row_length/2][column_length/2] is set to 1, which is where the walker starts. The random walk will continue for k-steps specified by the user. My spin to the random walk is that once the walker revisits an already visited cell, that cell's value is incremented by 1. So the grid would consists of integers greater than or equal to zero, where values greater than 1 could be interpreted as changes in elevation. This enhances the creativity of the graphical implementation later on.
The Results of Excavation 🔷
The excavated dungeon is represented by an m-by-n grid generated by the random walk. A visible region was constructed 20 pixels away from the top and left edge of the screen and cells from the grid will be drawn inside this visible region.
Earlier, cells in the grid could have values greater than 1 indicating (possibly) changes in elevation. Using this information, I developed a method that would decrement the RGB values of the (set color) of a cell that has a value greater than 1. However, I also wanted a way for color to "spill" over when the RGB values dropped below 0 or rose above 255. The method color_spill does just that, if while decrementing RGB values and they happen to drop below zero the Red would spill into Blue, Green would spill into Red and Blue would spill into Green. This color spill would happen (in a loop) as long as one of either Red, Green or Blue is below zero or above 255. Doing a random walk for a large amount of steps, example 10000 steps in a 50-by-50 grid, will show the color changes as described above as there is an increased likelihood that the walker will revisit previously visited cells.
 |
| A simple dungeon with possible changes in elevation indicated by darker cells |
Why Stop at Just Dungeons? 🗺
While experimenting with larger m-by-n grids and increasing steps, I found that the graphical representation of these grids closely resemble overworld maps akin to those in Final Fantasy (maybe). Currently, this implementation can render a 180-by-180 grid with up to 200000 steps for the random walk. Going above 180-by-180 renders nothing on screen, which I can only assume is due to the cells being too small. Here is a nice example of an overworld map generated by a random walk of 200000 steps in a 180-by-180 grid
 |
| Hey, its Narnia? |
The yellowed regions on the map are a result of a color spill where the set value of a cell, given by RGB(255,255,255) has decreased to below zero and therefore the color spills over as described earlier. In the next image, if the cells were of a purplish color it would produce color spills of green, shown here
 |
| Color spills for different default cell color |
The Future of The Lazy Dungeon Master 🎩
I designed this tool so that I wouldn't have to prep too much for my next DnD session. I have also developed this as a way to keep my interest in DnD and TTRPGs alive as I have been on a long hiatus from DMing. Currently I am working on documenting my code and adding some more improvements to the random walk. My plans for the future are to research more procedural generation techniques to produce even more tools for the lazy DM. I will also be working on a general menu framework for PyGame for all of my future graphical projects.
Comments
Post a Comment