# How do I generate a smooth random horizontal 2D tunnel? [duplicate]

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.

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

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
*
*   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
*
*
*   DESCRIPTION **************************************************************************
*
*   Raster is an AS3 Bitmap drawing library. It provide some functions to draw directly
*   into BitmapData instance.
*
*
*   This class is under RECIPROCAL PUBLIC LICENSE.
*


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: • 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. – wolfdawn 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. – wolfdawn Sep 29 '12 at 14:16