I've written a voxel system in both GDScript and C# in Godot, but I'm by no means an expert on this, so please take all of this with a grain of salt!
I would say if you are concerned about performance, which makes sense given how much data has to be processed in a voxel chunk, the biggest constraint is probably going to be how you render the Voxel, what optimizations you want to have, and whether your voxels need to access adjacent voxels.
For example, if you want to optimize for the GPU and reduce overdraw (drawing voxels you cannot see), then you will likely want to dynamically construct each face of the voxel that could be visible to the player, and then skip adding the mesh data for all the many voxels that may be completely obscured by voxels surrounding all faces. However, this optimization requires going through every voxel in the chunk, checking all adjacent faces, and then adding the relevant mesh data. This requires at least a single full loop through all the data and 6 adjacent voxel checks, so very processor intensive.
So, with that in mind, here's what I have found:
This is probably the fastest solution for most situations where you want to optimize for the GPU, perform voxel lighting calculations in code, or otherwise need to go through the data in a loop when something changes. Arrays are good for this because they are fast, fixed size, and there are some optimizations you can make while iterating over them to speed things up. However, they can be unwieldy to program with and, as you have mentioned, may require looping through the entire array even when the overwhelming majority is empty, since there is no way to know exactly what data you have without trying to access it.
I would recommend using an array if you are going to iterate through every voxel in the chunk routinely, as then you will see the most benefit from it. In my projects, I've used Arrays for voxel chunks because I have to iterate through the entire voxel chunk to generate the mesh.
Most voxel projects use arrays, but that doesn't mean it's the best solution for all cases! Depending on how you display and process voxels, using an alternative data structure may be MUCH faster, as you can skip a bunch of otherwise unnecessary calculations. If you have a way to just update small sections of a chunk, then an array might actual be slower since you would (potentially) have to iterate over the entire thing unnecessarily.
The kicker here is that many voxel projects have visuals and game play mechanics that rely on 'seeing' other nearby voxels, which almost always means looping through the entire chunk, so using an array is the general route.
Side note:
The absolute fastest solution is to use a three dimensional array that is flattened to a single dimension, if you want to absolute fastest access speed, though to be honest I've always just used multidimensional arrays and took the slight performance hit :smile:
Can't really speak for this one, as I haven't really tried it myself. I think the hard part with a list is going to be trying to determine if the list has a voxel at a certain position without doing a search through the entire list, which could be quite slow. If you fill the list to the maximum size of the chunk to get around the search issue, then you basically have an array and I'm not sure there would be any benefits to using a List. Again though, I haven't tried this at all so I'm really not sure!
This one is a bit of a toss up and I would say greatly depends on whether you need to iterate over the entire array or not, what is the key (voxel position?), and how much data/RAM you want to use.
The real question that would determine it's performance is how fast checking for an element that does not exist is. If the code for trying to determine if a key is an a dictionary is going through the entire dictionary and doing comparisons, then it would be much slower than an Array or List. On the other hand, if the method is really quick, then it could be fairly quick.
Though as you mentioned, iterating is going to be slow here, and that's really the big trade off. If you can minimize the need to iterate through every voxel in the chunk, then it could be decently fast and has the nice bonus of being really easy to work with.
I have tried this before with some success on some of my earliest voxel experiments, but those projects were slow. Whether it was the dictionary or just my code, I am not sure and am somewhat inclined to think it might have been my code rather than the dictionary itself. I do know that I iterated through every voxel in the dictionary, regardless of whether it had a voxel or not (used null for empty space), so I can probably say I wasn't using the data structure in the most optimal way.
My only concern with using Dictionaries is that I haven't really seen it used too much in very large voxel projects, which would make me hesitant to recommend it simply because there is probably a reason it's not used too often. I think it is probably because most voxel games need to iterate over the entire array too often to reap the benefits of using dictionaries, that or the memory footprint is just too great for the platforms the developers target.
Again, I want to stress again that I'm not an expert on this and so I would highly recommend taking everything I wrote with a huge grain of salt! Ideally if you want to have the best idea on the potential performance impacts, you may want to make a super simple voxel chunk system using each solution and doing some benchmarks to get an idea on what the performance impact of each solution may be.
Hopefully what I wrote helps give some potential considerations though! Regardless of which you choose, please keep us updated as I think voxel engines are pretty cool and would love to see how your voxel system develops :smile:
