1. Post #1
    Aces's Avatar
    March 2011
    147 Posts
    Source

    Terrain generation, Part 1

    I’ve been promising to write a technical post on Minecraft for a while, but never really got around to doing so. I’m on a tiny airplane now, though, with nowhere to run, so here we go!

    One of the most complex parts of Minecraft is the terrain generation. When I changed the game over from being just single zones of a map to an infinite map, the terrain generation got a whole lot more complicated, as terrain needs to get generated on the fly as the player explores, and it has to be the same no matter what direction the player approaches it from.

    1) How infinite is it?

    First of all, let me clarify some things about the “infinite” maps: They’re not infinite, but there’s no hard limit either. It’ll just get buggier and buggier the further out you are. Terrain is generated, saved and loaded, and (kind of) rendered in chunks of 16*16*128 blocks. These chunks have an offset value that is a 32 bit integer roughly in the range negative two billion to positive two billion. If you go outside that range (about 25% of the distance from where you are now to the sun), loading and saving chunks will start overwriting old chunks. At a 16/th of that distance, things that use integers for block positions, such as using items and pathfinding, will start overflowing and acting weird.

    Those are the two “hard” limits.

    Most other things, like the terrain generation seeds and entity locations use 64 bit doubles for locations, and they do much subtler things. For example, at extreme distances, the player may move slower than near the center of the world, due to rounding errors (the position has a huge mantissa, the movement delta has a tiny, so it gets cut off faster). The terrain generator can also start generating weird structures, such as huge blocks of solid material, but I haven’t seen this lately nor examined exactly what behavior causes it to happen. One major problem at long distances is that the physics starts bugging out, so the player can randomly fall into ground blocks or get stuck while walking along a wall.

    Many of these problems can be solved by changing the math into a local model centered around the player so the numbers all have vaguely the same magnitude. For rendering, Minecraft already uses local coordinates within the block and offset the block position relative to the player to give the impression of the player moving. This is mostly due to OpengGL using 32 bit floats for positions, but also because the rounding errors are extremely visible when displayed on a screen.

    We’re probably not going to fix these bugs until it becomes common for players to experience them while playing legitimately. My gut feeling is that nobody ever has so far, and nobody will. Walking that far will take a very long time. Besides, the bugs add mystery and charisma to the Far Lands.

    2) Isn’t that terrain shape pretty awesome?

    In the very earliest version of Minecraft, I used a 2D Perlin noise heightmap to set the shape of the world. Or, rather, I used quite a few of them. One for overall elevation, one for terrain roughness, and one for local detail. For each column of blocks, the height was (elevation + (roughness*detail))*64+64. Both elevation and roughness were smooth, large scale noises, and detail was a more intricate one. This method had the great advantage of being very fast as there’s just 16*16*(noiseNum) samples per chunk to generate, but the disadvantage of being rather dull. Specifically, there’s no way for this method to generate any overhangs.

    So I switched the system over into a similar system based off 3D Perlin noise. Instead of sampling the “ground height”, I treated the noise value as the “density”, where anything lower than 0 would be air, and anything higher than or equal to 0 would be ground. To make sure the bottom layer is solid and the top isn’t, I just add the height (offset by the water level) to the sampled result.

    Unfortunately, I immediately ran into both performance issues and playability issues. Performance issues because of the huge amount of sampling needed to be done, and playability issues because there were no flat areas or smooth hills. The solution to both problems turned out to be just sampling at a lower resolution (scaled 8x along the horizontals, 4x along the vertical) and doing a linear interpolation. Suddenly, the game had flat areas, smooth hills, and also most single floating blocks were gone.

    The exact formula I use is a bit involved (and secret!), but it evolved slowly over time as I worked on the game. It still uses the 2D elevation and noisyness maps, though.

    STILL TO COME, ON TERRAIN GENERATION:

    - Biomes!
    - Caves and Large Features
    - Trees, Lakes, and Small Features
    - The nether!
    They’re not infinite, but there’s no hard limit either.
    The terrain generator can also start generating weird structures, such as huge blocks of solid material, but I haven’t seen this lately nor examined exactly what behavior causes it to happen.
    Dun dun dunnnn. :monocle:
    Reply With Quote Edit / Delete Reply United States Show Events Late Late x 23Informative Informative x 6Artistic Artistic x 2Winner Winner x 1 (list)

  2. Post #2

    July 2010
    2,044 Posts
    I challenge someone to get to the point where the savegame starts fucking up.
    Reply With Quote Edit / Delete Reply United Kingdom Show Events Agree Agree x 4 (list)

  3. Post #3
    Gold Member
    Mikesword221's Avatar
    April 2009
    4,333 Posts
    Notch said they weren't infinite a long time ago.

    Edited:

    I challenge someone to get to the point where the savegame starts fucking up.
    Old, but same principles.
    Reply With Quote Edit / Delete Reply United States Show Events Informative Informative x 9Late Late x 1Winner Winner x 1Dumb Dumb x 1 (list)

  4. Post #4
    Aces's Avatar
    March 2011
    147 Posts
    I challenge someone to get to the point where the savegame starts fucking up.
    Or where they start finding towers or diamond ore.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 4 (list)

  5. Post #5
    Gold Member
    Mikesword221's Avatar
    April 2009
    4,333 Posts
    As you can see, Notch has implemented floating islands. It's just really big. :buddy:
    Reply With Quote Edit / Delete Reply United States Show Events Winner Winner x 1 (list)

  6. Post #6
    Gold Member
    _Kent_'s Avatar
    June 2009
    2,376 Posts
    Now how do seeds fit into this?

  7. Post #7
    Aces's Avatar
    March 2011
    147 Posts
    Since we're on the topic of glitchy worlds has anyone ever found natural cobblestone on a newly generated map?
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 14Disagree Disagree x 1Late Late x 1 (list)

  8. Post #8
    ~gay boi~
    Chickens!'s Avatar
    July 2010
    14,336 Posts
    Since we're on the topic of glitchy worlds has anyone ever found natural cobblestone on a newly generated map?
    1 block in the sky.
    I thought it was odd because i don't see how cobblestone would even be on a list of blocks to be generated.

  9. Post #9
    GOLF WANG
    Alec W's Avatar
    August 2006
    7,596 Posts
    Dungeons have normal cobble don't they?
    Reply With Quote Edit / Delete Reply Spain Show Events Agree Agree x 27 (list)

  10. Post #10
    Gold Member
    sbradford26's Avatar
    March 2009
    5,019 Posts
    This happened to me after converting.
    Reply With Quote Edit / Delete Reply United States Show Events Winner Winner x 61Disagree Disagree x 5Funny Funny x 2Informative Informative x 1 (list)

  11. Post #11
    FAT CAT ACCOUNTANT
    Esteam's Avatar
    September 2010
    4,775 Posts
    Since we're on the topic of glitchy worlds has anyone ever found natural cobblestone on a newly generated map?
    I've found natural dirt on a newly generated map.

    I haven't seen a single space in the bedrock in a long time, has anyone seen a split in the bedrock?
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 4 (list)

  12. Post #12
    nox
    nox's Avatar
    March 2007
    2,199 Posts
    Funny, I had chunk glitches yesterday, I think it was due to walking a few miles from the original spawn location, when I quit and came back I had lost all my items and a huge random chunk of hill was in the spot my road was at.

  13. Post #13
    Aces's Avatar
    March 2011
    147 Posts
    I've found natural dirt on a newly generated map.

    I haven't seen a single space in the bedrock in a long time, has anyone seen a split in the bedrock?
    Yes i've seen lots.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 2 (list)

  14. Post #14
    Toothpick's Avatar
    January 2010
    1,494 Posts
    I've found natural dirt on a newly generated map.

    I haven't seen a single space in the bedrock in a long time, has anyone seen a split in the bedrock?
    Nearly everytime I reach bedrock.

  15. Post #15
    Aces's Avatar
    March 2011
    147 Posts
    I've found natural dirt on a newly generated map.

    Um, there is natural dirt everywhere, it's prolly the 2nd most used block in generating worlds.
    Reply With Quote Edit / Delete Reply United States Show Events Disagree Disagree x 2 (list)

  16. Post #16
    FAT CAT ACCOUNTANT
    Esteam's Avatar
    September 2010
    4,775 Posts
    Um, there is natural dirt everywhere, it's prolly the 2nd most used block in generating worlds.
    lol wow
    Reply With Quote Edit / Delete Reply United States Show Events Dumb Dumb x 1 (list)

  17. Post #17
    Aces's Avatar
    March 2011
    147 Posts
    lol wow
    wat
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 2 (list)

  18. Post #18
    FAT CAT ACCOUNTANT
    Esteam's Avatar
    September 2010
    4,775 Posts
    you missed the joke entirely
    Reply With Quote Edit / Delete Reply United States Show Events Funny Funny x 4 (list)

  19. Post #19
    Aces's Avatar
    March 2011
    147 Posts
    you missed the joke entirely
    Oh
    Reply With Quote Edit / Delete Reply United States Show Events Funny Funny x 25Friendly Friendly x 3Winner Winner x 2Dumb Dumb x 1 (list)

  20. Post #20
    Gold Member
    sbradford26's Avatar
    March 2009
    5,019 Posts
    I've found natural dirt on a newly generated map.

    I haven't seen a single space in the bedrock in a long time, has anyone seen a split in the bedrock?
    I once found a lake in the bedrock on my server, but that is about it. The sad part is that that map was soo screwed up I had to delete it.

  21. Post #21
    I'm dumb! You don't have an excuse!
    MacTrekkie's Avatar
    July 2009
    5,485 Posts
    you missed the joke entirely
    It wasn't a very good one to be honest.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 28Friendly Friendly x 1 (list)

  22. Post #22
    Gold Member
    GamerKiwi's Avatar
    November 2006
    5,010 Posts
    This happened to me after converting.
    All that happened to my converted map was a bunch of areas where my guy would randomly become stuck in place.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 1 (list)

  23. Post #23
    FAT CAT ACCOUNTANT
    Esteam's Avatar
    September 2010
    4,775 Posts
    It wasn't a very good one to be honest.
    oh no im sad now
    Reply With Quote Edit / Delete Reply United States Show Events Friendly Friendly x 13Funny Funny x 2Dumb Dumb x 1 (list)

  24. Post #24
    totally not overcompinsating for lack of size elsewhere...
    Im-Bored's Avatar
    December 2007
    491 Posts
    oh no im sad now
    Did it hurt your self Esteam? :downsrim:
    Reply With Quote Edit / Delete Reply United States Show Events Funny Funny x 52Winner Winner x 5Agree Agree x 1Zing Zing x 1 (list)

  25. Post #25
    Gold Member
    Upgrade123's Avatar
    January 2008
    5,478 Posts
    This happened to me after converting.
    Holy shit.

  26. Post #26
    FAT CAT ACCOUNTANT
    Esteam's Avatar
    September 2010
    4,775 Posts
    Did it hurt your self Esteam? :downsrim:
    thats not even how you spell e oh

    ha i get it !!!
    Reply With Quote Edit / Delete Reply United States Show Events Funny Funny x 20Winner Winner x 2Zing Zing x 1 (list)

  27. Post #27
    Gold Member
    VistaPOWA's Avatar
    October 2008
    8,370 Posts
    This happened to me after converting.
    Could you upload that map?
    Reply With Quote Edit / Delete Reply Hungary Show Events Agree Agree x 1 (list)

  28. Post #28
    Apple extraordinaire~ ♥
    Reagy's Avatar
    November 2005
    16,224 Posts
    I've found natural dirt on a newly generated map.

    I haven't seen a single space in the bedrock in a long time, has anyone seen a split in the bedrock?
    I've had a lake/line of water which started from the surface then went all the way down to bedrock then past it.
    I'm guessing a set of chunks all got corrupted in that world.

  29. Post #29
    TheStateTrooper's Avatar
    September 2009
    2,067 Posts
    Do the shit in those videos do the same thing in SMP maps?

    That'd be sweet.

  30. Post #30
    Diamond Member
    MedicWine's Avatar
    January 2009
    8,122 Posts
    This happened to me after converting.
    Whats with the hacked in tools. I'm not saying you hacked in all those ores or anything, but why did you have to hack in diamond tools when you have all that ore. And why didn you hide it when the video started? And why did you hack in 64 stacks of tools?

  31. Post #31
    Facepunch Staff
    layla's Avatar
    March 2010
    2,540 Posts
    Now how do seeds fit into this?
    It's a seed for a random number generator which his perlin noise algorithms use.

  32. Post #32
    100% Homemade
    ZestyLemons's Avatar
    September 2007
    8,318 Posts
    Whats with the hacked in tools. I'm not saying you hacked in all those ores or anything, but why did you have to hack in diamond tools when you have all that ore. And why didn you hide it when the video started? And why did you hack in 64 stacks of tools?
    He used InvEdit to give himself 64 of every tool I guess, so he doesn't need to ever get a new pick for example.

  33. Post #33
    Gold Member
    ruarai's Avatar
    December 2009
    1,358 Posts
    Going to the limits and posting the results

    Edited:


    a weird grassless mountain

    Edited:


    really cool landscape

  34. Post #34
    FAT CAT ACCOUNTANT
    Esteam's Avatar
    September 2010
    4,775 Posts
    Going to the limits and posting the results

    Edited:


    a weird grassless mountain
    That stuff happens more often than you would think.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 5Disagree Disagree x 2 (list)

  35. Post #35
    Financial Expert
    Matix's Avatar
    July 2008
    2,144 Posts
    Cobble can be generated naturally where water meets lava.

  36. Post #36
    FAT CAT ACCOUNTANT
    Esteam's Avatar
    September 2010
    4,775 Posts
    But in the air?

  37. Post #37
    Gold Member
    ruarai's Avatar
    December 2009
    1,358 Posts
    im at 35000,1000 but theres still nothing interesting

  38. Post #38
    Gold Member
    Doomish's Avatar
    June 2009
    14,943 Posts
    I challenge someone to get to the point where the savegame starts fucking up.
    It was done a long time ago, at the start of Infdev in fact.

    Edited:

    Notch said they weren't infinite a long time ago.

    Edited:



    Old, but same principles.
    This is basically what still happens today.

  39. Post #39
    Gold Member
    sbradford26's Avatar
    March 2009
    5,019 Posts
    He used InvEdit to give himself 64 of every tool I guess, so he doesn't need to ever get a new pick for example.
    Yes I was making some large buildings underground in that world so I hacked my tools.

  40. Post #40
    Financial Expert
    Matix's Avatar
    July 2008
    2,144 Posts
    But in the air?
    Oh, no. That's definitely an anomaly.