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

example of grid

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

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.

  • 2
    \$\begingroup\$ I don't see how it's low-level; yes I said use bits, but that's not the material difference between my answer and yours. It's a data structure that stores what you want. Node pointers are not what you want; the 2D grid already establishes that relationship. Connectivity information is what you want. If I wanted to do it less efficiently, I would recommend storing eight bools per node, still not what you suggested. "Typical OO bullshit" means you ran to build a class without thinking about the data you really want. \$\endgroup\$ – user744 Aug 13 '11 at 19:53
  • 1
    \$\begingroup\$ +1. That is indeed even better and could be implemented very efficiently.. basically just with an array of type byte \$\endgroup\$ – bummzack Aug 13 '11 at 20:23
  • \$\begingroup\$ +1 I didn't even think of this but it's just so obvious and simple. Nice and elegant, well played sir. \$\endgroup\$ – Ray Dey Aug 13 '11 at 21:11
  • \$\begingroup\$ seems simple, but I will certainly have problems with storing the new connection after a step, but I will figure that out. \$\endgroup\$ – e-MEE Aug 13 '11 at 21:35
  • 1
    \$\begingroup\$ @e-MEE why? Just have constants for each direction (eg. TOP_LEFT = 1; TOP = 2; TOP_RIGHT = 4 etc.) and then use a binary "OR" operation with the current value to add this connection. \$\endgroup\$ – bummzack Aug 13 '11 at 21:59

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).

  • \$\begingroup\$ Since the elements only have a maximum of 8 connections, I don't think that this is the most efficient way to store the graph. \$\endgroup\$ – dlras2 Aug 13 '11 at 19:12
  • \$\begingroup\$ well, the thing is that I need the edge from [3,4] to [3,5] not only from 3 to 6 \$\endgroup\$ – e-MEE Aug 13 '11 at 19:14
  • \$\begingroup\$ @e-MEE - I'm not sure I understand your comment... \$\endgroup\$ – dlras2 Aug 13 '11 at 19:17
  • \$\begingroup\$ @Dan: If we are grading on efficiency, one needs to reach about 250 nodes before this solution uses more memory than yours, assuming the nodes are aligned on 32 byte boundaries. (Which will definitely be true of 64 bit systems and probably true of 32 bit ones.) And this solution is far more cache-friendly and lookup-friendly. \$\endgroup\$ – user744 Aug 13 '11 at 19:36
  • \$\begingroup\$ @Joe - I don't mean efficiency in resources, necessarily. bummzack even stated that it's most suitable for dense graphs, which the OP's graph doesn't sound like. This requires assigning an integer index to each node, which may not be needed, and just adds that complexity. \$\endgroup\$ – dlras2 Aug 13 '11 at 19:54

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.

  • \$\begingroup\$ the idea is good, but I wanted to make it without many if and switch.I will implement it tomorrow maybe, but your last sentence isn't very clear for me. (sorry english is not my first language) \$\endgroup\$ – e-MEE Aug 13 '11 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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