Efficiency of int[,] Arrays Versus Dictionary<> for Constant Updates

Question

I'm creating a playspace in Unity (which is only marginally relevant) in C#, which is ostensibly .NET since it's in Unity. The playspace is two-dimensional and is generated via cellular automata with refining methods which make the shape of the playspace "usable" for my intent.

Currently, data about the base playspace (alive cells or dead, open or closed, pathway or wall) is stored as a binary value in an int[,] array. Eventually, additional data will be stored in the array as well, or potentially in a secondary collection mapped back to that int[,] array.

The additional data will include information about things such as: has a player visited this cell, can the player see this cell currently (LoS), is there an enemy or object/item in this cell.

The LoS, hasVisited, and enemy data will be dynamic, obviously, as a player navigates and as enemies move along their paths.

I would like to design and develop this with performance in mind from the beginning as a misstep early on could cause performance bottlenecks later that might require significant refactoring - wasting precious development time as I near the end of the project.

My question is this:

Does updating an array or multiple arrays to track data become resource-expensive in a linear or exponential manner? In other words, if mapA is [80,80] and mapB is [160,160], is mapB going to consume roughly 4x the resources to maintain, or some greater or lesser amount? Are there benefits to using something like a Dictionary or custom collection if the size grows beyond some value of int[,]?

My initial thought was to use something like Dictionary<int[,], Dictionary<string, string>>. I use dictionaries pretty extensively in a utility I maintain for work, but performance is something I don't consider for that since it's internal and very use-specific, so I'm not incredibly familiar with the performance of Dictionary<> in general. The benefit to the Dictionary over multiple arrays of the same grid with different data is that I can have keys that make sense rather than just having additional values that would need to be tracked. I suspect, however, that the array might simply be faster, while less readable in the long run.

Thanks!

Answer 1

It might depend upon the size of the play space and how sparse it is but I would consider using the dictionary or some other managed structure.

If you have a 1000x1000 play space and you use an array it is going to generate 1,000,000 array-cells even if you only "visit" 10% of them. The dictionary method will use an internal array but it will only grow if it needs to and will start out fairly small. Say 10x10 (not sure, would have to check).

I am assuming that the percentage of visited space may be substantially less than 100%. The dictionary will keep the memory footprint smaller until it needs to be bigger and the overhead of the dictionary is negligible when it gets big.

Answer 2

UPDATE : As people pointed out in the comments, int[,] seems to be fairly different in C# than C++ int[][] as I assumed, I let the answer as reference. So as you should always prefer readability when performances aren't impaired, use int[,] instead of what I propose below.

I would also add that it is probably more efficient to even go down to a simple int[] to represent a bidimensional area. You can do that easily this way :

int[] myArray = new int[width * height];

int x, y; // suppose you want to reach the cell at (x, y) coordinates
int cell = myArray[x + y * width];

for(int i=0 ; i<myArray.Length ; ++i) // suppose you want to iterate through the array
{
    int x = i % width;
    int y = i / width; // be sure that width is an int here, we want the auto-flooring

    int cell = myArray[x + y * width] // like above ;)

    int cell = myArray[i] // or of course for simplicity
}

As I write this I'm not quite sure [] is more efficient than [,] in C#, but I know it is in C++.

Complete tutorial on the matter : Using Single Dimensional Array to Represent Two Dimensional Data

Answer 3

According to this answer, a Dictionary is internally a struct array. Therefore, you're adding an additional layer over simply storing them in a multidimensional array on your own. If you're looking for micro-optimization, then you'll never be able to beat the array by piling more on top of it.

Also, the int[,] will at the very least help readability since it is an accurate representation of how the data is visually displayed. So first, make sure you need to optimize before you do. Favor readability first over premature optimization.

I would stick with the int[,] for what you're doing. It will have better performance, and readability.