28
\$\begingroup\$

I am looking for a function to generate a random tile-based map as the visual boundaries of the map change (by going through the map). I want the map to be infinitely large, and have maze-like structure.

However, if the world is infinite, going back to where a player has already been before raises a problem. The game must remember how everything back there actually looked like.

So, I was thinking - "How does Minecraft solve this issue?" and I thought to myself that they must be using some kind of random-number function with a seed, that can both go forward but also backwards, and in that way, re-generate old tiles exactly as they were, but in new instances.

What are your thoughts on this?

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ How is it my answer is at +5 yet the question is only at +2? This is one of the best questions on the front page right now. \$\endgroup\$
    – user744
    Aug 4, 2011 at 21:26
  • 2
    \$\begingroup\$ does not minecraft simply store the chunks you already visited/modified? \$\endgroup\$
    – FxIII
    Aug 5, 2011 at 7:02
  • \$\begingroup\$ @FxIII: Minecraft must, because you can modify the landscape. If you can't do that, storing the chunks is probably a waste, or at least an overcomplication. \$\endgroup\$
    – user744
    Aug 5, 2011 at 9:44
  • \$\begingroup\$ @Joe Wreschnig: Ok, Ok... I was afraid that I missed something really big! \$\endgroup\$
    – FxIII
    Aug 5, 2011 at 9:51

3 Answers 3

Reset to default
21
\$\begingroup\$

What you've noticed is the difference between a random number generator and a noise function. A random number generator spits out a different number each time you call it. A noise function takes some arguments - say, a map x and y - and spits out numbers with random-like statistical properties, but the same value for the same arguments every time, i.e. it is a proper mathematical function.

The two are very closely related. A noise function can simulate a random number generator, by passing in a different value each time - e.g. noise(1), noise(2), and so on. And a random number generator, dumped into a giant table, can act as a noise function. In both cases though, you're using the wrong tool for the job.

Minecraft in particular uses Perlin noise, a type of noise which is cheap to compute, and has a desirable property of being continuous in as many dimensions as you need - if you graph f(x) to f(x + 1), there won't be any sudden jumps. This makes it very useful for many things like texture modulation, volumetric clouds and gases, and terrain generation.

If you are looking for an implementation to start playing with, Ken Perlin's improved Perlin noise generator is one of the simplest implementations.

Improve this answer
\$\endgroup\$
6
  • 3
    \$\begingroup\$ Note that a lot of random number generators use a seed, and will generate the same set of numbers given the same seed. \$\endgroup\$
    – thedaian
    Aug 4, 2011 at 20:44
  • 3
    \$\begingroup\$ @thedaian: Which is not particularly useful in this case, unless you want to regenerate every number; a noise function lets you get the 500th number without having to generate 499 before that. \$\endgroup\$
    – user744
    Aug 4, 2011 at 20:48
  • \$\begingroup\$ Given Perlin Noise algorithm, is it possible to calibrate it? Consider I want the algorithm to be more likely to generate a pack of wall-tiles, and then a pack of space-tiles. \$\endgroup\$
    – Mathias Lykkegaard Lorenzen
    Aug 4, 2011 at 20:48
  • 3
    \$\begingroup\$ You have not read and understood the links I gave in six minutes. \$\endgroup\$
    – user744
    Aug 4, 2011 at 20:50
  • 2
    \$\begingroup\$ This answer would have been complete with Notch's blog post: notch.tumblr.com/post/3746989361/terrain-generation-part-1 \$\endgroup\$
    – hiddensunset4
    Aug 4, 2011 at 21:26
3
\$\begingroup\$

The way Minecraft controls its generation is by creating a level seed which is used to seed all the random number generation for the game. If a chunk doesn't exist on disk when it is requested, it will be generated using Notch's generation function based on the level's seed; it's then saved to disk for later.

It sounds like you're looking to achieve similar behaviour, so that's a safe way to go.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

As Joe pointed out, you're looking for a hash function. Generally, random functions are just hash functions seeded with the last returned number. So if Random() returned Hash(seed)=1234, a second call Random() would return Hash(1234), at so on.

If you're looking for a simple hashing function for pseudo random numbers, check out MurMurHash. I've implemented it in C# and can post it somewhere if you're interested. More detailed information of Perlin Noise, which uses such a hash function, can be found at here, and an implementation of it in C# is here.

All of this information came from a question I asked a year ago here on Stack Overflow. What you're looking into is called procedural content generation, so if you need more information, do a search for that. Happy terrain-generating!

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ -1. Perlin noise's hash, at it is, bears no resemblance to the techniques used in MMH or other cryptographic hashing routines; that C# code is garbage that appears to just do linear interpolation between random values; it requires far more memory than proper Perlin noise and likely runs slower. \$\endgroup\$
    – user744
    Aug 4, 2011 at 21:24
  • 1
    \$\begingroup\$ @Joe - I'm sorry you feel so strongly about your implementation of Perlin Noise. Perlin Noise is itself a concept of turning a hash function into a continuous noise function. I've been generating lots of Perlin Noise very effectively with MurMurHash. As for the C# code, it's an example of how to programmatically determine the value of a single point in 2D Perlin Noise. I would never use it in production, but it is, in my opinion, easier to walk through than the code you posted. \$\endgroup\$
    – dlras2
    Aug 4, 2011 at 22:06
  • 1
    \$\begingroup\$ The OP had no knowledge of noise or hashing, so I simply attempted to provide references in hopes that they would further investigate and decide on their own how to implement whatever it is they needed to do. \$\endgroup\$
    – dlras2
    Aug 4, 2011 at 22:06
  • \$\begingroup\$ "Perlin Noise is itself a concept of turning a hash function into a continuous noise function." No, Perlin noise is one of the continuous noise functions invented by Ken Perlin (and not the one he called "simplex noise"). Not all continuous noise functions are Perlin noise; not all continuous noise functions are even gradient noise, of which Perlin noise is a particular example; the thing you linked to is not gradient noise, but value noise. \$\endgroup\$
    – user744
    Aug 5, 2011 at 9:19
  • \$\begingroup\$ The code in your link is "easier to walk through" because it is not Perlin noise; it is not as smooth; it uses far more resources; in short, it is easier to walk through because it is dumber. \$\endgroup\$
    – user744
    Aug 5, 2011 at 9:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .