# Generating random tunnels

What methods could we use to generate a random tunnel, similar to the one in this classic helicopter game? Other than that it should be smooth and allow you to navigate through it, while looking as natural as possible (not too symmetric but not overly distorted either), it should also:

1. Most importantly - be infinite and allow me to control its thickness in time - make it narrower or wider as I see fit, when I see fit;
2. Ideally, it should be possible to efficiently generate it with smooth curves, not rectangles as in the above game;
3. I should be able to know in advance what its bounds are, so I can detect collisions and generate powerups inside the tunnel;
4. Any other properties that let you have more control over it or offer optimization possibilities are welcome.

Note: I'm not asking for which is best or what that game uses, which could spark extended discussion and would be subjective, I'm just asking for some methods that others know about or have used before or even think they might work. That is all, I can take it from there.

Also asked on stackoverflow, where someone suggested I should ask here too. I think it fits in both places, since it's as much an algorithm question as it is a gamedev question, IMO.

-
maybe this question can help you : gamedev.stackexchange.com/questions/14065 –  Ali.S Sep 28 '12 at 21:43
possible duplicate of Helicopter game, but waves? –  bummzack Sep 29 '12 at 12:36

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. –  Arthur Wulf White 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 + t*control) + t*((1-t)*control + t*end); 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. –  Arthur Wulf White Sep 29 '12 at 14:16