Building an Infinite Procedurally-Generated World

The game FUEL is a great example. The game covers 14,400 km² but doesn't repeat itself.

http://en.m.wikipedia.org/wiki/Fuel_(video_game)

I agree that using one technique for an infinite world is probably going to get boring pretty quickly, and you can probably get more leverage out of a finite world.

But even with an infinite landscape, I think you could improve the variety by using a generator at different scopes - if your landscape is just one constant type of terrain, like a field, things will get boring. You might have a wide variety of rivers and trees, but the basic idea is the same. But if you have another generator controlling the terrain type - going between plains, desert, mountains, etc., that would be really interesting. At the small scope, variation in trees and water is still the same level of change, but there is also a larger scope that changes the overall feel at a much larger radius.

Heh. I agree, and I'm doing the same thing for my game.

As for Perlin noise, check out Simplex noise. It's what Perlin designed AFTER Perlin noise. I use 4D Simplex fractals to create my game world which tiles seamlessly when scrolling up/down as well as left/right. And I'm filling the world with random-but-connected cities, factions etc. That's where interesting emergent gameplay comes from.

BTW, I have a few writeups (quite technical) on the correct implementation of Simplex noise on spiralcode.wordpress.com

Unintentional, that's what happens when you write a toy not intending to publish it. Article has been updated with credit.

I don't see any free or open source sprites. There is nothing on the website indicating that they are free or open source. Are you asking someone to credit the creator of sprites they paid money to use? That's absurd to me. It's like wanting this guy to credit Verizon or Time Warner for the bandwidth he paid for. If Oryx sprites were open source, or free for noncommercial use, I think it would be a legitimate claim. Otherwise, not so much, because it boils down to advertising. Crediting someone else is advertising someone else, and I believe giving someone actual money automatically means they don't need to also advertise for them.

Well, if you had a mathematical model of continent formation from actual geology, you could use some of the noise generation to obtain values for the model's free parameters, and then just run the simulation forward (possibly approximating it very cheaply since you don't need maximal real-world accuracy) to get your continents.

http://www-cs-students.stanford.edu/~amitp/game-programming/... was a springboard for many people dealing with this problem. That whole site is worth a read if you're interested in game development at all.

(Author here): One approach is to use multiple layers of noise configured with different parameters. By joining multiple layers you can give the appearance of things like ocean, flatlands, and mountains.

Also, cannot recommend Amit Patel's stuff enough. That guy is a fountain of knowledge for all things gamedev.

What goes wrong if you just use Perlin noise for a height map and pick a "sea level" threshold? That also has the advantage of giving you an interesting seabed, if you have the ability to see underwater.

You'd still want various kinds of local mutation to create interesting features, though. For inspiration, you might look at how games like Angband and Crawl combine procedurally-generated overall level design with pre-constructed "vaults". A similar technique, with enough variations to avoid looking obvious, could work to embed more unusual features in an otherwise procedurally-generated set of continents.

Beyond that, you might also want a dedicated coastline-and-river generator, which picks appropriate high mountains, puts the top of a river there, and has it wend its way down altitude (eroding as needed) until it reaches the "ocean". Throw in some appropriate generation of beaches, riverbanks, and ocean cliffs.

In infinite generation, it's tricky to meaningfully do it. If you can constrain your space, I've had good luck with Voronoi generation and using those as continental plates. A little edge randomness, and I figure out what subducts, what separates, which plates are water and which plates aren't, and so on. Couple this with an iterative erosion mechanic and you can do some neat stuff.

