How would you manage chunks in an infinitely expandable voxel based world?

[dangerdoc]

Hello,
I am making a voxel based 3-D game that can be infinitely generated in all directions using procedural terrain generation. I am having a hard time managing the world in a way that it has these requirements:

*It can be updated each frame quickly
*It can remove unused chunks
*It can find out whether or not a chunk is rendered and add it if it isn't


Any ideas?
The ideas I have tried aren't very sound, and they will not work with several features. I have a chunk class that stores the block data, and a ChunkManager class that loads and unloads the chunks using arraylist. How would you make them index-able so you can find whether chunk (x, y, z) is loaded? If I went through the arraylist each frame and checked the coordinates of the chunk to figure out which need to be loaded and removed, it would probably run slowly.

I am stumped, and I can't find any code that shows ways to do this in an infinitely expandable world (Yes, its based on exploring). Any help will be appreciated!

dangerdoc

[CodeBunny]

In all honesty, the StackExchange sites (StackOverflow, GameDev, etc.) are a better place for this. This is a very heavy-duty question.

[dangerdoc]

Ok, Thanks CodeBunny! Ill go ask there (If it doesn't ask for too much personal information lol). Also, the question is still open if someone has an answer!  

Edit: Done!! 

http://stackoverflow.com/questions/11376201/chunk-management-in-a-voxel-based-game

[Fool Running]

I would create some kind of hash code based on the x,y,z location so that you can just look it up in a HashTable. Otherwise (since the world in infinite and the values can get too large to create unique hashes), you could create some kind of tree structure (where the root is the whole world, then under that you have the world divided into smaller chunks, then smaller chunks, etc) all sorted in such a way that a search would be fast.

[CodeBunny]

Would it be possible to do a variant of that? Use the tree structure to organize saved chunk files, but while in game, use a 6-axial linked structure? Effectively, the player is "in" a given chunk, and that chunk is linked to all adjacent ones. As new chunks need to be loaded, the tree structure is called upon to determine the correct ones.

You'd need to do fewer lookups, and it you could use it to get rid of the "far lands" problem in chunk-based games.

[dangerdoc]

Okay, I have come up with a theory on how it might work.

Every frame, the main class would call chunkmanager, which tells each chunk to render itself via mesh object. Tells which chunks have been edited (ie, build/destroy), and adds them to the loadmesh queue. Loads one chunk from each queue. If it has been X frames, ask each chunk if it is outside of the boundaries for a chunk to be rendered. If a chunk is too far away from the player, add it to the remove queue. Check the players location, transfer that to chunk coordinates, and check if the chunks around the player are loaded. If they are not loaded, add them to the load queue.

Is that feasible? Or would you spread out the update more instead of doing it in one frame? Thanks! I also will be storing the chunks in bigger chunks.

[basil]

you can get a working thing with that idea. a http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html would be enough to start.

but loki's answer on http://stackoverflow.com/questions/11376201/chunk-management-in-a-voxel-based-game is actualy pretty right.

[dangerdoc]

Thanks basil. That library looks good for this.