Sunday, November 11, 2012

A System of Caves

A true exploration and adventure game-world needs a decent system of caves.

Caves are exiting. You do not know what lies next. It could be that motherload you have been tracking for hours, it could be a band of nasty creatures.

Caves are also beautiful and interesting. I like it when caves surface and create openings in the face of mountains, or when a large portion of ground has collapsed and you can see part of the cave's profile like a giant ant farm.

Over the past few weeks I did many attempts on creating a good cave system. It is a lot more difficult than it seems, especially if you want to generate them in real time.

I tried different solutions until I hit what I thought it was the winning formula. The key wast think of the cave system more like a dungeon in a castle, pretty much like roguelikes do in ASCII. You end up with a system of narrow tunnels that connect in meaningful ways and often lead to large interior spaces. It is then possible to give an interesting rhythm to the system. You can count on the system to reward the explorer with awesome crypts after enough tunnels have been explored.

Another challenge was to create the connections between the caves and the surface. I wanted caves to be fun and beautiful, and actually help you get around the world. For instance they often serve as shortcuts below mountains.

I also had to pay close attention on how the caves played with the rest of the terrain. If you had all the time in the world this would be hardly a problem. To generate this on-the-fly and make sure there are no odd floating bits, it is kind of tricky.

I leave you with a series of screenshots showing some caves I have encountered in my travels. At the end you will find a wireframe video that shows the profile of a cave system. I hope you like them.









Here is the video:

