# Algo for narrowing cavern

I'm in a bit of crunch time and I find myself spending way too much time tinkering with an algo, so I would like some help.

In the game I am working on, there are some old-style, pixelated minigames. One of the minigame is a spaceship in a cavern. The caverns curves and narrows down over time until the ship crashes in a wall. I want them to be generated at random during runtime.

I'm having a problem creating the walls of the cavern and narrowing them while keeping a smooth curve on them.

For the narrowing, I keep track of it with a variable that decreases over time, but how about the curving and how to keep it natural? I've though of a keeping a target point that goes up and down randomly and have the wall try to reach for it, therefore smoothing the randomized number but it is not working great.

Any ideas/algo?

You're on the right track, add noise (perlin or otherwise..) to the floor and ceiling to make it look 'natural' and jagged. Then you could use 1D Brownian motion, as you suggested actually, as a target point, and draw the opening around that point.

Generate the level one slice at a time, and simply move that slice toward the player. If it goes up and down too fast (the target value, that is), you can try and smooth it using a sliding window, the simplest being simply averaging with the previous target value like so

window = 0.8;
targetY = next_brownian_value() * (1-window) + targetY * window;


Which will create an exponential sliding window (in this case, the targetY will be one fifth the new random value, 4/25ths of the previous random value, 16/125ths of the one before that, etc). Try playing with the window size and see what happens, higher value gives more smoothing (higher influence of previous values).

Note that the next_brownian_value should not be influenced by the targetY, it should go on its usual drunken walk.

EDIT
Naming the weighting factor 'window' was a slight misnomer, as a larger window should have a more smoothing effect. I've reversed the meaning above to make it more intuitive. It's still not really a window 'size' in a theoretical sense (which is usually defined to where the contribution is 1/e for exponential stuff..), but it least it's the right way around now..

• Thanks for the info. That is definitely the way I should do it. But I can't find an implementation of brownian motion (in java). In the end, I'm going with a random point selection for the target. Far from perfect, but at least it's got the 'old school' part going for it.
• @ADB; random walk is a simplified brownian motion, and should suffice, and is more or less simply x = x + random(); where random() is -1 or 1. Dec 21, 2010 at 11:45