Infinite 3D Cave in Unity

Question

A friend and I are hoping to make a game in Unity in which you fly through an infinite 3D cave that can twist and wind in any direction (though obviously not to the point that the turns are impossible to make). We were thinking about creating a number of tunnel "pieces" that each curve a certain amount, and spawning each at the end of the one that came before.

But we have no idea how to make sure that the mouth of one tunnel piece always aligns perfectly (in both position and rotation) with the end of the previous one. Can anyone offer any advice on how to accomplish this?

Are we even going about it in the right way, or is there a better way to procedurally generate the cave? Bonus points: It'd be awesome if the cave could change in diameter and/or shape as well, though that'd just be gravy.

Answer 1

There is rarely a "right way" or "wrong way" when it comes to game design. There are many, many ways to solve this problem, but here are a few possible approaches to explore:

• Constrain the tunnel pieces to both start and end only in certain directions; for instance only along the axes. Then you just have to keep track of the offset from the beginning to the end of a segment, along with enums describing the direction of movement at the start and end of the segment. This way you don't have to worry about rotating your tunnel meshes at all, as long as you always pick the next one such that it starts in the same direction the last one ended in.

• Make each segment start at the origin of its local model space with the tunnel traveling along a specific axis (+X, +Z, or -Z would be the most logical choices, but all of the models should use the same one), then store the position of the end of the tunnel and final direction of travel in some way so that the next mesh can be transformed correctly. (a transformation matrix is probably the easiest way to store this information, but you could also use a displacement vector + quaternion, dual quaternion, displacement + new basis vectors, displacement + euler angle rotations, etc.)

• Procedurally generate your cave by streaming new vertex data to a few meshes. You can do this using the Mesh class. When generating new vertex data, the easiest way is probably to pick a point somewhere in approximately the same direction as the previous cave segment, then let the center of the cave move toward that point. Then you can use cylindrical coordinates to procedurally create detail on the walls of the cave. Think of it as extruding out the end of a cylinder, then individually translating each vertex closer to or further from the center of that cylinder.

Any solution that uses premade segments will require you to make sure that all the meshes have the same shape and diameter around the center of the tunnel, but you can get around this somewhat by having the segments overlap to an extent, and have each segment flare out at the ends. If done right, it shouldn't be too obvious to the player that there's a seam.

On the other hand, if you go for entirely procedurally-generated geometry, you'll have more work to ensure that you don't generate sections that are impossible to traverse, and you might run into issues with collision detection.

Keep in mind, with any "infinite" game, you should be aware of the limitations of floating point representations. If the player gets too far from the world origin, it becomes easy to lose precision in floating point calculations (when two large values are subtracted from each other, for instance). To avoid this, you can make the world move around the player, rather than the player move through the world, but its usually easier to just check the player's position every so often, and if they're too far from the origin, rebuild the world with the player at or near the origin.

Answer 2

Here's a technique I experimented with recently. My RenderMonkey prototype shows a section of badlands-style canyon, but the same principle should work in caves.

The idea is to start with tiles that are generic, downright boring, with simple predictable edges so they're easy to line up without seams or gaps:

These starting tiles could be shapes you've modelled, or procedurally-generated macaroni tubes of cylintrical geometry (this form is a variant on bcrist's and Steven Stadnicki's suggestions). Using models you've created makes it easier to handle arbitrary topology like branching paths, or points of interest like open caverns. This is still possible with pure procedural (see Gyroninja's suggestion about metaball techniques), but challenging.

Once a tile is placed into the world, displace its vertices using noise functions applied in worldspace. This preserves connectivity and seamlessness between tiles (since coincident vertices have the same worldspace input, and get the same displacement output), but makes every tile look unique and organic:

Texture and normals are applied in worldspace too - here using triplanar mapping - so that adjacent tiles are completely seamless, without tricky UV unwrapping constraints.

The hope is that a technique like this gives you the ease of planning and level design control of a tiled map, without visible repetition or mechanical-looking structure in the playable result.

You can use a lower-res mesh with only the low-frequency noise components applied to create the collision representation. As bcrist notes, you'll need to control the maximum amplitude of the noise relative to the radius and sharpness of turns of the tunnel, to ensure it never pinches off completely.

One further note: if your cave really is infinite, you may need to "recenter" it periodically as the player moves further and further from the origin. Because floating point numbers lose precision at high magnitudes, physics and rendering artifacts can creep in at extreme distances. If you do this, you'll want your worldspace noise to be periodic over a large scale, with the period exactly matched to your recentering offset, so you don't encounter seams after recentering.

Answer 3

You could model your cave as a sequence of points, each with an associated size, with lines connecting them. Then treat each point and line as metaballs and metacylinders. This gives you a basic shape for your cave, to which you might want to start adding variation, such as by randomly offsetting vertices.

Answer 4

Here's another approach to procedural generation that hasn't been explicitly mentioned yet: spline skinning. You can use a version of Hermite Splines (which provide a curve interpolating positions and tangents) to define the curves: when it's time to generate a new segment, just choose a position (roughly in the direction of the previous segment, as bcrist says) and a direction (roughly in the same direction - e.g., within some well-defined cone of the previous direction), then use the new position+direction and your previous position+direction to build a new 'spine' for your cave. Once you have this backbone, you can skin it with a cylindrical construction: determine the positions and tangents of (for instance) 10 points along the curve, use those positions/tangents to find an orthogonal 'frame', and then use these frames to build cylindrical segments. One small caution with this is that the cave can't curve too much, or else you may run into self-intersection issues.

EDIT: Here's a rough pseudocode breakdown of the algorithm:

Parameters:
  L = (average) segment length,
  V = segment length variation,
  R = cylinder radius,
  T = segment angular variation
  S = number of 'rings' per segment

Setup:
Choose an initial point P_0 and direction D_0 (for concreteness' sake, these can be
the origin and the X axis).  Set P_prev and D_prev to these values.
Initialize u_prev to be the Y axis and v_prev to be the Y and Z axes.
  (Note that (D_prev, u_prev, v_prev) form a mutually-orthogonal 'coordinate frame')

Generate a segment (do this as many times as you want):
{
  Choose a (temporary) direction D within a cone of size T around the previous direction D_prev
  Choose a segment length L_cur = at random from within the range [L-V, L+V].
  Set the current terminal point P_cur to P_prev+D*L_cur - this is the position
  we'll interpolate to
  Set the current terminal direction D_cur to a direction chosen at random from
  within a cone of size T around the previous direction.  (There are good ways
  of doing this - if you look back through gamedev.SE you should find some)
  'Build' the Hermite spline H that goes from (P_prev, D_prev) to (P_cur, D_cur)

  Now, skin that spline:
  for ( i = 1; i <= S; i++ ) {
    find the position P of the hermite spline H at t=i/S
    find the direction D of the spline at t (this will be just the derivative)
    'transport' the orthogonal frame to the new spot: for instance,
      v_new = D x u_prev
      u_new = v_new x D
    (note that this keeps u_new, v_new close to their old values, and orthogonal
    to each other and to D)
    Use the previous and current frames and positions to build a cylindrical 'ring':
    For theta from 0 to 2pi {
      find the points (P+(u_new, v_new, D) * (cos theta, sin theta, 0))
      and connect them to their counterparts from the previous ring
      (note that that multiplication is a matrix-vector multiply)
    }
    update u_prev and v_prev to u_new and v_new
  }
  update the other prev variables to their 'new' values
}

This is obviously very rough pseudocode; if there's any piece of it that's unclear just let me know and I'll try and explain, but it's going to be hard to cover all the details without just a huge code dump...