What data structures can efficiently store 2-d "grid" data?

Question

I am trying to write an application that performs operations on a grid of numbers, where each time a function runs the value of each cell is changed, and the value of each cell is dependent on its neighbours. The value of each cell would be a simple integer.

What would be the best way of storing my data here? I've considered both a flat list/array structure, but that seems ineffective as I have to repeatedly do calculations to work out which cell is 'above' the current cell (when there is an arbitrary grid size) and nested lists, which doesn't seem to be a very good way of representing the data.

I can't help but feel there must be a better way of representing this data in memory for this sort of purpose. Any ideas?

(note, I don't think this is really a subjective question - but stack overflow seems to think it is.. I'm kinda hoping there's an accepted way this sort of data is stored)

Answer 1

A dynamically allocated array of arrays makes it trivial to point to the cell above the current cell, and supports arbitrary grid sizes as well.

Answer 2

If lookup time is important to you, then a 2-dimensional array might be your best choice since looking up a cell's neighbours is a constant time operation given the (x,y) coordinates of the cell.

Answer 3

Here are a few approaches. I'll (try to) illustrate these examples with a representation of a 3x3 grid.

The flat array

+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+

a[row*width + column]

To access elements on the left or right, subtract or add 1 (take care at the row boundaries). To access elements above or below, subtract or add the row size (in this case 3).

The two dimensional array (for languages such as C or FORTRAN that support this)

+-----+-----+-----+
| 0,0 | 0,1 | 0,2 |
+-----+-----+-----+
| 1,0 | 1,1 | 1,2 |
+-----+-----+-----+
| 2,0 | 2,1 | 2,2 |
+-----+-----+-----+

a[row,column]
a[row][column]

Accessing adjacent elements is just incrementing or decrementing either the row or column number. The compiler is still doing exactly the same arithmetic as in the flat array.

The array of arrays (eg. Java)

+---+   +---+---+---+
| 0 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 1 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 2 |-->| 0 | 1 | 2 |
+---+   +---+---+---+

a[row][column]

In this method, a list of "row pointers" (represented on the left) each is a new, independent array. Like the 2-d array, adjacent elements are accessed by adjusting the appropriate index.

Fully linked cells (2-d doubly linked list)

+---+   +---+   +---+
| 0 |-->| 1 |-->| 2 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 3 |-->| 4 |-->| 5 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 6 |-->| 7 |-->| 8 |
|   |<--|   |<--|   |
+---+   +---+   +---+

This method has each cell containing up to four pointers to its adjacent elements. Access to adjacent elements is through the appropriate pointer. You will need to still keep a structure of pointers to elements (probably using one of the above methods) to avoid having to step through each linked list sequentially. This method is a bit unwieldy, however it does have an important application in Knuth's Dancing Links algorithm, where the links are modified during execution of the algorithm to skip over "blank" space in the grid.

Answer 4

Further to my comment, you may find the Hashlife algorithm interesting.

Essentially (if I understand it correctly), you store your data in a quad-tree with a hash table pointing to nodes of the tree. The idea here is that the same pattern may occur more than once in your grid, and each copy will hash to the same value, thus you only have to compute it once.

This is true for Life, which is a grid of mostly-false booleans. Whether it's true for your problem, I don't know.

Answer 5

You should abstract from how you store your data. If you need to do relative operations inside array, Slice is the common patterd to do it. You could have something like this:

public interface IArray2D<T>
{
    T this[int x, int y] { get; }
}

public class Array2D<T> : IArray2D<T>
{
    readonly T[] _values;
    public readonly int Width;
    public readonly int Height;

    public Array2D(int width, int height)
    {
        Width = width;
        Height = height;
        _values = new T[width * height];
    }

    public T this[int x, int y]
    {
        get
        {
            Debug.Assert(x >= 0);
            Debug.Assert(x < Width);
            Debug.Assert(y >= 0);
            Debug.Assert(y < Height);

            return _values[y * Width + x];
        }
    }

    public Slice<T> Slice(int x0, int y0)
    {
        return new Slice<T>(this, x0, y0);
    }
}

public class Slice<T> : IArray2D<T>
{
    readonly IArray2D<T> _underlying;
    readonly int _x0;
    readonly int _y0;

    public Slice(IArray2D<T> underlying, int x0, int y0)
    {
        _underlying = underlying;
        _x0 = x0;
        _y0 = y0;
    }

    public T this[int x, int y]
    {
        get { return _underlying[_x0 + x, _y0 + y]; }
    }
}