How can I randomly generate 2D tile-based side-scroller terrain?

Question

I want to randomly generate a map for a 2D sidescroller game using the following tileset:

I have found a few great articles on the bitmasking process, for example: http://www.angryfishstudios.com/2011/04/adventures-in-bitmasking/ http://www.saltgames.com/2010/a-bitwise-method-for-applying-tilemaps/

I like the idea of using a bitmask/tilemask instead of doing a huge if clause or switch statement.

However, I am having trouble visualizing the entire process and none of these articles talk about randomizing.

My tiles fit together in multiple different ways, not just one way as the tiles in the examples I linked seem to.

For example here are just a few examples:

Since my tiles fit together in many different ways I don't think an 8 bit mask will work. Therefore, I was thinking of using a larger bitmask. Something like char[8] or char4.

If someone could please show some pseudocode/examples of how the general algorithm would look, I would greatly appreciate it.

Answer 1

Yes, the mask size would grow with increasing number of options - your own link http://www.saltgames.com/2010/a-bitwise-method-for-applying-tilemaps/ second part explains the main idea.

In essence, you'd have to enumerate X possibilities for each 'border' between tiles; in your particular example it looks like the "tile top/bottom" may be either (1) white (2) covered or (3) half-covered - which coincidentally matches the 'trinary' example given in the article.

But the masks would only help you restrict the tile possibilities to those that can be drawn, by itself it isn't a method that shows how to generate the actual maps in a sensible way.

Your particular tileset actually is quite restrictive - it describes only a single surface rising/falling, and at any 'integer-level' starting point you have only a few valid choices. For example, after tile #2 only tiles #1 or #8 are possible. You could simply move from left to right, making a list of which (few) tiles can come after the previous tile, and randomly choosing one of them.

Answer 2

Have you considered using a 1D Perlin or simplex noise function? There are a number of advantages to this, including:

1. Infinite (within the realm of floating-point precision), non-repeating terrain

2. Can be generated real-time (even in a shader, which is fast), or ahead-of-time and stored in textures, as in your example

3. Borders automatically match up as both Perlin and simplex are continuous.

4. Although the terrain itself is pseudo-random, it's easy enough to apply an envelope function or simply reduce the number of octaves in areas where you need flat areas or other specific terrain features that you need.

See this link for a fairly thorough explanation of 1D Perlin implementation.

An envelope is basically a scalar field or function that is multiplied with the noise function before saving or displaying your output.

(Initial image borrowed from the above-referenced article.)

In this example, the red line represents a piecewise function defined as

x < 0.3 : y = (0.3-x)/0.3)
x < 0.5 : 0
x < 0.7 : (x - 0.5) / 0.2
else    : 1

... which may be better defined using a smooth function. In this case, it just scales things down to 0 before the plateau, then back up to 1 afterwards.

Update

Here's an example of a 3D simplex "terrain" from one of my projects, with diffuse + specular lighting applied, generated entirely within a vert + tess + frag shader pipe. For your situation, I'd take a vertical slice out of this to get the terrain slope.

And a top-down orthographic view: