Sign in to follow this  

Splitting world generation into chunks

Recommended Posts

I'm trying to learn about procedural 2D world generation but I'm a little confused about something. I already have a good algorithm (http://www.roguebasin.com/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels) that randomly generates the kind of terrain i want, but the problem is I don't know how to scale this effectively for 'infinitely' large worlds.

 

One of the simple obvious solutions i thought of was to just use a 2D array like so:

int[][] field = new int[Short.MAX_VALUE][Short.MAX_VALUE];

Where each int in the array represented information on a tile and it's index values represented the coordinates of each tile. I would then just simply run the algorithm on the field to generate the level's terrain.

 

Problem is, this line of code doesn't work. I get a java.lang.OutOfMemoryError. Even if it did work i'd imagine it would take forever just to populate the field.

 

 

It's obvious i need to split the field so that i can just run the population algorithm onto the local area near the player, and dynamically generate the rest of the terrain as the player walks around.

 

I'm thinking of splitting the world into chunks. I'm not really sure how to do this though. If all I did was split the field into chunks and populate them individually, then i'd have abrupt terrain changes at the border between each chunk. I need the terrain to be consistent accross chunks. It seems if I went for this approach I would need each chunk to "know about" its neighbouring chunks as its being generated to ensure consistent, seamless terrain between them.

 

I'd imagine i'd have to do something like check the 8 neighbouring 2D arrays together, patch together the ones that are loaded, running the population algorithm, then splitting the array again to form the target chunk. It seems like a really complicated solution i don't think its a good one. Can anyone give me tips?

Share this post


Link to post
Share on other sites

32768^2 seems a bit large to me, but I agree it's close to infinite :)

(4 bytes * (327688^2) is 4GB. You'll need a 64bit JVM for that, and sufficient real memory.)

 

The images I have seen from your previous post, suggest you don't need 32bit (an int) for the algorithm. A single bit may be sufficient. That would need 128MB, which is much more manageable. (32768^2)/8 bytes).

 

 

If the algorithm just needs a single bit at each field, that would be the way to go, imho. Java may have dedicated bitvectors (yep it does, look for BitSet, for Java 7), else you may need to build one yourself.

You can store your entire field in memory, and run the algorithm.

 

 

If you do need an 'int' for the algorithm, yeah , chunks seem the direction to go. I would probably make all chunks and store them onto disk.

For example chunks of 1024x1024 fields, that gives you 32x32 chunks, if you want it that big.

 

The algorithm seems to be designed for a contiguous range over the map. The simplest way to achieve that is to build a cache for the chunks.

On top of that make an interface that gives read/write access to field positions. It accesses the cache, and loads new chunks as needed, and saving/discarding chunks you didn't use for a while (called LRU caching).

 

Then run the algorithm, using the cache. Don't forget to flush the cache afterwards :)

Share this post


Link to post
Share on other sites

As Alberth says, store it as a bit image if you can. You may also be able to run RLE or some other type of compression on each line / sub grid of the map.

 

If memory is an issue or you want to store more than 1 bit, another suggestion for an alternative, rather than storing / loading from disk, given that the procedural CA algorithm described should run quite quick:

 

  1. In development, run the cave generator on the whole 32768 x32768 (or whatever) area. Split this up into chucks as Alberth suggests.
  2. However, instead of storing them to disk, store into a special structure ONLY the boundary lines (forming a grid) of the chunks. Then, as you run the game and you need to display each chunk, run the procedural generator in realtime on each chunk needed (so you have a most recently used cache) as it comes into view.

 

As you run the procedural generator on each chunk, fix it so that the chunk boundary will be read in the cellular automata, but not written. This will probably give a slightly different result than the original caves, but it should be repeatable, providing you use a repeatable random number generator seeded in a standard manner per chunk (look at how worley noise is generated for an example of this).

 

There may be an even better way of doing this, but this is just off the top of my head, should allow really huge areas with little memory use. Bonus points if you figure out a chunk may be needed in advance, and spread the generation over several frames to avoid any frame stutter. :)

Share this post


Link to post
Share on other sites
Posted (edited)
If all I did was split the field into chunks and populate them individually, then i'd have abrupt terrain changes at the border between each chunk

 

an algo that's repeatable, like perlin noise, is required for that.  if you can pass the algo an offset (UL corner of the chunk) and have it generate from there, your're ok. if not, you'll need to switch algos, or fixup seams.

 

i do heighmap (ground mesh) seam fixups (heighmap blended seams) in Caveman 3.0.  But there i'm only blending two heigtmap values based on distance from the seam. You're talkiing about making non-tile-able proceedurally generated cave interior level sections tile-able - without hand editing. 

 

The basic problem would be where one tile is "hollow" at the seam area, and the adjacent tile is solid rock.  You could carve out the solid rock a bit, or fill in and close off the hollow edge. 

 

Places where both tiles were hollow at the seam might need some cleaning up as well to look natural.

 

You really should be thinking about how big you want the map, how its stored, and the ram requirements, before you select an algo in the first place. That way you don't "code yourself into a corner"., like you have now. You have an algo, but it needs 4gig of ram to do what you want.  And you have no good alt.plan.B for implementing chunks.  Think twice - code once.  Just calling 'em like i see 'em.

 

Don't feel bad, we all code ourselves into a corner once in a while.  In Caveman 1.0 I spent a week making it zoom from 1st person view all the way out to orbit, only to realize you couldn't see the sun to tell what time it was. Cross a week off my life, and move the code to the junk.cpp file. OK, what's next on the todo list? life goes on.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

If you use chunks of 256 * 256, would it work to add a border of 1 for each iteration the cellular automata algo?

So if the algo uses 4 iterations, you use (256+8)^2 chunks, and then the border of the clipped 256^2 chunk might become seamless to neighbouring chunks.

 

I did not read how the algo works, but i'm pretty sure you can tune it this way. You just need the initial seed generation well defined over the entire area.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this