# 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.

## 1 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:

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