After a several month absence from work on my Wa, my personal roguelike project, I decided to get back into it. One of the hard parts of picking up a dusty project is re-familarizing yourself with the code. So, I decided to write an article about my cave generator since it would force me to read, think about and understand my code. I may later add a basic (and most likely incorrect) algorithm analysis.
I was tipped off to the idea of using cellular automata rules to generate a cave by links from the Roguelike Development site. I didn't find any code to use, so I read a bit about how the rules work and from that whipped up this method fairly quickly. I previously had a cave generator using a fractal method, but although I found an algorithm I was able to port to Python, I frankly didn't understand it and I feel much more comfortable with code that I 'get'. The CA method seems to be a fair bit faster as well.
The algorithm has three phases:
1. Create the initial map
I start off with a rectangle, add a border of permanent (in the game they'll be non-diggable, meltable, etc.) and randomly
place a number of empty floor squares on the map. After some experimentation, I decided that starting with around 40% of your
squares as floors yields a nice looking cave system.
Note that in theory, this could take a long, long time. I'm selecting random points on the map to add floors to, so if I
randomly get many collisions (picking a square that is already a floor), it could take a fairly long time. In most cases, though, it
shouldn't be too bad. Even when I am adding the last square, the probability of collision is about 0.4. Even if it were
0.5 everytime I was laying a floor square, on average setting up the initial map would take 2N operations (where N is the number of squares
on the map) on average. There will be few collisions while there aren't many floor squares, so it will require far fewer operations in most cases.
In any case, I haven't run into any issues during testing.
From one sample run, I got this for my starting conditions:
2. Run a cycle of CA rules through the map# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . # # # . # # # . # . # # . # # . # . # . . # # # # # . # # . # . . # . . . . # . # # # # # # . . . . . # # # . # # . # # # . . # # . # # # . . # . . # . . . # . . # # # # # . . . # . . . # # . # # . . # # . # # . . # # # # # # # . # # # # . # # # . # . # # # # # # . . # # . # . # # # # . . # # # # # . # # # # # # . # # # . . # . # . . . # . # # # # # # . . # . # # . . # . . # # # # . # . # # # . # . # # . # # # # # . . # . # # . . . # # # . # . . # # # . . # # # # . # . . # # # # . . # # # # # . . # # . . # . . . # # # # . . # # # # . . . . # . # # . . # . . # . # # # . # . . # # . . . . . # . . # # # . # # . . # . # . . . . # . . # # # # . # . . . . . # . # # . # # # # . . # . . . # . . # . . # # . . . . . # . . . . # . # . . . # . # # # . # # # . # # # # # # # # . # # # . . # # # # # . . . . # # . # # . . . . # # . . # # # # # # # # . # . # . # # . # . # . . . # . . . # # # # # . # . . . . # # . # . # . # # . . # . # # # . . . # # . # # . # # # # . # . . . # # . . # . # . # # # . # # . # # # . # . # . . . . . # # . # . . . . . # # . . # # . . # # # # . # . # . # . . # # . # . # # . . # # # # . . # # . # # # # # . # # # # . . # . . . # . . # # . # # . . # # . # . # # # . # # . . # . . # . . # # # # # . . . . # . # . # # # # # # . # # # . # # . . # . # . . # # . . # # # . # . . . # # # . . . . # # # # . . . # # . # # # . # # . # . . . # # # # # # . . # # # # . . . # . . . # . . . # # # # . # . # . . # # # # # . # . # . # # . . . # # . # # . # # . . # # . . . # # # . # # # . # . . # . . # . . # . # # # . # # . . # . # # # # # # # # . # # # . . # # # . . . . . . # . . # # # # # # # # # # # . . . # # . # . # # # . # # # . . # . . # # # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
We get one large cave area, with six small areas which are cut off from the main room. Joining them together turns out to be the trickiest part of the algorithm.# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . # # # # # # # # # # . . # # # # # # # # # # # # # . . . . . # # # # # # . # # # . . # # # # # # . # # # # # . . . . . . # # # # # # # # # . . . # # # # # # # # # # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # . . # . . . . . # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . # # # # # # # # # # # # # # # . . # # # # . . . . # . . . . # # # # # # # # # # # # # # # . . # # # # # . . . . . . . # # # # # # # # # # # # . . # # # # # . . # # . . . . . . . # # # . . # # # # . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # # . . . . # # # . . . . # # # . . . . . . . . . . . . . # # # # # # # # # # # . . . . # . # . . . . . . . . . . . . # # # # # # # # # # # # . . . . # . . . . . . . # # . . . . # # # # # # # # # # . . . . . . . . . . . . . . # # . . . . # # # # # # # # . . . . . . . . . . . . . # # . . # # . . # # # # # # # # # # . . . . . . . . . . . # # # . . . # # . # # # # # # # # # # . . . . . . . . . . . . # # . . . # # # # # # # # # # # # # . . . . . . . . . . . . . # # . . . # # # # # # . # # # # # # . . . . . . . # . . . # # # . . . . # # # # . . . # # # # # . . . . . . . . . . # # # # . . . . # # # # # . . # # # # . . . . . . . . . . . # # # # . . . . . . # # # # # # # # # . . . . . . . . . . . # # # . . . . . . . # # # # # # # # # . . . . . . . . . . . . # . . . . . . . # # # # # # # # . # # . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # . . . # # # . # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
############ # #2 # # 1# # ############This means the player from move from 1 to 2. (I may do it Nethack-style where a burdened player can't move that way)
A nice-looking, fully connected cave area! A 30X30 cave typcially takes .3 - .4 seconds to generate on PIII-500Mhz desktop at work, which isn't too bad. If performance proved unacceptable for larger maps on slower machines I would consider porting the cave generator to C. Python makes it fairly easy to compartmentalize parts of your code this way.# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . # # # # # # # # # # . . # # # # # # # # # # # # # . . . . . # # # # # # . # # # . . . # # # # # . # # # # # . . . . . . # # # # # # # . # . . . # . # # . . # # # # # # . . . . . # # # # # # # # . # # # # # # . . . # # # # . . # . . . . . # # # # # # # # # . # # # # # # . . # # # . . . . . . . . . . # # # # # # # # . . # # # # # . . # # # # . . . . # . . . . # # # # # # # # # # . # # # # . . # # # # # . . . . . . . # # # # # # # # # # # . . . # # # . # . . # # . . . . . . . # # # . . # # # # . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # # . . . . # # # . . . . # # # . . . . . . . . . . . . . # # # # # # # # # # # . . . . # . # . . . . . . . . . . . . # # # # # # # # # # # # . . . . # . . . . . . . # # . . . . # # # # # # # # # # . . . . . . . . . . . . . . # # . . . . # # # # # # # # . . . . . . . . . . . . . # # . . # # . . # # # # # # # # # # . . . . . . . . . . . # # # . . . # # . # # # # # # # # . . . . . . . . . . . . . . # # . . . # # # # # # # # # # . # # . . . . . . . . . . . . . # # . . . # # # # # # . # . # # # # . . . . . . . # . . . # # # . . . . # # # # . . . . # # # # . . . . . . . . . . # # # # . . . . # # # # # . . # # # # . . . . . . . . . . . # # # # . . . . . . # # # # # # # . . . . . . . . . . . . . # # # . . . . . . . # # # # # # # . # . . . . . . . . . . . . # . . . . . . . # # # # # # # # . # # . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # . . . # # # . # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #