Infinite world architecture, how do you do it?

WIP games, tools & toy projects Cube World Projects
#1

I was thinking of Minecraft the other day and i wondered how he did it. So, i tried coding something really fast using simple arrays, but i soon encountered a wall.

Say the center of the world is at (0,0,0) and the world is supposed to be infinite in the X and Y direction, you can’t have negative arrays, even though the X and Y will have to be negative somehow.

For example, the center is at world[0][0] if the player moves left, you can’t access the array with, say, world[-1][0];

So is the solution to start creating the world really far like at world[1073741823][1073741823], and just hope the player never reaches the end of the infinite… finite world? (of course, the “world” array would contain “chunks” of, says 161616 cubes) Or you could have an even bigger array on top of “world”, say, “universe” which would contain other “world” arrays?

Also, i read the old thread by Markus Persson, and he was talking about octrees and chunked rendering. He dismissed the former as being too slow in favor of chunked rendering (which i have no idea what it is exactly, besides what the name implies). I looked a bit into it, but it seems i lack the mathematical knowledge to understand the reasoning behind it’s choice. Could someone explain it in plain english for me? :slight_smile:

Well, where do i start? Is there a good read somewhere about this topic?

#2

A good place to start would be the minecraft wiki, which has the minecraft save formats documented pretty well (and I’ve been adding to as I find bits out from Tectonicus):

http://www.minecraftwiki.net/wiki/Alpha_Level_Format
http://www.minecraftwiki.net/wiki/Alpha_Level_Format/Chunk_File_Format

Basically, the world is split into 16x16x128 (think a 16x16 square floor, 128 blocks high) chunks, each of which has it’s own save file. In memory they’re probably just held as a series of 16x16x128 arrays (that’s how I’m doing it at any rate).

As the player walks around you need to convert their world position into a chunk position (basically just divide by 16 and drop the remainder). Then you can figure out what chunks the player has near them quite easily. Any nearby chunks that aren’t loaded into memory need to be loaded from file, and any that don’t have a file need to be generated via the level generator.

On top of that you want some kind of cache, so you hang on to old chunks in the hope that they’ll be useful soon (say, the player turns around and starts walking back again).

The basics are pretty easy. The tricky bits come when you have to have additional caches (like building display lists for the geometry), and dealing with writing back the results of the player’s changes to disk, and having a world generator that can operate on individual chunks at a time.

#3

Ah, i see. Thanks for the link!

So he’s using a procedural algorithm to generate the world whenever you reach an undiscovered chunk, which makes the world seem seamless.

Similar to a perlin noise, i guess, but in 3D?

It is interesting. Also, i didn’t think of writing chunks to disk.

I’ll have to test it, but it does mean that the program is constantly accessing the disk since a 16x16 chunk of land is really really small, maybe there’s some optimization to do there. Although, the problem he has is that if you look up (or down for that matter), there’s always a chance of seeing the top 128th cube of the sky, so you must have it in memory…

#4

Streaming in and out to disk isn’t too bad, it can be done in a background thread so it won’t interrupt your framerate and walking speed is slow enough that you have plenty of time to load things before you actually get near to them.

Vertically is more tricky - you could divide the world into chunks vertically as well, but gravity gets in the way as you can fall a lot faster than you can walk. Plus things like water simulation and lighting need the whole vertical slice loaded in order to calculate properly. I believe Notch has said he has no plans to increase the size of the world vertically. That makes sense I think, while it’d be nice to have a ‘taller’ world, the existing height of 128 is still plenty huge and it doesn’t really restrict the gameplay in any way.

Oh, and someone was experimenting with 3d perlin noise for minecraft levels here: http://www.gamedev.net/community/forums/mod/journal/journal.asp?jn=259175&reply_id=3734714

It’s obviously not as detailed or complicated as minecrafts, but it’s the most interesting discussion of that kind of level gen that I’ve seen.

#5

Yeah, but what about multi-player? If you have even 16 players going in different directions at the same time… :smiley:

#6

Then your server needs to hold chunks surrounding 16 players (although since a server only has to deal with local logic like movement, you don’t have to have chunks in the far distance loaded for drawing). Which is one of the reasons minecraft servers are pretty heavy on the memory.

#7

If the world is randomly generated, and the random values are seeded (say using that location of the world), then you can drop any section of the world when someone leaves. This avoids having to keep every part of the world so far in memory. You do need to keep a record of the changes to that section and reapply those when you re-generate that section. i.e.


    World world = new World( x, y );
    world.apply( changes.get(x, y); );

In terms of allowing negative indexes in arrays this is quite easy to do. I built my own dynamic array a few years ago which allows you to move into negative space (it also allows you to set values outside the array and just fills in the gaps with null). Standard version is here and a 2D version is here.

To move into negative space I keep track of an offset stating how far I’ve extended into negative space. I then add this to the index value of any future checks.

An alternative is just use a map. This would be better if your dotting around the world a lot randomly as it would allow you to avoid having to resize as often and would avoid having tonnes of empty space between entries.

One of the big problems with infinite worlds though is that they can quickly become dull (I’ve not played Minecraft so this is no reflection on that game).

edit: Fixed the code tag.

#8

Interesting discussion. What would be a good method for generating “nice looking” seamless terrain in discrete chunks?

#9

This interview with Markus was linked a while back:

[quote]11. Ahawks This may be “confidential” information, but I have to ask: As a developer, I am amazed at the amazing world that’s created dynamically. Towering mountains, twisting caves opening up to caverns, islands, precious ores sprinkled throughout, etc. Notch, could you explain at a high level how the world generation algorithm does this?

I’m not sure how to explain it without getting technical… The complicated high level technical version is: First I generate a linearly interpolated 3d perlin noise offset along the y axis. I fill that in so that everything except the top x blocks is stone, then I do a second pass to add features like grass, trees, gravel, sand, caves and flowers. The world is generated in chunks of 16x16x128 blocks, based of pseudorandom seeds that are a mix of the level base seed and the chunk location in the world. This ensures that you always get the same terrain in an area regardless of what direction you traveled there from.
[/quote]