Cave Generation
Tuesday, July 15, 2014 - 11:55
Hi All,
I've created with some help from couple of sources on theory relating cave generation. I was wondering if any one had thoughts on the topic. One such topic is balance, how to handle multiple caves linkage (portals, complete removal), etc.
Here is my work in progress: http://pcmsolutions.ca/cave-gen1.html
Thoughts and ideas are very much appreciated. It's all in the name of art, well the art of programming.
Thanks!
I like the results you're getting with your current generator and I don't feel that there's any need for you to change it drastically. However, I'm going to suggest a different approach just because I enjoy these kinds of conversations.
Note that this is just off the cuff, so I can't guarantee how well it would work in practice. However, in theory, the advantage of it would be that you would be able to specify how many "rooms" the cave has, along with the general shape of the cave. If you make the nodes big and the connection width small, you could have a bunch of large rooms with small interconnecting passages. If you keep the nodes small but numerous and allow for some more variation in the connection width, you could have a cave that's made up of randomly winding passages. You could also tweak the connection generation to favor caves with lots of dead ends or a web of passages.
Your method is what most D&D dungeon generators are doing. I like the cellular automata but I can certainly see the appeal of growing caves.
Once the generation is done the hard job I think setup a tileset for use in a system and populating the map with alternate tiles and not feel weird. Sort of like you'd need a rule set, i.e since water tiles can be generated do you allow some water to movement, or wide enough to support a bridge.
Lots to still figure out on what makes the most sense. I think maybe it is easier to have someone design the level after all.
Bart's idea is sound. I used a variant based on a drunken walk, starting from a set of randomly chosen points. Didn't even bother with interconnecting passages -- simply tweaking the length of random walks was enough. I even had a nice function to make water pool in certain places (wall tiles with fewer than five neighbors would become water). Sadly I can't show you the code in action; changes in web browsers have broken it. But yeah, that works.
I'll setup a testcase for node variant @Bart suggests and see how that places out.
If your not specifically looking to roll your own, I would reccommend rot.js
http://ondras.github.io/rot.js/hp/
I used it in my PDJ game. You can see the results here:
https://dl.dropboxusercontent.com/u/141246873/PDJ/index.html
@Ryan, cute game.
I learn by doing and making a game has been on the "TO DO" list since my C64 game days.
I did the first bit that @Bart suggested.
Steps. New > Grow to see the node growth. It very simply random generates between 2-12 nodes. Then for each node runs a lovely hardcode loop 12 times. A drunkard walk between 2-5 steps in 8 possible directions. If the direction is invalid it uses the last successful coordinate to stumble on from.
http://pcmsolutions.ca/cave-gen2.html
The cave generation algorithm depends on the game/application it is used for.
E.g. if understanding "It's all in the name of art" then the caves must look beautiful. In case you want a kind of a survival game the caves should be realistic. A strategy game will require its own sort of caves. And a maze-solving game needs other kind of caves.
In my game 'Project Helena' I use 3 following approaches to (cave-like) map generation:
1. Formula-driven map generation.
2. Stamp type maps.
3. Procedural map generation (with two variants: random objects and map areas filling).
The next stage of map generation is addition of some manually created objects (called 'buildings' in the code) including entry point.
After the map is generated all inaccessible areas are replaced for walls.
And there are several criterions of map acceptability for the game (considering 'Project Helena' is a turn-based strategy):
1. Free space ratio (for 'Project Helena' the maps should have 20% to 60% free space).
2. Map homogenity (I usually demand that free space ratio for different map segments should not be different by more than 15% in average)
In case the map is inacceptible by these criterions it is re-generated. There are some algorithms like 'linear-sinus' I use which preform very poorly and have to be re-generated many times until some acceptible result occurs, but when they do well, they create a nice-looking and interesting-to-play map.
As of today there are 29 different map generation algorithms, which you can find in the source code of: https://sourceforge.net/projects/projecthelena/
I've attached several examples. Do not pay attention to a white box and red/blue dots :) It's game-specific (large-scale map, enemies and items).
i think if you would turn just the cave generation into a library.. tons of people would use it? all those maps look gorgeous.
I'm afraid I don't know how to :) I just compile the programm in Lazarus to get windows/linux executable... Never worked with libraries before... And I don't think lazarus/fpc unit would be of any use, not so many apply it for game development.
Moreover I use only 4 tiles for walls/floors, and most map algorithm create just one pair. Plus several other 'to-do' ideas. I'm going to improve this soon, but I mean that it is not 'finished' yet. I hope that will be completed after integrating the game with Castle Game Engine for better graphics.