Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm creating a grid-based iOS game using Cocos2d. Currently the grid is stored in an NSMutableArray that contains other NSMutableArrays (the latter are rows in the grid). This works ok and performance so far is pretty good. However the syntax feels bulky and the indexing isn't very elegant (using CGPoints, would prefer integer indices). I'm looking for an alternative.

What are some alternatives data structures for 2D arrays in this situation?

In my game it's very common to add and remove rows from the bottom of the grid. So the grid might start off 10x10, grow to 17x10, shrink to 8x10 and then finally end with 2x10. Note the column count is constant.

I've consider using a vector<vector<Object*>>. Also I'm vaguely aware of some type of "fast array" or similar offered by Cocos2d. I'd just like to learn about best practices from other developers!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

First of all, given the grid sizes you've talked about you're not likely to run into performance issues with your current implementation, so if you're asking this because you have a performance problem this may not be it (and you should profile). That said:

The "array of arrays" approach might seem like a reasonable representation of a grid (and to some extent, it is), but it has some drawbacks. As you've discovered, using the interface can be awkward (especially if you're using something the like Cocoa array classes, since their indexing APIs are cumbersome already).

They're also not very cache-coherent, since the entire grid is not guaranteed to be contiguous in memory, and they allow the grid to be "jagged" (i.e., not really a grid) since you could adjust the size of an individual row only, should you so choose (of course in some cases this is a benefit, but not in this one).

So, why not just use a single array? A one-dimensional array (vector, NSMutableArray, bare memory, whatever) can represent a n-dimensional grid easily and requires only a little bit of indexing math, and it provides you the significant benefit of improved locality-of-reference for the entire grid's elements.

An example using vector (although the principle applies to any other array interface):

unsigned width = /* ... */
unsigned height = /* ... */
std::vector<Object*> grid(width * height);

// Compute the linear index of the item at (row, column) in the grid:
unsigned row = /* ... */
unsigned column = /* ... */
unsigned index = column + (row * width);

// Access the grid:
grid[index] = /* assign some object */

The principle here is to treat each contiguous set of width elements in the array as a single row. That's how you arrive at the indexing math used to compute index.

Another issue you touched on is how your grid resizes. This is an issue regardless of the grid implementation you use. You might try handling it by only increasing the actual storage for the grid; never decrease it. Almost any implementation of a grid is going to involve a copy of the existing grid elements when the grid resizes. Implementations utilizing linked-lists won't (or will minimize them), but then you're back to having cache-coherency issues.

You want to minimize that copying, and at a minimum you only need to resize to increase storage. You can keep, independently, a variable indicating the grid's logical size and only process that many rows, ignoring any extra "deactivated" rows that might exist beyond that when your grid resizes down. This means the resize-downward operation only involves setting a variable to the new, lower number.

This can be extended to apply to cases where the grid resizes in both directions, even though your specific case does not currently seem to require that.

I mentioned cache coherency/locality of reference a few times, and that's because I'm assuming since your game is "grid based" your doing a lot of iteration over all (active) cells in the grid. It's that kind of use-case where coherency of your data can have a surprising impact on performance, although it's still true that at the specific numbers you mentioned it's unlikely to be that big of a deal.

share|improve this answer
    
+1. Thanks for the info! I like the idea of using a single array and storing the rows in blocks/chunks. Also the idea of "down-sizing" the grid by adjusting a boundary instead of adjusting the size is cool! –  SundayMonday Dec 3 '12 at 2:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.