Infinite world generator

Question

I want to make an infinite 2-D world generator. I thought I would make a chunk class that represents some part of the world. I only don't know where to store the chunks, and how to generate new ones.

I thought I could store chunks in vector and remember their X,Y. For the player, I make 3x3 array (where he stands in the center) with pointers to the chunks to form the vector. When he moves up, for example, I move upper and middle row lower, and load new chunks from the vector. I dont know if this is a good idea, It was the first thing that I thought up.

Anyway, I don't have any idea how to generate chunks, so they match each other (no desert near water, aso). Even generating constant dimension map is quite hard for me (I really need infinite world).

Some time ago I generated constant dimension world using flood method, so I filled whole map with grass at the beginning, and then made random spots of water, trees and other ones, although I dont think that is usable in infinite world case.

Answer 1

This probably isn't the right way to do this, but may give you some ideas. what you could do is store a 3x3 2D array of chunks or even a 5x5 array of chunks into memory. Updating the these chunks and which chunks are loaded depending on the player's position. The rest of the world can be stored within a file, which is read from and written to. When a player moves within 2-3 chunks of a un-initiated chunk, or empty chunk, generate that chunk using whatever method you want.

The tricky part of this is if you have rivers or bodies of water, forests, or any other type of landscape that spans across multiple chunks, you'll have to have a separate algorithm to handle that when generating new chunks. Will probably need to measure the intersection between two lines each time you generate. The line created by the intersection of land and water, or plains and forests, and the line that represents the edge of the chunk. Once you have that point, you can probably figure out which side of that point on the chunk needs land/water, and randomly generate it from there.

This is what I see happening in Minecraft anyways.

Answer 2

These problems have been addressed in implementations of Conway's Life.

One way to achieve an unbounded world and only deal with the portions that are different from each other is described in discussions of the hashlife algorithm and data structures. It also deals with high performance within a chunk and good performance across chunks. Chunks that are the same are represented by one description that many chunks can point to.

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478

http://en.wikipedia.org/wiki/Hashlife

http://golly.sourceforge.net/

http://tomas.rokicki.com/hlife/

http://www-users.cs.york.ac.uk/~jowen/hashlife.html