67 comments:

  1. In the fifth screen shot from the top, it looks as if there is a portion of the cave ceiling that has broken off and fallen to the ground. Is this a result of the generating algorithm, or is it a happy coincident?

    Perhaps the ceiling elevation is offsetted by the ground elevation, making it look the way it does.

    Awsome as usual, by the way. (I do not use "awsome" haphazardly!)

    ReplyDelete
    Replies
    1. It is a result of the algorithm, but in fact cause and effect are switched. It is the bump in the ground what caused the hole on top.

      Delete
  2. The caves are quite cool =3, the only things which bothered me slightly, were the fact that there were only stalagtites, and no stalagmites, and that the cave entrances often seemed rather wide for how much rock was above it... but then again, the pillars might act as supports.
    Will you be giving the caves their own texture? Cause especially caves with stalagtites and mites (caves formed by water) usually have some sort of a glistening shine to them, and are really smooth with interesting details =3.

    ReplyDelete
    Replies
    1. Yes you are right about that. I can have stalagmites too, not a problem.

      The caves can have their own textures, I did not spend much time texturing this.

      Delete
    2. I figured as much with the textures =3, just thought I would say it just in case.

      Delete
  3. Looks really interesting, would be a fun part of any game.

    The issue I noticed was that you don't seem to be gaining or losing elevation anywhere in the systems?

    Awesome as always.

    ReplyDelete
    Replies
    1. You are correct, this is only for this video so you can see the system of tunnels and larger crypts.

      Delete
  4. WOW this is amazing! You must have done a lot of optimization to get this running in real time? or is it still running off the farm?

    ReplyDelete
  5. Miguel, from one PCG-obsessed programmer to another, I must say, congratulations and thank you. Sincerely, thank you for pushing the boundary of what is possible with procedural content. Your work will open the eyes of many to what is possible in video games and beyond with respect to procedural methods.

    This is undoubtedly the future of content creation...and it brings me so much happiness to see you proving it, day after day, with these incredible demonstrations.

    Keep pushin :)

    ReplyDelete
    Replies
    1. BTW your path tracer is impressive. You can do the gas rendering at 10 FPS in CUDA?

      For anyone else who has not seen it: http://jpcs348b.blogspot.ca/

      Delete
    2. Yep, always more to do I suppose...but I can't imagine how exciting it's going to be watching you go there!

      And yes but no, what I meant when I said my goal was 10 FPS was 10 samples per pixel per second. So yes, I can take 10 samples per pixel per second, but MC path tracing takes 1000s of samples to converge (the final image took 3 hours, but that was overkill).

      However, if one were to remove all of the geometry, I imagine that you could get 10 fps for real on the gas if you tone down the quality a bit. That volumetric data is fast to trace compared to the kd-tree geometry.

      Delete
  6. How much RAM and video memory is this client typically using?

    ReplyDelete
    Replies
    1. All of it!

      It is actually high but very steady.

      RAM: ~800 Megs.

      Video: 470,294 KB

      Here is the breakdown for video:

      VBOs: 235,082 KB
      Textures: 195,566 KB
      Static Buffers: 39622 KB

      This could be improved a lot. I do not use compressed textures at the moment.

      Delete
  7. Very nice Miguel. I check your blog daily for updates and today you did not disappoint! I can't wait to see a "showcase" video showing off all of the features you have been working on in one video. Keep up the amazing work!

    ReplyDelete
  8. For me, some of the most exciting things to stumble upon in caves are the large interiors that not only spread out horizontally but vertically. High ceilings over deep canyons are great. If it's dark enough, you feel like you're standing in the middle of a void, with nothing above or below you. I love it and I really hope you'll support for such things in your engine.

    ReplyDelete
    Replies
    1. Now that you mention it, the lighting inside caves is something I am having some trouble figuring out. In real life it is simple, it is usually pitch black. For a game I am not sure if this is right.

      Delete
    2. Limited lighting can be pretty atmospheric. If you give the player a torch or flashlight, caves can become sources of danger and excitement. You never know what might be lurking outside the range of your light, or when the path might suddenly reach the edge of a deep canyon.

      Most games seem to make caves bright, as Andrew Doull mentioned below, using mushrooms, lava, etc. When used in small amounts, I think that works. It gives players something in the distance to aim for. I'm of the opinion that caves should primarily dark, evoking the player's fear of the unknown and their curiosity to find out just what might be out there.

      Delete
    3. I agree, it would be really nice to have in-cave luminescence rare, not completely absent, but hidden away and requiring exploration. For example, look at minecraft, that game has really dark caves, and then eventually you have lava when you get low enough, stumbling upon lava (if you didnt bring any torches and fell into a cave) is a relief, since you can finally see again, but that does not mean the lack of light is a bad thing, it actually enhances both experiences, the experience of finding lava (which gives light) and the experience of being lost in a cave system, after which you found some slight relief.

      This luminescence could also be magic mushrooms, light giving grass, or glow in the dark rocks or something like that. If you plan on having giant chambers in your caves, it would be brilliant to have to crawl through narrow, dark passages, to eventually get into this large room with light (Might also not contain light, which will also produce an epic effect =3)

      What I am saying is; you dont have to limit yourself to one type of light, play with it, but dont forget about darkness =3 (I dont like unrealistic ambient light btw =3 *angry cat sound at Oblivion*)

      Delete
    4. I'd be preferential to mostly darkness with occasional light sources as well, lava, glow worms, lumiscent fungi or lichens, just for atmosphere, or possibly for players to intentionally cultivate.

      I also wanted to say, yay big open spaces. I'd be very happy if we could find, from time to time, a Menzoberranzan that needed only buildings to be a jaw dropping city-state.

      Delete
    5. The question of what is right for a game can depend on what type of game it is, or how it supposed to feel to the player. That "feeling" though, is a core part of game design and requires almost every other aspect of the game to come together and support it. Which would be hard to do with PCG since nothing is as planned as it would need to be.

      So far in your PCG project all there is to it is the realistic world. Since I imagine that you plan to keep that theme then you are limited to what is typically inside of caves, fungi, lichen, plants, lava, even certain phosphorescent minerals (though technically those need to first absorb light energy from something). Those are actually kind of limiting.

      Here on earth there isn't a large amount of things that give light off naturally in caves. On another planet anything possible, but then there isn't this problem if anything is free game to be a light source.

      Looking at what other games have done in the past. I can think of three basic solutions: Glowing natural-sources, ambient lighting, and leaving it completely dark. Most games seem to use a combination of 2 of these ideas based on what their engine and the player can do.

      Oblivion/fallout3/etc uses natural lights and large ambient lighting to brighten up caves and can make it easy for a player to understand their surroundings without needing to bring in more light, and at worst confuse and pull them out of the experience with unrealistic lighting. Minecraft has mostly dark caves with scarce natural lighting and the ability to create torches that provide light, at worst making it impossible for the player to see and understand things when both are denied to them.

      Your game has not defined how it will handle lighting in any of these ways yet. Most of your followers in this thread seem to like the idea of darker caves with a few lights, though no clear idea what provides light. Your engine allows for the player to destroy or place things so placing lights is also a viable solution. Again it's very similar to Minecraft in that way. Lets think of somethings that Minecraft doesn't have.

      Not because you need to distance your game from it, but because there's more options than what Minecraft uses.

      So you can add glowing plants to list. Also phosphorescent materials could be interesting to use. Another idea would be some sort of animal that provides light, what comes to my mind is the deep sea anglerfish, which has a growth that emits light to lure prey in close. A cave dwelling predator that emits or uses light in a similar way could be interesting in your game.

      Again these are ideas, which you could either take, leave, or expand upon in your own way. My goal was to expound on and take a look at possible solutions to this issue.

      Delete
  9. Have you given much thought to water and/or geothermal interaction with caves? I know you're skipping rivers for the first release but it'd be nice to see something in there.

    I suspect you're going to have to go with typical fantasy world lighting: luminescent mushrooms, glowing mineral deposits, lava and so on.

    ReplyDelete
    Replies
    1. Well keep in mind this is generated in realtime, so there is very little space for global methods like any simulation. Actually what you see in the realtime aspect of the engine is all local.

      I will be adding water later this year. Even then, I will have to figure out how to do it with a local method.

      Delete
    2. I dont think people mind if you make them wait a while to generate the initial (rough) world through simulation, and then tweak it in real time, I believe that is what Dwarf Fortress does, as long as you only need to do it at the start of any world, I dont think it will be a problem, if you have to do it at the start of every game though, people might not like it =3.

      Delete
    3. You are right about that. But I would still like to see how far it can go without a pre-generation phase.

      Delete
    4. I will be very interested in your results, as local river generation seems to be a yet-unsolved problem in PCG. I have no doubt that you will solve it, though :)

      Delete
  10. I found your blog yesterday and read every article in order. I want to do exactly what you are doing. I have a degree in Mathematics so that part doesn't intimidate me, and I'm a competent web developer at my day job, but I have no experience in graphics programming. What sort of learning resources could I check out to start down the long and winding road of procedural world simulation?

    ReplyDelete
    Replies
    1. The GPU Gems programming series will probably teach you anything you will need to know. Nvidia has the books online and they are free.

      Delete
  11. Sorry for spamming your comments, but this is a different topic from all of those (and I like speaking my opinions =3)

    Anyway, on to the topic: I noticed there are some loose pockets of air in your cave generating system, which gave me the idea: Dont take it out! Work with that, have caves which dont really connect to anything, caves with collapsed entrances for example or perhaps caves with too small entrances to enter, this means the player will have to dig to explore, which makes the exploration even more fun (hopefully) =3. Also, it would be nice if you could make caves to not be EVERYWHERE (like minecraft does) its nice to be able to dig a basement without falling into a cave =3.

    ReplyDelete
    Replies
    1. It is actually like that. There are caves you only can discover if you dig a little bit. Sometimes what looks a dead end is actually a few meters away from another corridor.

      Also only 25% of the surface has caves. They are more probable where plains encounter the mountains.

      Delete
    2. Why do I even write suggestions? You seem to read my mind unconciously regardless XD

      Delete
    3. It is because I am you, three years into the future.

      Delete
    4. Woohoow, I get to make an awesome procedural world three years from now! =D, and get to change my name to Miguel Cepero! Funny how one can be his own inspiration... BTW, isnt there supposed to be some sort of paradox-prevention system going on? You know, universe blue-screening and all that?

      Delete
    5. If the universe hasn't noticed it yet, don't call attention to it!

      Delete
  12. Are you planning in releasing a tech demo or a sandbox of this in the next year? i would love to test it, although i'm not sure my computer will be able to run it.

    ReplyDelete
    Replies
    1. Yes, hopefully early next year I will have a public alpha.

      What kind of system you have?

      Delete
    2. hey miguel, christonian here my system should be able to handle this right???

      i5 2500k
      8gb ram
      ATI 5770 1gb

      Delete
    3. Yes, no problem. Your system is better than the one I use.

      Delete
    4. Whats is more important for the game, the graphics card or the CPU. I ask because I have a 5 year old CPU (Q6600) but a less than one year old graphics card (AMD 7870).

      Delete
    5. Q6600 should be fine, but it is on the fringe. The CPU is used for the generation. You may get the generation buffering green bar more frequently than others.

      Your GPU is top-notch. The framerate will be insane.

      Delete
    6. Hi Miguel, thanks for replying to my comment :D

      The specs of my computer are:
      CPU: Intel Core 2 duo E7500 2.93 GHz
      GPU: Nvidia Geforce 8600 GT
      Ram: 2GB

      It is like 4 years old, but still can run Crysis on middle graphics at 30 FPS

      Delete
    7. You should be fine... Soon you'll know!

      Delete
  13. This is again very impressive and I cannot wait to see this filled with monsters and some light. But in contrast to all the other terrain you have shown so far, the caves do not look right for me. Don't get me wrong, but your terrain looks so realistic most of the time, that the cave entrances strike out to much. In my opinion, there is something wrong with them - the actual rock formations are too synthetic. I know it's hard, but maybe you find a way to make the entrances look more 'real' - I would also suggest to make them smaller and less obvious.
    But maybe I am wrong and this feeling disappears, once you use addapted textures :)

    ReplyDelete
    Replies
    1. Well you cannot argue with a feeling. I will try to see what is wrong.

      Delete
    2. Ok, it was not my intent to argue with a pure feeling ;) I wanted to express that the cave entrances look very artificial to me and this does not match with the rest of the world. Take picture 5 as an example: I cannot imagine nature would produce this rock formations (maybe I am wrong). Erosion and tectonic formed the mountain and the rocks in the front, but the cave seems to be copy/pasted from another region. Furthermore, when I look at the texture from the rocks, I would expect a more eroded surface with little rocks missing on the slab. In the textures you can see the sites of fractures, but they are missing in the geometry.
      Hence there are two parts: First, the mismatching results of erosion/tectonics (mountain vs. cave) and second, the correlation between textures and fine geometry.
      Hopefully you can see my point now :)

      Delete
    3. I did see your point. I meant I cannot argue with a feeling. If you feel something is off, that alone is a sign there is something wrong.

      Delete
    4. They look a bit like dripping rock that's entirely held up by stalactites, almost alive. Caves are often slightly round in shape as they are carved out from water flow. This one looks like something has landed and enveloped the landscape rather then being there for millions of years.
      Nice work none the less, and fast! Wow, how do you find the time?

      Delete
    5. I think there's a couple of issues (which may be what blackonyx is picking up on):

      1) large stalactites and stalagmites won't normally form in an exposed-to-the-wind area in a cave as the drops of water which carry the calcium/minerals won't be constantly moving over the same route or dripping on the same spot -- they'll get shifted by air movement and the mineral won't get deposited in the same spot. This might be fixable if you can calculate distance from open air.

      2) particularly with screenshots 4, 5 and 6, the exits of the cave entrances are too sudden in the landscape and too large and don't appear to fit the geometry of the land (this may be the same point as blackonyx is making above). In 5 and 6 in particular the weight of the ground above would simply be too heavy (in nature you'd end up with a collapse and a much smaller cave). Again, this might be something you can fix with a distance-to-surface number. Simply a smaller entrance in each of those cases would suffice, since it's purely the exposed state that appears wrong.

      On second thoughts, there's a kind of ant farm appearance: that may be the simplest way of describing it.

      I look forward to the spelunking! :D

      Delete
    6. Thanks for the analysis. I see what you mean. I will look into this.

      Delete
  14. This is great stuff Miguel, I wondered - how does your visibility system work with the viewpoint being able to roam so freely through such a 3D environment? Is there visibility information stored with each chunk as to which boundaries have empty space?

    ReplyDelete
    Replies
    1. No visibility information. I only do Frustum culling. I rely on the LOD system to keep the number of polygons sane.

      Great progress on your blog lately. I love the new voxel procedural planets.

      Delete
    2. Thanks! I asked about visibility as it's something I've been thinking about recently. The trade-off with ray-casting voxels is interestingly quite different as the geometry count is very low (12 tris and eight verts per SVO) but the pixel cost extremely high so rendering extra cells is very cheap if they don't actually shade pixels.

      I'm currently rendering the planet cells (each cell contains an SVO) front to back using the stencil buffer to prevent overdraw.

      Delete
    3. Have you considered viewer-aligned billboards? You could cache cells if they are sufficiently far away.

      I saw a paper from some Italian guys who where doing something like that for rendering trees. If you don't know about them I can dig out the link...

      Delete
  15. I was waiting long time for a new post, I was thinking few days ago If you would add some caves to this terrain and here I am.. :D Nice job. I'm waiting for more info and posts :)

    ReplyDelete
  16. This adds so much in atmosphere, it's stunning!

    One thing I wondered about though, after looking at the wireframe video - caves all appear around the same level, and have a flatish floor.

    In real life, caves go over and under eachother, and have different shapes in different sections - of course there's your halls and corridors, but there's also chasms, small and/or low crawlways, paths going up and down, twisting around, there's slideways, pitfalls, etc.

    Would it be possible to include those features in your generation algorithm? Given how fast you came up with this, you should have no problem ;)

    Good luck, with whatever you do, it's looking magnificent!

    ReplyDelete
    Replies
    1. http://procworld.blogspot.co.nz/2012/11/a-system-of-caves.html?showComment=1352663457986#c6673731404627209595

      That guy(or girl) said the same thing, but in less words.
      The answer was that that was only for the video to show off certain things =3.

      Delete
  17. Your work is incredible and the bad side is that it's actualy tempting me to go to a voxel engine to

    ReplyDelete
  18. Where I can download ProcWorld? If I can.

    ReplyDelete
    Replies
    1. Maybe you posted early demo version, if I strongly ask? :)

      Delete
  19. I'm totally looking forward to this program, it will be so popular when you release it! You'll make so much money, and your time will be well worth spent. :) I have a i7 3770k, 2 gtx 460's SLI, 8gb ram ddr3 1600 mhz, i.. just can't...wait. for this program!!! :D

    ReplyDelete
  20. This is amazing! Would you care to share how you randomly generate the caves? I'm curious to know how you achieved such an amazing system :)

    ReplyDelete