How To Generate Procedural Racetracks Without Noise | Hacker News Reader

How To Generate Procedural Racetracks Without Noise

bordeen.blogspot.com

81 pointsbane20 comments

A simpler implementation off the top of my head, although I can not verify immediately how good the results would be:

Instead of generating a convex hull, use polar coordinates and generate points in a circle or ellipse with a random radius modifier (since these tracks don't have overlaps this method should work fine). You can pretty easily control the spacing and delta in the radius and theta, and then just use Bezier curves from there which should not have weird cusps that the author describes if your spacing is correct. With a few modifiers (like using Manhattan distance for the radial measurement) you can make some variations like more "square" tracks although this would introduce (potentially) new complications.

That said, the author's implementation works great regardless of complexity and would probably fair better with more complex track types.

I find it really funny that your suggestion is best implemented with Perlin noise.

I love stuff like this. I wrote an Android game[0] that has terrain that's procedurally generated using a very simple algorithm. Discovering other content-generation algorithms which give nice, random but realistic-looking results gets me buzzed as hell.

[0] https://github.com/bitwize/rboots-android/

I really do enjoy reading about terrain generation algorithms, I've been playing with perlin noise but haven't managed to make anything that looks realistic yet. I don't know whether you'd judge my tried and true method as realistic but I threw together a gallery for my progress on the last Ludum Dare, the gallery moves past world generation pretty quickly though.[1] The source is up on github.[2]

[1] http://imgur.com/gallery/13k1R [2] https://github.com/Lockyy/YOGO-Moment-of-Interaction

You may also enjoy reading http://procworld.blogspot.fr/ for some interesting posts about procedural terrain, vegetation and architecture generation. I found the visual results are quite impressive.

I think this is a great example of how well-studied algorithms crop up in (potentially) unexpected places, i.e. convex hull.

Often in day-to-day work algorithms aren't immediately useful. But when they are, they really make a difference.

I love this, and I think I'd enjoy driving those tracks.

I'm surprised that there are not more "design your own track" racing games. It feels like that kind of user customisation is popular, and sharing tracks would be very popular.

The TrackMania series has strong support for designing your own tracks.

Great post!

It might be a good idea to look at the https://en.wikipedia.org/wiki/Euler_spiral to make the curves more "realistic" or convenient to drive through. If this would be desirable of course depends on the type of game.

This is quite interesting, although I wonder if it's possible to also generate non-looping race tracks. Noise would be great. For example, touge tracks in the mountains of Japan where you start at the top, and descend with very twisty roads.

http://initiald.sega.jp/ind5/img/course/happo.jpg

Include elevation! How fun would that be :)

http://www.oocities.org/ds_map/map_data/myogi.gif

http://en.wikipedia.org/wiki/Random_walk would be something that can be utilized for this

Non-looping tracks would probably be easier because you could generate the track as you go. Roll a dice and see if the next piece of track will go left right or straight. You don't have to worry about ending up at a predefined point.

Not only that, I think you could be creative and make physically impossible overlapping tracks, just like games like Portal 2 or The Stanley Parable have impossible architecture. As long as this doesn't happen often, you might not even realize this is happening.

> From this defined retangle, generate a collection of random points inside it

That immediately defeats the "Without Noise" requirement.

Noise in this context refers to perlin/simplex noise, not the use of rand()

If you sample it sparsely enough, though, you might as well use rand. There wouldn't really be any gain from using a noise function in this application, however.

I think it was worth pointing out in the context of this post, though, as he took the time to directly address the part of his audience who apparently seems to think all "procedural" content should descend from a noise function, which is probably common with beginners. Often a simple random number generator will do just fine.

That misses the point completely.

You can trivially create a race track by following a route of a certain height in a perlin noise map. No algorithm needed at all. All you need is 2d perlin noise and a single if block:

    for x, y in range():
        if lower < perlin[x][y] < higher:
            map[x][y] = brown
        else:
            map[x][y] = green

The author just decided to take a different approach.

That piece of code is an algorithm just fine.

This algorithm is not sufficient. There's no requirement for the contour line to be simple, connected, or even closed within the domain you specify (the higher the frequency the more likely it will be closed, but the more likely it won't be connected).

One approach would be to then walk the line from the start and connect neighboring points that aren't too close to previous points and don't cause a turn tighter than some given angle (non-simple curves should only happen if you're unlucky enough to run into a saddle point of your desired value), but that solution starts looking a whole lot like taking the convex hull of clusters of random points...you could have just taken fewer points and then smoothed the curve that fits around them :)

Reply on news.ycombinator.com