2

THE GOAL
I'm building a world generator that should be able to dynamically add "voxels" to some sort of list as the camera nears the edge of what already exists. Each voxel should be as efficiently accessible as possible since a few hundred voxels from a list of thousands will need to be accessed every frame.

APPROACHES I'VE CONSIDERED
1) My first thought was a multidimensional array of voxels, it's indices being the x and y coordinates of the voxel: Voxels[,] voxels = new Voxel[128,128];

Pros: This should be very fast to pull from assuming I know the coordinates of my voxel: Voxel myVoxel = voxels[x, y];

Cons: I either have to cap the world size, or I have to completely recreate the array every time I want to generate new terrain...

2) To fix this I figured I could just store the x & y values in a string, and use them as keys in a dictionary. Dictionary<string, Voxel> voxels = new Dictionary<string, Voxel>(); Voxel myVoxel = voxels[x + "," + y];
Then adding to the list would be as simple as calling a .Add(); method.

QUESTIONS
1) How does the efficiency of pulling from an array differ from a dictionary. In my head, an array would be multitudes faster since I assume Dictionaries must iterate through every key to check equality (excuse my ignorance if I'm wrong)

2) If an array truly is that much faster to pull from, would destroying and recreating an array of upwards of hundreds of thousands of items multiple times a second (dependent on chunk size) be worth it?

Mind you the target platform is mobile phones, and not every voxel generated will be stored in ram, so the list will never become dangerously large. Testing still needs to be done to determine specific sizes, but the concept is there...

Thanks in advance

Ian Gungee
  • 33
  • 4
  • Sounds like you want a Dynamic Defaultable Dictionary. Combine this: https://stackoverflow.com/questions/2601477/dictionary-returning-a-default-value-if-the-key-does-not-exist With a dictionary that takes an location (think Tuple or even Point) as the key and the value would be your Voxel object. Dictionary lookup is achieved using the GetHashCode() method to quicken the lookup, so it doesn't have to look through each index typically. – kw1jybo Mar 12 '19 at 18:06
  • Dictionaries are usually some form of hash table ( https://en.m.wikipedia.org/wiki/Hash_table ). Hash tables don’t need to search through every entry, unless the hash function is incredibly bad. If you did go with a Dictionary as you described, my guess would be that constructing the strings would make things slower than they need to be. So a dictionary that uses a Tuple or point as @kw1jybo suggests sounds better than that. As for whether the array or dictionary is faster, you could make a basic version using each data structure, and measure which is faster yourself! – Ryan1729 Mar 13 '19 at 05:39

1 Answers1

0

For your questions,

1) If you know the index of the element in the array, an array is fastest (O(1) time). For example, if you're using world positions, you could use the floor of your world position coordinates for each voxel as their indices in the 3D array. Basically, when you generate your world from the 3D array, use the index as the world position and then you'll be able to find their indices in constant time with Math.floor(worldPosition) in your 3D array - this is the fastest.

Dictionaries are faster than arrays when you're searching through an unsorted data structure without knowing the index. See here for a picture (Dictionary lookups for an unsorted list are O(1), and array lookups are O(n)).

2) You will probably need to use multi-threading for it to run well. For example, you could use a different thread to generate data for each quarter of the 3D array, and then join the threads back with the main thread to generate the objects. You shouldn't run into problems with this approach as long as you generate the objects after you've joined the threads back up with the main thread and only use the other threads to generate the 3D array (if you're using Unity, then you can't use any Unity library functions in the other threads).

Also, I'd highly recommend checking out Sebastian Lague's videos on terrain generation for other best practices if you're using Unity https://www.youtube.com/watch?v=wbpMiKiSKm8&list=PLFt_AvWsXl0eBW2EiBtl_sxmDtSgZBxB3

Nicholas Bucher
  • 440
  • 2
  • 7