I'm programming in C# and I'm pretty certain that it will throw a hissy fit if I try using pointers. Instead If I am storing an array of 26 structs for each graph node on the map then wouldn't that be a waste of memory. How else can I approach it?

No C# expert here, but I just read really quickly regarding reference and value types in C# and it seems to me you would be much better off by using classes, since they are reference types. So your nodes/tiles would be a class. And, you would basically have some number of references to the surrounding neighbours. In this case, you would use much less memory than using structs if I understand things correctly..

Hope that helps.

In the node class I have the maximum amount of neighbours allocated to a node array:


private GraphNode[] neighbours = new GraphNode[26];


public GraphNode[] Neighbours
{
get { return neighbours; }
}


Now if I create two nodes and the second node to the neighbours of the first node:



GraphNode node = new GraphNode(this, Vector3.Zero);
GraphNode node2 = new GraphNode(this, Vector3.One);
node.Neighbours[0] = node2;


then it doesn't appear to reference that node as:


node2 = null;


doesn't make the node.Neighbours[0] = null.

In the node class I have the maximum amount of neighbours allocated to a node array:


private GraphNode[] neighbours = new GraphNode[26];


public GraphNode[] Neighbours
{
get { return neighbours; }
}


Now if I create two nodes and the second node to the neighbours of the first node:



GraphNode node = new GraphNode(this, Vector3.Zero);
GraphNode node2 = new GraphNode(this, Vector3.One);
node.Neighbours[0] = node2;


then it doesn't appear to reference that node as:


node2 = null;


doesn't make the node.Neighbours[0] = null.

I think I understand. And, no it shouldn't. node.Neighbours[0] is a reference and node2 is a reference, but they both point to the same thing which is a GraphNode containing Vector3.One.

Now, node.Neighbours[0] = null just kills the reference, not the actual object. BUT, if you change the information inside the object:

node2.vector.x ++;
And then

print node.Neighbours[0].vector.x;

Then you will see the change.

You may should read this: http://www.albahari.com/valuevsreftypes.aspx

Thank you. I'll report back if I have any problems during implementation, but I have all I need for now

Regarding nodes and edges... think the board game Risk. If I were to ask you which countries were connected, you could tell me despite the varied geometry. Now just replace the countries with dots, and draw one line over each border. You now have a waypoint graph.

BTW, for more on generic graphs of this sort, see "Graph Theory" on Wikipedia and elsewhere.

I understand what you mean by points and connecting lines. This is my approach using that idea:

1) In the case of full 3D movement and diagonals I have checked my map and created a node at equally spaced distances where there is no geometry. [The points]
2) Using the code below I then check each node for neighbours and add them to the neighbours array at the specific index if they exists. [The connect line between points]

The code has been snipped but the idea is the same for all subsequent neighbour checks:


// [Neighbour Index]
// z [TOP]
// / 0, 1, 2, 3, 4, 5, 6, 7, 8
// /
// [0]_____[1]_____[2] [MIDDLE]
// / | /| 9, 10, 11, 12, 13, 14, 15, 16
// / | / |
// [3] | [4] [5] | [BOTTOM]
// y / | / | 17, 18, 19, 20, 21, 22, 23, 24, 25
// | / | / |
// | [6]_____[7]_____[8]___ | [Array Indices]
// | [17] [18]| [19]
// | / | / +Y -Z
// | [20] [21] | [22] | /
// | / | / | /
// | / | / |/
// [23]____[24]____[25] --- x .-------> +X

// Check all neighbours
for (int x = 0; x < depth; ++x)
{
for (int y = 0; y < height; ++y)
{
for (int z = 0; z < width; ++z)
{
int index = x * width * height + y * width + z;
int neighbourIndex;

// Check for neighbouring nodes
if (nodes[index] != null)
{
// Array indices
int xIndex;
int yIndex;
int zIndex;

// [Left, Top, Far]
// XNA: -X, +Y, -Z
// Array: -X, +Y, -Z
xIndex = x - 1;
yIndex = y + 1;
zIndex = z - 1;

// Check array bounds
if (xIndex >= 0 && yIndex < height && zIndex >= 0)
{
neighbourIndex = xIndex * width * height + yIndex * width + zIndex;

// Check if the node exists
if (nodes[neighbourIndex] != null)
{
// Add the neighbour
nodes[index].Neighbours[0] = nodes[neighbourIndex];
}
}


Is this what you mean by a waypoint graph and am I generating it in an efficient manner?

Ok... so let me get this straight. The player can be in an arbitrary point in space and all you want to do is detect which fixed point node is closest to his arbitrary location?

Ok... so let me get this straight. The player can be in an arbitrary point in space and all you want to do is detect which fixed point node is closest to his arbitrary location?

I have used a nearest neighbour algorithm with an octree to do that.

I then wanted to know how I could find the neighbouring nodes from the nearest neighbour, that's when topic went towards storing references to the neighbours in each node and using them. I have now done that using the algorithm shown in my previous post which is linked to your suggestion to graph theory.

Is there anything I have done incorrectly or inefficiently?

Is your geometry dense (i.e. usually most of the 26 possible connections are used) or sparse (i.e. usually only a few connections are used)? In the sparse case, you should be using a list of neighboring node IDs/references instead of storing an array. For the dense case, why not just use a true cubic map with bit flags controlling which connections are available? I.e. use one bit out of 26 possible bits for each connection; if the bit is set, the connection is valid, otherwise there is no link. This can be stored compactly in a single 32-bit integer for maximum efficiency on current hardware.

For the dense case, why not just use a true cubic map with bit flags controlling which connections are available?

I understand bit fields/bit flags but how would they work in this case? Would I have to create a cube map of nodes and include null nodes in that map as the levels will not always be cubic?

My current way is to index the node's neighbours in an order that defines which ones to ignore depending on the movement type (diagonal nodes are odd numbered). This helps speed up A* path finding calculations.



// [Generate All Neighbours]
// • 2D/2.5D - Non diagonal neighbours - [0, 2, 4, 6]
// • 2D/2.5D - Diagonal neighbours - [1, 3, 5, 7]
// • 3D - Non diagonal neighbours - [8, 10]
// • 3D - Diagonal neighbours - [9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

// [Neighbour Index]
// z [TOP]
// / 9, 11, 12, 13, [8], 14, 15, 16, 17
// /
// [9]_____[11]_____[12] [MIDDLE]
// / | /| 7, [0], 1, [2], 3, [4], 5, [6]
// / | / |
// [13] | [8] [14] | [BOTTOM]
// y / | / | 18, 19, 20, 21, [10], 22, 23, 24, 25
// | / | / |
// | [15]____|[16]____[17]_ | [Array Indices]
// | [18] [19]| [20]
// | / | / +Y -Z
// | [21] [10] | [22] | /
// | / | / | /
// | / | / |/
// [23]____[24]____[25] --- x .-------> +X


It seems simple enough but sloped movement will be difficult.