("Look, this is Perlin noise" made this a disappointing article for me. It's the sort of thing you saw on GameDev.Net fifteen years ago...)

The last time I made a world generation algorithm for a voxel engine prototype I got reasonable results through the judicious combination of different types of noise, (specifically simplex, ridged and turbulence noise) and transforming the result using cubic hermite splines for added control, provided you are okay with generally only having one or two main continents (three and four do occur, but are much less common).

This image shows 16 possible world maps (I found it useful to just have them appear next to each other in the world so I could quickly get an overview of the consequences of tweaking parameters): http://imgur.com/dthr7O2

This is the algorithm that generated the world (written in C#). permutation is a random ordering of the numbers 0 to 255, repeated twice. HermitePoints take an x and y coordinate and a slope. Noise functions take an x and y coordinate, a number of octaves, a frequency and a permutation. Turbulence and ridged noise output results in the domain [0, 1], simplex noise in the domain [-1, 1].

  private static Chunk GenerateChunk(short chunkX, short chunkZ, int seed, byte[] permutation)
  {
      var chunk = new Chunk(chunkX, chunkZ);

      int worldMapSize = 256;
      short maxHeight = (short)Math.Min(worldMapSize >> 2, Chunk.CHUNK_HEIGHT);

      float[] worley = new float[2];

      HermiteSpline continentCurve = new HermiteSpline(new[]
      {
          new HermitePoint(0f, 0f, 0f), new HermitePoint(0.07f, 0.03f, 1f), new HermitePoint(0.12f, 0.1f, 0.7f),
          new HermitePoint(0.21f, 0.18f, 1f), new HermitePoint(0.24f, 0.2455f, 0f), new HermitePoint(0.26f, 0.26f, 1f), new HermitePoint(1f, 1f, 1f)
      });
      HermiteSpline continentMask = new HermiteSpline(new[]
      {
          new HermitePoint(0f, 0f, 0f), new HermitePoint(0.25f, 0f, 0f), new HermitePoint(0.4f, 1f, 0f), new HermitePoint(1f, 1f, 0f)
      });
      HermiteSpline plateMountainCurve = new HermiteSpline(new[]
      {
          new HermitePoint(0f, 0f, 0f), new HermitePoint(1f, 1f, 3.5f)
      });

      for (short x = 0; x < Chunk.CHUNK_SIZE; x++)
      {
          for (short z = 0; z < Chunk.CHUNK_SIZE; z++)
          {
              int globalX = (chunkX << Chunk.CHUNK_SIZE_LOG2) + x;
              int globalZ = (chunkZ << Chunk.CHUNK_SIZE_LOG2) + z;

              //Subdive the world into squares, each of which contains an independent world map
              //The edges of each square are lowered so that each map is separated by oceans
              float xSeparator = (float)Math.Sin((globalX & (worldMapSize - 1)) * MathHelper.Pi / worldMapSize);
              float zSeparator = (float)Math.Sin((globalZ & (worldMapSize - 1)) * MathHelper.Pi / worldMapSize);
              float rectSeparator = (float)Math.Min(1, 3 * Math.Min(xSeparator, zSeparator));
              float circleSeparator = xSeparator * zSeparator;
              float mapSeparator = rectSeparator * 0.375f + circleSeparator * 0.575f + 0.05f;

              //Use turbulence noise to get the typical clumped shape of continents and add some simplex and ridged noise for the thinner shapes
              float continentNoise1 = Noise.Turbulence(globalX, globalZ, 8, worldMapSize, permutation);
              float continentNoise2 = Noise.Simplex(globalX, globalZ, 8, worldMapSize * 0.16f, permutation) * 0.5f + 0.5f;
              float continentNoise3 = Noise.Ridged(globalX, globalZ, 8, worldMapSize * 0.5f, permutation);
              continentNoise2 *= continentNoise2;
              continentNoise3 *= continentNoise3;
              float continentHeight = continentNoise1 * 0.5f + continentNoise2 * 0.25f + continentNoise3 * 0.125f;
              float baseHeight = continentCurve.Map(continentHeight * mapSeparator);

              //Add mountains caused by convergent continental plate boundaries
              float continentMult = continentMask.Map(baseHeight);
              float plateMountainNoise1 = Noise.Ridged(globalX, globalZ, 8, worldMapSize * 0.4f, permutation);
              float plateMountainNoise2 = Noise.Simplex(globalX, globalZ, 8, worldMapSize * 0.2f, permutation) * 0.5f + 0.5f;
              float plateMountainNoise = plateMountainNoise1 * 0.66f + plateMountainNoise2 * 0.33f;
              float plateMountainHeight = plateMountainCurve.Map(plateMountainNoise) * continentMult;

              //Apply the map separation
              float finalHeight = baseHeight + plateMountainHeight;

              //Convert the height from range [0,1] to range [1,255]
              byte height = (byte)(finalHeight * (maxHeight - 1) + 1);

              for (short y = 0; y < height; y++)
              {
                  chunk[(short)x, y, z] = (byte)((y + 1) * 255 / (maxHeight + 1));
                  chunk.SetStack((short)x, z, new short[] { height, (short)(Chunk.CHUNK_HEIGHT - height) });
              }
          }
      }

      return chunk;
  }

This isn't directly relevant, but a while ago (nearly 2 years, apparently ._.) I wrote a thing that generates islands based on height contour lines and heightmaps based on them...

https://dl.dropboxusercontent.com/u/1094010/island_compiled....

I made a generator for non-infinite worlds(specifically, Ace of Spades 0.x, which is a 512x512x63 colored-cube space) that created "faucets" for land and water, flood filled a low-res "biome" tilemap from them, and then applied some noise and interpolation to the tilemap, plus some heightmap modification to make a river. The larger number of passes creates a very "hand-generated" result, although a careful observer will discern that the edges are all slightly rectangular. One of the major benefits of the biome approach is that I could define the average height and deviations of the heightmap, making it easy to position mountains adjacent to flat open fields.

I've never seen the Perlin approach as being sufficient for making terrain that is _realistic_, since real terrain is shaped through iterative processes, not analytic ones.

[0] Example: http://imgur.com/txVfRYV

The real world partitions land and water by treating values below a certain threshold as ocean. That's not the problem.

There are tons of good terrain generators. Try Google. VistaPro, from the 1980s, is the classic.[1]

So far, nobody has built a procedural city generator good enough to generate a detailed city at ground level. This is one of the better ones, but the result comes out looking like a modern prison.[2]

[1] https://en.wikipedia.org/wiki/VistaPro [2] http://orphancity.tumblr.com/

Putting a probabilistic bell curve on top of simplex noise works generally well.

Here's what I did: https://thefiletree.com/espadrine/art/island.html?plug=none

I did this for a project a while back with reasonable results. The algorithm was this: Test each tile for distance to water (you don't have to get this absolutely perfect, just check in about 8 different directions from the centre of the tile). The closer the tile is to water, apply a scaling factor to the elevation, such that at MAX_DISTANCE you scale by 1, at 0 (water's edge) you scale by a factor of 0 (ie you will always have 0 elevation. The exact curve of the scaling factor can be played around with to give you sharper or smoother coastlines... You can even slowly vary the scaling function so that you can have everything from river deltas to cliffs in different parts of the world.

I like your idea here. I think the downside of this approach is you must scale your random data points by a scaling factor to get them in a known range.