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
