How can I generate an "unlimited" world?

I would like to create a开发者_JS百科 game with an endless (in reality an extremely large) world in which the player can move about. Whether or not I will ever get around to implement the game is one matter, but I find the idea interesting and would like some input on how to do it.

The point is to have a world where all data is generated randomly on-demand, but in a deterministic way.

Currently I focus on a large 2D map from which it should be possible to display any part without knowledge about the surrounding parts.

I have implemented a prototype by writing a function that gives a random-looking, but deterministic, integer given the x and y of a pixel on the map (see my recent question about this function). Using this function I populate the map with "random" values, and then I smooth the map using a simple filter based on the surrounding pixels. This makes the map dependent on a few pixels outside its edge, but that's not a big problem. The final result is something that at least looks like a map (especially with a good altitude color map). Given this, one could maybe first generate a coarser map which is used to generate bigger differences in altitude to create mountain ranges and seas.

Anyway, that was my idea, but I am sure that there exist ways to do this already and I also believe that given the specification, many of you can come up with better ideas.

EDIT: Forgot the link to my question.

EDIT 2: I think I'll have to clarify that it is important that two adjacent parts of the map, generated separately, needs to smoothly connect to each other.

EDIT 3: Some more information was asked for in the comments.

Here's an image taken from a page about fractal and Perlin Noise that looks much like what I have produced myself previously (since my best attempt probably used Perlin Noise):

Think of black pixels as deep sea and white pixels as mountain tops. This is what I need, a simple 2D elevation map.

What I want to be able to do is to pick any rectangle from the very large world (in the range of MAXINT * MAXINT pixels) and generate it. If I would generate any part of the image above it should get exactly the same pixels as if I generated a bigger part encompassing the smaller one.

Now on to Unreason's questions:

Required performance: My main aim would be a turn based RPG, so performance could be quite low, but I think it would be very interesting to see if it is possible to create a fast algorithm.

Memory requirements: Preferably nothing should be pregenerated, but other than that, memory usage should match any ordinary game or application.

Required detail: Well, if you look at the image, you get the idea. It would be very nice though, if it was possible to zoom out and pan without having to calculate the map at the most zoomed in level first.

Required types of objects and object properties to generate: Nothing fancy, I am happy with the terrain according to the image above. But I admit I've been thinking of a similar setup where everything is a very very big city. That would be another question, though.

EDIT 4: Hopefully the final one.

OK, after reading a bit it seems that Perlin Noise is the way to go. I have one more question though (if someone cares to answer now that I have accepted one (actually two) answers :) ).

The perlin noise function takes doubles. What's the range for these doubles? [0-1[ ? Or can I happily send in my large integers?

---

Normally, all terrain/world generators work in the way you described - they are able to produce vast (random-looking) worlds from a very limited input data (set of parameters).

So, you might want to put further constraints on your question.

If anything will work for you or if you are just begging to research - take a look at different focuses and approaches here.

As for randomness/deterministic I am not sure that you really talk about randomness here and it can be a bit confusing, I think you only want to be able to create a lot of variations. So you might want to drop that from your search terms.

Take a look also at procedural generation (especially 'see also' and 'external links').

Personally, I think there is a lot of promise in the concept of terrain synthesis where you basically mix and match real terrain samples with some sort of transforming operations - which provides realistically looking terrain with desired properties.

EDIT: Here's an implementation of 'plasma fractals' (mid-point displacement) in processing.

If that is good enough for you then you could rework the algorithm to allow it to generate any part of the grid (I have a feeling it will boil down to hashing the coordinates to get random number seed around connecting lines, or everywhere).

Also you might work with different levels of detail with this method so that you can generate more detail closer to the point of view.

---

Have a look at Perlin Noise, it is a type of deterministic random data named after it's inventor Ken Perlin. If you search for "Perlin Noise" or "Ken Perlin" you will find a ton of articles on procedural textures and landscape generation.

---

Terrains are typically generated with fractals.

A simple method is Plasma Cloud algorithm, also known as Midpoint displacement algorithm. The general idea is:

1. Set some altitude values for the corners of the area.
2. Divide the rectangle into 4 smaller rectangles.
3. Calculate altitude for the new points as average of the surrounding points and add some random displacement value to that
4. Recursively divide each rectangle into smaller rectangles, and reduce the amount of displacement accordingly.

The random value is generated with a pseudo random number generator. If you give specific seed at the beginning, the same sequence of numbers is always generated.

Plasma cloud automatically generates smooth transitions, so no additional smoothing filter is needed.

Plasma cloud gives quite realistic landscapes, but they become boring in long term. Therefore, more complex algorithms (Perlin Noise, Ridged Perlin, etc.) may be used in addition. To get more variety, you could use one fractal (with low resolution) to adust the parameters of another fractal that calculates the actual values.

Fractals can be used to create textures and bumpmaps, too.

A good example of a program that generates landscapes with fractals and other procedural methods is Terragen. Terragen generates photorealistic images, so it is slow, but it has OpenGL preview that creates the landscape on-the-fly.

Edit: The problem with Plasma Cloud is that you can not generate a single point (or a small area) without generating the whole area. This is because it normally uses random number generator, which is dependent on the previous random number value.

However, you do not really need statistically good random number generator to generate terrain. Thus, you could replace the rand function with some function that calculates the random number from X and Y coordinates instead of previous value. Something like this (untested):

const int a = 0x7fffffff / 48271;
const int b = 0x7fffffff % 48271;

int displacement(int x, int y)
{
    int     seed, result;

    seed = x ^ ((y << 1) & 0x2AAAAAAA) ^ ((y >> 1) & 0x33333333);
    result = 48271 * (seed % a) - b * (seed / a);

    Return (result & 0xffff);
}

The above was modified from actual random number generator so that the seed is calculated from x and y. But maybe even some simpler function would be sufficient.

Edit2: To create infinite world, you can start for example with a rectangle of 10km x 10km. Use the displacement function above to set initial altitudes for the corners of the rectangle within which your target location is. Then start splitting the squares with Plasma Cloud algorithm. You only need to split and calculate those squares you are interested in, so you will quickly reach the target area (it is much like binary search).

---

What you've got is pretty much the only way to do it - basically you've created a function, f, which gives geographical data for f(x,y). Of course, you can have several functions which you use to build up the terrain.

In addition to Perlin Noise, lookup fractal landscape generation. These can produce some very naturalistic loooking terrain.

---

There are some papers listed here.

You mentioned Perlin Noise and that works well, especially if you need to generate terrains not topologically equivalent to a plane.

The Science of Fractal Images has a section on spectral synthesis which lets you tune the results based on the desired fractal dimension. The problem with this is that it's difficult to generate terrains other over a plane or torus.