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?

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 :)

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. :)

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.