5
\$\begingroup\$

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
\$\endgroup\$

3 Answers 3

8
\$\begingroup\$

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.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ +1. That is indeed even better and could be implemented very efficiently.. basically just with an array of type byte \$\endgroup\$
    – bummzack
    Commented Aug 13, 2011 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
    Commented Aug 13, 2011 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
    Commented Aug 13, 2011 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
    Commented Aug 13, 2011 at 21:59
  • \$\begingroup\$ @e-MEE sol.gfxile.net/boolean.html That might be of use to you :) \$\endgroup\$
    – Ray Dey
    Commented Aug 13, 2011 at 23:44
3
\$\begingroup\$

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

\$\endgroup\$
7
  • \$\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
    Commented Aug 13, 2011 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
    Commented Aug 13, 2011 at 19:14
  • \$\begingroup\$ @e-MEE - I'm not sure I understand your comment... \$\endgroup\$
    – dlras2
    Commented Aug 13, 2011 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
    Commented Aug 13, 2011 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
    Commented Aug 13, 2011 at 19:54
-1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\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
    Commented Aug 13, 2011 at 19:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .