# Is it more efficient to store my tile grid as a dictionary or an array?

I've just started making a video game in AS3, and I'm trying to keep the graphics, sound, and actual game state in three completely different spots and sets of classes. That being the case, the graphics module will have to repeatedly parse the state module. The game is divided into levels, and each level is divided up into square spaces (like a board game); thus the graphics module will have to repeatedly parse out a certain cross-section of spaces of the current level.

The player will always show up in the middle of the spaces' overall graphic (the "Grid"), and there will be 4 spaces in every direction from the player's positioin that will be displayed, along with any object each space may contain (such as the player, a monster, etc.).

So right now I'm trying to decide how to store the spaces in each level (all of the level's spaces themselves, not the graphics). The first thing that came to mind was a 2D Array. Then I started to use a 2D Vector, then came back to using an Array, like at first; and now I'm wondering whether to use an Array or a Dictionary.

The problem:

Let's say a level looks like this:

``````xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxPxxxxxxx
``````

x's are blank spaces, P is the space that the player. As the Grid parses this information, if it's a 2D Array, then it can use the length property of the main Array and the length property of each sub-array to set up its for loops reasonably well. Furthermore if a space is outside the bounds of the 2D array, then rather than wasting memory trying to form more objects in the code or something, the Grid can just assume the space is blank:

``````var arr:Array;
var space:Space;

for (var i:int = level.playerX - 4; i <= level.playerX; i++)
{
arr = level.spaces[i];
if (arr)
{
for (var j:int = level.playerY - 4; j <= level.playerY; j++)
{
space = arr[j];
if (space)
{
// find every object inside space and animate accordingly
}
else
{
// assume the space is blank
}
}
}
else
{
// assume the whole column of spaces is blank
}
}
``````

Within the player's radius, the Grid must animate any non-existent spaces as blanks. Therefore the graphical output is as follows:

``````xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxPxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
``````

But now if we have a level that looks more like this:

``````xxxxxxxxxxxxx
xxxxxxxxx
Pxxxx
xxxxx
``````

then using an Array leaves two basic options:

1. Use null elements within the sub-arrays to get the Grid to animate non-existent spaces that come before the real ones in the sub-array (the sub-array's length can be used for non-existent spaces that come after the real ones).

2. Make that simple for-looping inside the Grid a whole lot more complex to compensate for rows and columns of spaces starting at variable locations along each axis (and not simply ending at variable locations).

I don't want to use option 2. I was just going to use option 1 with Arrays, but now the possibility of using Dictionaries instead has come to mind. At least with Dictionaries, I wouldn't have to just waste memory every time I wanted, let's say, for the first space in a row to begin at postion 5.

Sorry, I know this was lengthy, but I hope I've illustrated the problem. Which is better - an Array, or a Dictionary? If a Dictionary is better, should it use sub-Dictionaries or sub-Arrays to establish a 2-dimensional effect? Thanks!

-
This is one of those questions that come down to "Are you having performance issues?". Premature optimization. Then someone will suggest to do some profiling. Personally I'd just go with a 1D or 2D array. Tiles usually just represent a type. For invisibile tiles I'd just set that to 0. What you need to do is make sure you have a good interface structure so that you can later on rewrite the context in case you decide to handle it differently without touching your complete system. – Sidar Aug 8 '13 at 2:25
"Array" is almost always the answer for any question about data structures and performance. Seriously. – Sean Middleditch Jan 3 '14 at 18:50

``````var tile = tiles[y * width + x];
This will allow you to access the tile at position (`x`, `y`) but still retain the benefit of having all your data in a single contiguous array, rather than an array-of-arrays approach, which has poorer locality-of-reference (although if you have access to actual contiguous 2D rectangular arrays in your language, you could those too). Keep your levels rectangular tile grids, even if some tiles are not used (the "null" tiles in your previous example can be represented by a sentinel value, such as `0` if all you are storing are tile IDs, or `null` if you are storing actual `Tile` references).
The rationale here is that most of the time you're going to be looping over regions of the tile grid to check or do something with a bunch of tiles. It benefits you to be able to access and iterate those regions quickly, and an array provides `O(1)` random access and quick iteration. Dictionaries can also provide `O(1)` access for hash-based implementations with a good hash selection, but sometimes that becomes amortized and even when it isn't, the constant factor is usually higher. Iteration over dictionary keys is usually not as efficient (or even possible in the fashion you'd need), so they make a sub-par choice here.