My game works on a hex grid that uses a 3-dimensional grid system. Right now I am just keeping a list of occupied hexes and each time something needs to move it checks every adjacent hex against every occupied hex to see if it is occupied. So instead of checking once, it checks once for every unit and building on the board (Hope that makes sense). I want to fix this but I’m unsure of how.
I could use a 2-dimensional array to keep track. The third dimension in my grid system is unnecessary, every space adds up to 0 so (5,-2,-3) would be the same as (5,-2) The reason I didn’t use this from the beginning is since my board is hexagonal instead of a rectangle (or diamond as it would be here) the array would have a bunch of extra spaces I don’t need to keep track of and I don’t know enough about arrays to know how much that would effect it. Is that even a legitimate concern or is there some sort of array alternative (in C#) that would be better suited for what I am trying to do?
So you have two choices really - the array you mention and a Dictionary. In the dictionary approach you select a key which is (at its best) a mathematical formula that yields a unique int for every combination of board position. The benefit of this approach is that you only store data when a cell is occupied, the downside is that you either need to check that the dictionary has a particular key or subclass it so you have a version that returns empty when the key is not found. Dictionary lookup is O(1) which is in the same class as an array lookup but it will be a bit slower.
The array will waste space, the question is do you care?
you care if the board is big
cells are sparsely populated
For memory sake you would probably use a 1d array and index into it using exactly the same formula as for the dictionary. Then your overhead will be to do with the number of unpopulated cells. Dictionaries will carry at the very least a 4 byte (size of an int) overhead for every cell compared to the array. So work out that unpopulated amount and figure it from there - it really depends on the size of the thing you are storing in the array or dictionary. If its a 128 byte sized struct then you will need a lot less sparsity for a dictionary to make sense compare to a 4 byte int or bool. if you are storing a class or other reference in there then the wasted space will be 4 bytes per empty entry and a population percentage approaching 50% would dictate an array.
If the board is small then just use the array - the wasted space won’t count for much (again based on the size of the thing you are storing).