Quickly Getting chunks from Unorganized list.

Hi,
I have a simple block based game which is made up of chunks, each chunk containing a 16*16*16 3 dimensional array of block ids. I used to make the world up of a 3 dimensional array of chunks but this limited the size of the world, and now i would like to create an infinite terrain and instead of using a 3 dimensional array i have decided to use a list of chunks. With the 3 dimensional array i could simply get blocks based of a Vector3 and simple maths, but now i use a list and chunks are put into it and unloaded from it in random order (the list isn't organised).
How can i get a specific chunk at x position from this list without looping through the whole list which is causing the world to load extremely slow? This is how i'm doing it now:

Code (CSharp):

1. public Chunk GetChunk (Vector3 worldPosition)
2.     {
3.         Vector3 chunkPosition = new Vector3 ((int)Mathf.Floor (worldPosition.x / chunkSize), (int)Mathf.Floor (worldPosition.y / chunkSize), (int)Mathf.Floor (worldPosition.z / chunkSize));
4.         for (int i = 0; i < loadedChunks.Count; i++) {
5.             if (loadedChunks [i].transform.position / chunkSize == chunkPosition) {
6.                 return loadedChunks [i];
7.             }
8.         }
9.         return null;
10.     }

If there is any other way that you would suggest can you please let me know because i am having trouble creating infinite terrain, where as a set size was easy for me to handle.

Thanks for you help and time.

 

You should use Dictionary in this case, it is fast and easy.
Use positions as keys and chunks as values.

Thanks.

 

I have considered using Dictionaries but i have no idea how fast they are compared to getting an instance straight from an array or looping though a list and haven't had the time to experiment with them yet.
Ideally i would like to get a chunk as fast as possible as this is whats holding up everything else. So would you happen to know how fast dictionaries compare to other options?

 

Do this, dictionaries have no lookup time compared to "normal" collections such as lists, due to them being indexed with a key-value format.

EDIT: https://stackoverflow.com/questions/13829665/speed-and-functionality-of-dictionary-vs-list-vs-array


as mentioned in there and as I have all over here, your probably not going to actually see much of a difference unless your doing crazy big operations.

EDIT2: this explains when to choose which https://www.dotnetperls.com/dictionary-list-loop

 

Code (CSharp):

1. public Chunk GetChunk (Vector3 worldPosition)
2.     {
3.         Vector3 chunkPosition = new Vector3 ((int)Mathf.Floor (worldPosition.x / chunkSize), (int)Mathf.Floor (worldPosition.y / chunkSize), (int)Mathf.Floor (worldPosition.z / chunkSize));
4.         if (loadedChunks.ContainsKey (chunkPosition * chunkSize)) {
5.             return loadedChunks [chunkPosition * chunkSize];
6.         }
7.         return null;
8.     }

I've finished implementing dictionaries and its decently a lot faster. Now i just need to implement terrain loading when i move and see if it keeps up without destroying the fps.

And just a quick question is it possible to loop though all values of a dictionary? because i don't seem to be able to get a reference by an index.

Thanks for the info everyone.

 

What you're really looking for is an octree.

Dividing your world into chunks and then using dictionaries in each chunk is halfway to octrees. But if halfway gets you where you need to be performance-wise, might as well stick with it.

 

Keep us updated with your game.

Thanks.

 

Would you guys have any clue why waitforseconds in coroutines isn't really working on low number, for example when i do waitforseconds(0.00001f); it seems to be waiting around 0.05-0.1 seconds instead.

 

The minimum it can wait is the current frametime.

 

Oh that would make sense now that i think about it.
So if the game was running at 60 fps the minimum time would be 1/60 = 0.016 seconds?
Thanks.

 

Does anyone know how i could spiral outwards instead of doing this:

Code (CSharp):

1. for (int x = -radius; x < radius + 1; x++) {
2.             for (int y = -radius; y < radius + 1; y++) {
3.                 for (int z = -radius; z < radius + 1; z++) {
4.                     Vector3 position = new Vector3 (x * chunkSize, y * chunkSize, z * chunkSize);
5.                     if (Vector3.Distance (chunkPosition, chunkPosition + position) <= radius * chunkSize) {
6.                         if (!loadedChunks.ContainsKey (chunkPosition + position)) {
7.                             CreateChunk (chunkPosition + position);
8.                         }
9.                     }
10.                 }
11.             }
12.         }

So that chunks closest to the player are loaded first?

 

As TonyLi mentioned you should really use an octree or at the very least a quadtree for storing your chunks. Its a fast data structure for querying object positions & saves on doing weird workarounds.

 

I don't really know much about octrees to be honest this thread is the first time I've ever heard of them. So i would like to focus on getting the basic functionality of my game working first before getting into other stuff like octrees, unless octrees are completely necessary?

 

There are a few on github for unity. But I would only advise using or making them, if that's your bottleneck, and it's a meaningful bottleneck (technically everything is bottlenecked).

Hows your expertise with Unity Profiler? if you haven't mastered it, this thread is 100% pointless.

 

It's when I'm setting up and loading the chunks which is causing lag.

 

How is that irrelevant to timing? Have to know what precisely is causing it to optimise it surely? and by how many ms.

 

I try to load the chunks in as fast as possible to make sure it reaches the player so that you cant fall through the world, but if i could load the chunks slower it wouldn't create as much lag as the calculations would be spread out. Also I'm currently not doing any culling, so when i get around to implementing that the world should (hopefully) load a lot faster due to having to calculate less chunks.

The profiler shows me That my GenerateChunks coroutine (6.95 - 25ms) is the main problem.

 

I've decided that flood fill will work best for loading chunks closest to player first so I've come up with this:

Code (CSharp):

1. //uses flood fill to load chunks around defined position by a certain radius
2.     //*culling not yet implemented
3.     IEnumerator LoadChunksExperimental (Vector3 worldPosition, int radius)
4.     {
5.         Vector3 chunkPosition = new Vector3 ((int)Mathf.Floor (worldPosition.x / chunkSize), (int)Mathf.Floor (worldPosition.y / chunkSize), (int)Mathf.Floor (worldPosition.z / chunkSize)) * chunkSize;
6.         List<Vector3> ffChunks = new List<Vector3> ();
7.         ffChunks.Add (chunkPosition);
8.  
9.         //flood fill loop
10.         while (true) {
11.  
12.             if (Vector3.Distance (chunkPosition, ffChunks [0]) > radius * chunkSize)
13.                 yield break;
14.  
15.             TestToCreateChunk (ffChunks, Vector3.up);
16.             TestToCreateChunk (ffChunks, Vector3.down);
17.             TestToCreateChunk (ffChunks, Vector3.forward);
18.             TestToCreateChunk (ffChunks, Vector3.right);
19.             TestToCreateChunk (ffChunks, Vector3.back);
20.             TestToCreateChunk (ffChunks, Vector3.left);
21.  
22.             ffChunks.RemoveAt (0);
23.             yield return new WaitForEndOfFrame ();
24.         }
25.  
26.     }
27.  
28.     //tests to create a chunk based off chunk loading method
29.     void TestToCreateChunk (List<Vector3> ffChunks, Vector3 direction)
30.     {
31.         if (!ffChunks.Contains (ffChunks [0] + direction * chunkSize)) {
32.             ffChunks.Add (ffChunks [0] + direction * chunkSize);
33.             if (!loadedChunks.ContainsKey (ffChunks [0] + direction * chunkSize)) {
34.                 CreateChunk (ffChunks [0] + direction * chunkSize);
35.             }
36.         }
37.     }

I still need to implement culling for maximum efficiency though.
Any suggestions of feed back?

 

So an octree divides each area into smaller areas again and again and is recursive, so change your methods to call themselves until the division ratio is where you want it and you get an octree (sort of, still look up an actual implementation to see how to link the branches of the tree as you traverse)

 

I'm quite happy with the way i load chunks, but if the view distance is set high, too many chunks are calculated and it takes a while to load the world, can anyone suggest any culling algorithms or methods to ignore chunks that cant be seen?
Thanks.