*Edit July 28
I've been happy with this little cave-generator that i made. I might want to use some of it for Ludum Dare this weekend, so I am releasing the current code under the creative commons license.
You can try playing it now! it takes a few seconds to generate a level. There is no "win" state currently, but i envision a game where you have to avoid obstacles, collect stuff, and climb to the top of the cave.
I am using the algorithm i describe below, with a few improvements. If the cave that gets generated is "empty," which would make it impossible to climb, the algorithm will stick some bridges and ladders to climb into the structure. This process is dynamic, so if the cave is dense fewer will generate. Likewise, if you have a very dense cave, there is a safety-check that will make sure the cave can be completed by punching holes through blockages.
If you are interested in using some of this code and have questions, please let me know. The level-generation is almost entirely separate from the character code, so you can choose one or the other. If you are interested, I recommend looking at the callback functions (_init, _update60, and _draw) to understand the basic flow first. There is a lot of code here, about 3500 tokens, but most of it is lumped in the level generation and can be kept as is.
I imagine this being useful for quickly banging out a metroidvania or something along those lines. I hope you enjoy!
-PBG
Howdy,
I recently started making a little game about a critter who falls into a cave and has to climb out. I wanted to create a big world, but I didn't want to actually design it, so i wrote a little script to generate a large cave-like structure.
The algorithm is pretty slow - it is based on a paper i read in grad school (but cannot remember) for modeling the nucleation and growth of particles in solution. I start with an empty space (64x128 array of zeros) and first create walls by making all of the border values 1. Then, I 'seed' the space by randomly selecting a fraction of the array locations and setting them to 1. I then run a kinetic-monte-carlo simulation. Every step, every single '1' in the array a small chance that it will attempt to move 1 space in a random direction. In chemistry, this represents the random movements small particles or even molecules will make in solution, brownian motion.
If a '1' element in the array is next to another '1', a stickiness factor is applied, making it harder for the element to move away - this encourages the growth of clusters. it is possible to modify this stickiness factor to create more spherical shapes, long shapes, etc. I could also seed the space with regular shapes like boxes or lines and use this algorithm to make them appear more organic.
Anyways, in the demo above, you can watch the simulation run - as it runs, you can see clusters forming. It usually takes me about 4000 frames before the level looks nice (i need to speed up the code!). There's actually a game here too - press z to hop into the caves and explore!
I cooked this up pretty quickly, and I really like how it looks. I will definitely flesh this out into a full game, but I thought this was a fun little demo so I decided to share.
Thanks!
PBG
Neat! All the math kind of goes over my head but it's interesting.
For the in game part, it looks like you can jump infinitely. Is this intentional? It makes it easier to explore.
Enargy,
Yeah, the infinite jump is kind of a debug tool right now - this was more to demonstrate how the game might eventually look than to be a stand-alone game.
I will remove flying once I've finalized the game - right now it lets me explore the levels easily and recover from a fall quickly.
Great!
Very interesting indeed, especially the scientific background motivation!
I was looking for something just like this. I will try your code in a platform dungeon game I'm working on.
Thanks for sharing it! :)
@dw817 I never saw your post, sorry for not getting back to you. This version of the algorithm does not guarantee traversability, but the finished version does. Check out Hungry Harry's climb for a version that has guaranteed end states. https://www.lexaloffle.com/bbs/?tid=30153
[Please log in to post a comment]
