1 registered members (blaurock),
750
guests, and 3
spiders. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Infinite Terrain
#415446
01/18/13 18:25
01/18/13 18:25
|
Joined: Dec 2009
Posts: 256 USA , NY
msmith2468
OP
Member
|
OP
Member
Joined: Dec 2009
Posts: 256
USA , NY
|
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
|
|
|
Re: Infinite Terrain
[Re: msmith2468]
#415449
01/18/13 18:45
01/18/13 18:45
|
Joined: Mar 2011
Posts: 3,150 Budapest
sivan
Expert
|
Expert
Joined: Mar 2011
Posts: 3,150
Budapest
|
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.
Last edited by sivan; 01/18/13 18:45. Reason: NINJA
|
|
|
Re: Infinite Terrain
[Re: sivan]
#415452
01/18/13 19:20
01/18/13 19:20
|
Joined: Dec 2009
Posts: 256 USA , NY
msmith2468
OP
Member
|
OP
Member
Joined: Dec 2009
Posts: 256
USA , NY
|
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!!
Last edited by msmith2468; 01/21/13 02:45.
|
|
|
Re: Infinite Terrain
[Re: Superku]
#415535
01/19/13 22:02
01/19/13 22:02
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
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):
#define P1 1149851
#define P2 1860498
#define P3 87403803
#define P4 1568397607
#define P5 3010349
unsigned int getChunkHash(int x, int y)
{
unsigned int h = (x * y) + P5;
h ^= x < 0 ? x * P1 : x * P2;
h ^= y < 0 ? y * P3 : y * P4;
return h;
}
Last edited by JustSid; 01/19/13 22:09.
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Infinite Terrain
[Re: msmith2468]
#415544
01/20/13 01:51
01/20/13 01:51
|
Joined: Oct 2004
Posts: 900 Lgh
rojart
User
|
User
Joined: Oct 2004
Posts: 900
Lgh
|
I am working on creating an infinite terrain generation system. ... 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 My suggestion is to check infinite_terrain.c example from sample folder.
|
|
|
|