[Prototype] Procedural Cave Generator
Like I've mentioned before I have a real soft spot for procedural games, so I thought I'd read up a little on procedural content generation and give it a go myself. What I have below is what I managed to put together in the last 3 days, and though it's quite rough, I think it's quite neat (a mother always does :)
Here's a link to the Cave Generator for those who like hitting a button and seeing random things appear on the screen ;)
Procedural Cave Generator
"R" to generate a new stage.
"P" to toggle Perlin Noise map.
"Esc" to exit.
Key:
- White Line: Solution Path for that cave.
- Purple Cell: Teleporter, created in pairs and link to each other by the purple line.
- Purple Line: Shows link between teleporter pairs.
- Door: (Red, Green, Yellow and Teal) Teleporter that needs a corresponding coloured key to work.
- Whitened Cells: Unused Key Points in cave.
Quick description of the methods used:
1.) Firstly, I generated a cave system using Cellular Automata.
2.) Next, using flood filling, I find each cave that generated and record their size as well as their bounding box.
3.) Then I look for 8 Key Points that are more or less evenly spaced and on the perimeter of each cave. These are just cells that are closest to the corners of the bounding box, or the midpoint on the bounding box edge. These are the transparent white cells you'll find around the perimeter of each cave. They sometimes overlap, but that's fine.
4.) In order to get the most out of each cave, I calculate the shortest path between each Key Point, and then choose the longest one as the solution path for that cave (White Line).
5.) Cave are then ordered from large to small and are then assigned what type of cave they will be. The biggest cave will always be the Main Cave. If the second biggest cave meets some size requirement, it becomes the Secondary Main Cave and part of the solution path by linking its start to the Main Cave's end (Via Teleporter - Purple Line). All subsequent caves are also checked for size, and if the requirements are met, become Bonus Caves (Max of 4).
6.) Now we connect the Bonus Rooms and place their Keys so they can be reached. First I create a list of all the caves that can currently be reached, in the beginning this is just the Main Cave (and the Secondary Main Cave if the size requirement were met). The first Bonus Room Door and its Key may be placed in any of the caves that can currently be reached, and once they have been placed that Bonus Room becomes part of the caves that can be reached. This is then repeated for each Bonus Room.
7.) Lastly a Perlin Noise map is generated. It's values will later be used as a probability map for the spawning of enemies and treasure (not in this build), ensuring that they are not evenly distributed across the stage, but occur rather in clumps.
And there you go, my "Hello World" into procedural content generation :D If my explanation is confusing, shout at me until I make it understandable.
Here's a link to the Cave Generator for those who like hitting a button and seeing random things appear on the screen ;)
Procedural Cave Generator
"R" to generate a new stage.
"P" to toggle Perlin Noise map.
"Esc" to exit.
Key:
- White Line: Solution Path for that cave.
- Purple Cell: Teleporter, created in pairs and link to each other by the purple line.
- Purple Line: Shows link between teleporter pairs.
- Door: (Red, Green, Yellow and Teal) Teleporter that needs a corresponding coloured key to work.
- Whitened Cells: Unused Key Points in cave.
Quick description of the methods used:
1.) Firstly, I generated a cave system using Cellular Automata.
2.) Next, using flood filling, I find each cave that generated and record their size as well as their bounding box.
3.) Then I look for 8 Key Points that are more or less evenly spaced and on the perimeter of each cave. These are just cells that are closest to the corners of the bounding box, or the midpoint on the bounding box edge. These are the transparent white cells you'll find around the perimeter of each cave. They sometimes overlap, but that's fine.
4.) In order to get the most out of each cave, I calculate the shortest path between each Key Point, and then choose the longest one as the solution path for that cave (White Line).
5.) Cave are then ordered from large to small and are then assigned what type of cave they will be. The biggest cave will always be the Main Cave. If the second biggest cave meets some size requirement, it becomes the Secondary Main Cave and part of the solution path by linking its start to the Main Cave's end (Via Teleporter - Purple Line). All subsequent caves are also checked for size, and if the requirements are met, become Bonus Caves (Max of 4).
6.) Now we connect the Bonus Rooms and place their Keys so they can be reached. First I create a list of all the caves that can currently be reached, in the beginning this is just the Main Cave (and the Secondary Main Cave if the size requirement were met). The first Bonus Room Door and its Key may be placed in any of the caves that can currently be reached, and once they have been placed that Bonus Room becomes part of the caves that can be reached. This is then repeated for each Bonus Room.
7.) Lastly a Perlin Noise map is generated. It's values will later be used as a probability map for the spawning of enemies and treasure (not in this build), ensuring that they are not evenly distributed across the stage, but occur rather in clumps.
And there you go, my "Hello World" into procedural content generation :D If my explanation is confusing, shout at me until I make it understandable.
Thanked by 1Boysano
Comments
If we look at most side scroller games we find each level is of course designed to either teach the player a new ability, challenge them or make a certain creative or narrative point.
However, the convenience of always being able to complete a level because its designed for you to complete isn't always how the real world always works and of course we rule that out in the name of playability and there's nothing wrong with that.
Perhaps, however instead of designing levels to suit the player what if the player was designed to tackle the levels. What if the players could expand their own abilities creatively and attempt to solve procedurally generated situations. I feel there is a difference between playing a level designed to be beaten and a procedurally generated level that's entirely up to your creativity to solve.
What if its ok if you cant beat a procedurally generated level and let someone else come in and try with their character...
I have that soft spot for procedural generation as well and i think its because of curiosity, we always think that if we can write a code that can do something we cant really predict that will lead to this unknown world. I sometimes feel we utilize that but then hamper it, it cant be too unpredictable otherwise we cant play through it. Maybe the player just has to adapt maybe we as developers have to adapt and let that go. We have hundreds of games that already take extra caution to not irritate the player. I think we could maybe let go of that restriction a bit and that that could lead to something else, something different.
Thank you Pieter for sharing this.
I downloaded and had a look at the demo.... mmhh this was done in Gamemaker? Nice.
Thanks for sharing this. I hope you find the inspiration/time to take this further into something more interactive in the future. I have a similar post on the procedural level topic here.
I'm happy that this little experiment was of some use to other people. My hope was that this would spark some discussion on procedural content generation, and if anyone has some links to good reading material on the subject, please post them below.
Here are a few links I found while reading up on the subject:
noelberry.ca/2011/04/procedural-generation-the-caves
reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/
roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation
journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/
I love the concept of PCG, and still want to make a game based on it (and not just randomization), just to find the time :)
As @konman says I like the idea of making a game, which I can play myself and be surprised with it. Many games are so polished or planned, that once you are done cooking it you don't want to play it. Maybe when I'm big one day I'd make one for myself to play haha
Do you mind us using the GML? Modifying it, etc?
@Boysano I've been using Game Maker now for 6 years, so I've become very comfortable and fast using it, and it's always been able to translate my ideas onto the screen.
There are plenty of more powerful tools out there, but if you have to be a jack of all trades it's better to use the simpler ones :D As I'm primarily an artist it's perfect for me.
I can do it, it is just a matter of time priority, etc.
For a pet project which is on hold (Meemo's Planet), a year ago I made a procedural map generated world with biomes, etc. But it was not procedural enough to my liking, I should really redo it now that I can do more with GMS.
What I meant is sharing is caring, and I would not mind working together on GMS stuff in my innovation time, etc.