Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by Anko, Seth Battin, MrCranky, Nathan Reed, Vaughan Hilts May 17 at 15:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
maybe this question can help you : gamedev.stackexchange.com/questions/14065 –  Ali.S Sep 28 '12 at 21:43

1 Answer 1

up vote 12 down vote accepted

Some intuition:

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

Randomize points

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

This is how it looks now without the segments: enter image description here

Step3: Draw bezier from red point to red point, using the original point as control. enter image description here

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:

tunnel in bezier

share|improve this answer
    
Wow, nice! Can you continue a line and keep it smooth, that is, can you draw above lines in a few steps? –  Markus von Broady Sep 29 '12 at 5:35
    
You can continue a line indefinitely and keep it smooth using beziers I will add more information. –  Zehelvion Sep 29 '12 at 11:21
    
This would look great I think, but how hard would proper collision detection be with this? Is there an easy way to detect when a bezier segment is crossed? –  IVlad Sep 29 '12 at 13:08
    
This is a great answer. @IVlad you can print the curves on a bitmap and then check pixels. –  Markus von Broady Sep 29 '12 at 13:47
    
@MarkusvonBroady - Thanks for the compliment :) IVlad: Markus von Broady is correct. Once it is on a 2d-array, you can easily check if the outer outline of your character intersects with lit pixels on the Bezier curve. (Second option)----- You could use the Bezier function: q(t) = (1-t)*((1-t)*start + tcontrol) + t*((1-t)*control + tend); to create an integer array that describes how high is the ceiling is in each x-value and then check if your character's bounding box is slightly higher or bellow the ceiling. –  Zehelvion Sep 29 '12 at 14:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.