Infinite Terrain

I am working on creating an infinite terrain generation system. The system uses tiles that work like a treadmill, placing tiles behind the player, in front of the player. Everything works great, generating new terrain is smooth.

However my current system does not have a way to remember terrain that has already been generated. For example: if the player moves forward for a while and turns around and goes back to a place he has already been, then the terrain will be regenerated and look entirely different.

I had some ideas for storing the terrain data that the player has already been to.

Idea 1: A linked list of a data structure that stores the tiles texture, height, and 4 neighbors.
This method works great in my mind because the tiles can look up the next tile to be placed in front of them and transfer the data to the new tile. This would be quick and infinite because I can always generate new tiles and link them to the system.
Further understanding of this idea revealed a flaw. When the player travels in a large circle and renters the place he started the linked list method would not recognize that this was a place that has already been discovered and would proceed to recreate it. I could fix this by traversing the linked list to see if a tile has been seen before or not, but this would be a very time consuming process and would quickly slow down the game.

Idea 2: An array of data structures that store the tiles texture and height.
This method would allow for quick access to any point on the map. This would avoid the problem described in the last scenario because I could simply check the new position to see if the tile has been created before.
A new problem is that it is not infinite. An array has a defined size. I could make the array adjustable in size if its size limit is exceeded, but that would require creating a new array and copying the data from the old array to the new one. This could become very time consuming on very large maps.

If anyone has any ideas, thoughts, or suggestions to a solution for storing an infinite set of data as described, I would appreciate it.

Thank You for your time.
Michael Smith

You can use a fixed seed value for your random function which means that you would not have to store anything at all. Consider the following example (that will probably not work this way but you should get the idea):

i = (int)(player.x/1024);
j = (int)(player.y/1024);
random_seed(i+j); //or any other formula
generate terrain using this seed value

someone earlier in this forum somebody had a great idea for a similar case, to use certain random seed values for randomly generated terrains, thus it is unnecessary to store height data, only the seed value is enough, because the random value always the same for the same random seed value.

Superku you just (blew my mind)!!

That makes so much sense to me!! It's so simple yet so powerful and solves many issues. I will get to work on it.

Thinking ahead a bit... how would changes or alterations of the terrain be stored??

Thank You!!

are you using a voxel system?

What kind of terrain are you using and what alterations are to be stored?

A pretty neat way to store heightmaps (or audio waves) in a lossless but compressed manner is to take two points and only store the offset between them in the smallest possible data type, then going to the next point and store its offset and so on. If you know that most values will be the same, you can also store the range in which the offsets are going to be zero.

Obviously this is pretty simple (but pretty much the same way most lossless audio codecs work, on a very high level), and you can do some more tricks when you work with a spacial grid, but that should get you started.

Edit: To store them efficiently, you can create a hash out of the tiles position and store it either in a big hashtable (probably not a good idea because rehashing on disk is quite expensive), or use the filesystem itself as hashtable and the name of the filestream as hash. The filesystem is quite good at fetching named resources, so that's not going to be a huge problem. Also, because I'm a lovely person, here is a hashing function that has no collisions for +-10k tiles in every direction (I bruteforced the correct prime numbers myself and also tested that there are no collisions):

JustSid's idea to save only the changed values and its offsets is a great idea and common practice in numerical mathematics to save and work with sparse matrices, see here if you want to know more about it:
http://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_.28CSR_or_CRS.29
The German version has some probably helpful images, too:
http://de.wikipedia.org/wiki/Compressed_Row_Storage

My suggestion is to check infinite_terrain.c example from sample folder.

i think the infinite_terrain demo isn't the thing he wants
he wants real infinite terrain, not just the fake one

I am not using voxel's I am using height map. I am using a 2D grid with values that represent height. Then I am using a simple square tile with 4 vertices that are altered to the values in the grid and properly connected to the tiles around it.

Unlike my previous attempt at a terrain generation system that used square tiles with 100 vertices that required complex algorithms for adjusting them properly. My new method breaks it down to a simple form that can more easily be handled.

As far a manipulating the terrain was just a thought. I currently have no defined use for the terrain generation so no requirements of its capabilities need to be met. However I would like to create the system as flexible as possible.

Thank's everyone for all of the suggestions. They are great and I plan to look into each of them.