algorithm - How do I generate a smooth random horizontal 2D tunnel?

I'd like to create a smoother version of the navigable and quite natural-looking random tunnel found in this classic helicopter game.

It should ideally be...

• infinite, so more can be generated as the player progresses;


• parametrised, allowing control of its thickness over time;


• made of smooth curves, not rectangles as in the above game;


• precomputable, as knowing its bounds in advance allows collision detection for e.g. positioning powerups inside the tunnel.

I'm looking for a generic method I could implement myself. Further parameters and optimizations are welcome.

Asking here was suggested on StackOverflow. I think this fits in both places, as it's as much about the algorithm as about gamedev.

Answer

Some intuition:

Step1: Randomize points-each time taking a step forward on the x-axis

Step2: Imagine segments(lines) between these points, add new points in the middle of each one

This is how it looks now without the segments:

Step3: Draw bezier from red point to red point, using the original point as control.

Step 4:

1. Randomize new control point



2. Imaging new segment


3. calculate new red point


4. Draw Bezier from previously last red point to the new one


5. Repeat

Answer:

You can use Beziers here to create a smooth continuous curve ... first randomize a continuous list of points:

//screen size 640 x 480
safeViewDistance = 700; //How far can the player see
playerX;

averageDist = 100 // averageDistanceBet
lastX = - 2.5 * averageDist //the further point in the tunnel
tunnelHeight = 300 // space between ceiling to floor

while(lastX < playerX + safeViewDistance)
{
    lastX += (0.5 + Math.random()) * averageDist;
    points.push(new Point(lastX, Math.random()); 
}


//to draw the ceiling and floor use bezier:
lastDrawnPoint = 1;
function drawPoints(yOffset, yCoeff)
{
    while(lastDrawnPoint < points.length)
    {
        i = lastDrawnPoint;
        startPoint = average(points[i-1], points[i]);
        controlPoint = points[i];
        endPoint = average(points[i],points[i+1]);


        startPoint.y *= yCoeff;
        startPoint.y += yOffset;
        /repeat for control and end

        drawBezier(startPoint, controlPoint, endPoint);
    }
}

Drawing a Bezier approximation can be handled by iterating with n = 100 on the function and drawing lines:

q(t) = (1-t)*((1-t)*start + t*control) + t*((1-t)*control + t*end)

By iterating I mean running on 0 <= k <= n like this:

q(k/n)

Here is a sample code for Bezier in AS3 copyrights

Raster class
*   
*   @author     Didier Brun aka Foxy - www.foxaweb.com
*   @version        1.4

*   @date       2006-01-06
*   @link       http://www.foxaweb.com
* 
*   AUTHORS ******************************************************************************
* 
*   authorName :    Didier Brun - www.foxaweb.com
*   contribution :  the original class
*   date :          2007-01-07
* 
*   authorName :    Drew Cummins - http://blog.generalrelativity.org

*   contribution :  added bezier curves
*   date :          2007-02-13
* 
*   authorName :    Thibault Imbert - http://www.bytearray.org
*   contribution :  Raster now extends BitmapData, performance optimizations
*   date :          2009-10-16
* 
*   PLEASE CONTRIBUTE ? http://www.bytearray.org/?p=67
* 
*   DESCRIPTION **************************************************************************

* 
*   Raster is an AS3 Bitmap drawing library. It provide some functions to draw directly 
*   into BitmapData instance.
*
*   LICENSE ******************************************************************************
* 
*   This class is under RECIPROCAL PUBLIC LICENSE.
*   http://www.opensource.org/licenses/rpl.php
* 
*   Please, keep this header and the list of all authors

Actual code

/**

 * Draws a Quadratic Bezier Curve (equivalent to a DisplayObject's graphics#curveTo)
 * 
 * @param x0            x position of first anchor
 * @param y0            y position of first anchor
 * @param x1            x position of control point
 * @param y1            y position of control point

 * @param x2            x position of second anchor
 * @param y2            y position of second anchor
 * @param c             color
     * @param resolution    [optional] determines the accuracy of the curve's length (higher number = greater accuracy = longer process)
     * */
public function quadBezier ( anchorX0:int, anchorY0:int, controlX:int, controlY:int, anchorX1:int, anchorY1:int, c:Number, resolution:int = 3):void
{   
    var ox:Number = anchorX0;
        var oy:Number = anchorY0;
        var px:int;

    var py:int;
        var dist:Number = 0;

        var inverse:Number = 1 / resolution;
        var interval:Number;
    var intervalSq:Number;
    var diff:Number;
    var diffSq:Number;

        var i:int = 0;


        while( ++i <= resolution )
        {
            interval = inverse * i;
        intervalSq = interval * interval;
        diff = 1 - interval;
        diffSq = diff * diff;

            px = diffSq * anchorX0 + 2 * interval * diff * controlX + intervalSq * anchorX1;
            py = diffSq * anchorY0 + 2 * interval * diff * controlY + intervalSq * anchorY1;


            dist += Math.sqrt( ( px - ox ) * ( px - ox ) + ( py - oy ) * ( py - oy ) );

            ox = px;
            oy = py;
        }

    //approximates the length of the curve
    var curveLength:int = dist;
    inverse = 1 / curveLength;


        var lastx:int=anchorX0;
        var lasty:int=anchorY0;

    i = -1;
    while( ++i <= curveLength )
    {
        interval = inverse * i;
        intervalSq = interval * interval;
        diff = 1 - interval;

        diffSq = diff * diff;

        px = diffSq * anchorX0 + 2 * interval * diff * controlX + intervalSq * anchorX1;
        py = diffSq * anchorY0 + 2 * interval * diff * controlY + intervalSq * anchorY1;

            line(lastx,lasty,px,py,c);
            //aaLine(lastx, lasty, px, py, c);
            lastx = px;
            lasty = py;
    }

}

Once you clean up the code, the result will look like this: