How can I store information about what cells are connected to others in a 2D array?

Question

I have a 10x11 array in my game. What is the best structure and way to store the connections between the elements of the array?

Some info about the connections:

• they are simple (2 elements are connected or not)
• an element can be connected with its 8 neighbours
• when I move from one position to another I need to add that connection
• when I'm in a position I need to check that element's connections

For example: "the player" is at [6,1]

1. I need to check for all 8 directions if there is a connection there or not(this function returns a byte or int[8], doesn't matter)
2. If the player wants to move to [6,2] I dont allow it
3. If the player wants to move to [6,1] I allow it and store the new connection

Answer 1

bummzack's answer is good if you need to store an arbitrary graph. Since you are storing a graph that is also a 2D grid, there is an even better way.

Associate eight bits with each index; each bit indicates whether a connection is available in one of the eight possible directions. If the connection costs are not uniform, you can instead store eight bytes (or eight ints, or eight floats). This will use significantly less memory than a full adjacency matrix, and scales linearly rather than quadratically with the number of nodes.

Answer 2

Since the amount of nodes is known, an efficient way to store connections would be an adjacency matrix.

It's basically a two-dimensional array of booleans (or ints/floats if you want to store edge-costs) that has a row and a column for each node. So if you want to get/set the edge from node 3 to node 6, you would look up the entry in row 3 and column 6. If the value there is true (or not zero), then there's an edge from 3 to 6.

Since you have 110 nodes, your adjacency matrix will be a 110x110 array.

This way of storing the graph is suitable for a dense graph (eg. you have lots of connections) and it's very fast to get and set edges (connections).

Answer 3

I would create a simple node class, with eight node properties, one for each direction. (N, NE, S, etc.) Any connection that does not exist has a null node element in that direction's property. Store these in your array, and use them like sort of like a linked list. It's simple and understandable. Each node could have a value property, which points to what you had originally stored in the array, or you could simply add the eight navigation properties to your existing data.