I've got a simple algorithm that generates an array of node positions for a 3D game map:



public Vector3[] GenerateGraphNodes()
{
Vector3[] nodes = new Vector3[width * height * depth];
int numNodes = 0;

for (int x = 0; x < depth; ++x)
{
// Start at row 1 as we are checking the tiles below before create a graph node
for (int y = 1; y < height; ++y)
{
for (int z = 0; z < width; ++z)
{
// If this tile is empty then we can create a node if a tile below exists
if (tiles[x * width * height + y * width + z] == null)
{
if (tiles[x * width * height + (y - 1) * width + z] != null)
{
// Add graph node
nodes[numNodes].X = TILESIZE * x;
nodes[numNodes].Y = TILESIZE * y;
nodes[numNodes].Z = TILESIZE * z;
++numNodes;
}
}
}
}
}

Vector3[] n = new Vector3[numNodes];

for (int i = 0; i < numNodes; ++i)
{
n = nodes;
}

return n;
}


While this works great and I have all my nodes, how can I efficiently find the closest node to an A.I. character based on its position?

The method I'm currently using is to snap the character's position to the node grid and search the entire node array for the node matching this snapped position. This is highly inefficient and I was wondering what advice you guys could give for finding the nearest node in this scenario?

For example should I be placing the nodes in a bounding volume hierarchy, or using an entirely different approach?

how can I efficiently find the closest node to an A.I. character based on its position?

Have you considered using nearest neighbour search? I don't know about its computational cost though.

By the way, how is array n different from array nodes in your code?

Have you considered using nearest neighbour search? I don't know about its computational cost though.

Nearest neighbour search appears to follow the idea of placing all the nodes in a BVH and then testing the distance from a point inserted, if I'm not mistaken. That's what I'm currently doing so I guess I'm on the right track.

By the way, how is array n different from array nodes in your code?


n returns an array that contains no null nodes, in other words it is an array this is the length of the number of nodes created.

I could return 'nodes' and iterate through until I reach null but I don't see what advantage that would have over an exact array size. This method is not run once per update.

Well, if the nearest object you are searching for is stored in the node array, then you can perform an outward search, especially when you have dense conditions. It won't be any worse than checking every node.

Illustrated:

p = player
x = empty node
n = nearest neighbour
- = searched nodes
[font="Courier New"]
Check if player is on same tile as a neighbour
[font="Courier New"]xxxxxxx
xnxxxxx
[font="Courier New"]xxxxxxx
[font="Courier New"] xxxpxxx
xxxxxxx
xxxxxxx
[font="Courier New"]xxxxxxx
[font="Courier New"]
Check surrounding 1 level out
[font="Courier New"]xxxxxxx
[font="Courier New"]xnxxxxx
xx---xx
xx-p-xx
xx---xx
xxxxxxx
[font="Courier New"]xxxxxxx


[font="Courier New"]Found on level 2
xxxxxxx
[font="Courier New"]xn----x
x-----x
x--p--x
x-----x
x-----x
[font="Courier New"]xxxxxxx


You can do this with a Queue and recursion or with a few loops.

Also, complex but efficient http://en.wikipedia.org/wiki/Kd-tree

'lambrtz' said:

Have you considered using nearest neighbour search? I don't know about its computational cost though.

Nearest neighbour search appears to follow the idea of placing all the nodes in a BVH and then testing the distance from a point inserted, if I'm not mistaken. That's what I'm currently doing so I guess I'm on the right track.

By the way, how is array n different from array nodes in your code?

n returns an array that contains no null nodes, in other words it is an array this is the length of the number of nodes created.

I could return 'nodes' and iterate through until I reach null but I don't see what advantage that would have over an exact array size. This method is not run once per update.

I've had another thought that concerns me.

A lot of 3D/2D A* alogrithms use nodes arranged in a square/cube so they can be packed neatly into an array and neighbouring nodes can be found easily by incrementing/decrementing indices. If I'm using a non square/cube arrangement that doesn't play nice with an array how the heck can I check the neighbouring nodes as quickly?

Using find nearest neighbour each frame for each enemy would be silly in comparison to checking neighbouring nodes by incrementing/decrementing indices, so how can it be done with this arrangement?

EDIT: I type this at the same time as the message above was posted, but my question still stands.

I've had another thought that concerns me.

A lot of 3D/2D A* alogrithms use nodes arranged in a square/cube so they can be packed neatly into an array and neighbouring nodes can be found easily by incrementing/decrementing indices. If I'm using a non square/cube arrangement that doesn't play nice with an array how the heck can I check the neighbouring nodes as quickly?

Using find nearest neighbour each frame for each enemy would be silly in comparison to checking neighbouring nodes by incrementing/decrementing indices, so how can it be done with this arrangement?

EDIT: I type this at the same time as the message above was posted, but my question still stands.

You could store pointers to each node's neighbours within each node. These could be initialized during the initialization of the node array.
e.g.

node[j][k].neighbours.add(node[i+1][j][k]);
node[j][k].neighbours.add(node[j+1][k]);
node[j][k].neighbours.add(node[j][k+1]);

etc..

Then you can easily iterate through neighbours without relying on the indices to perform the transition. But in larger searches you may have to use a "visited matrix", and this becomes expensive.

Alternatively, you could also step through the neighbours in each direction for a number of steps, then switch directions.

Hope that helps.

You could store pointers to each node's neighbours within each node. These could be initialized during the initialization of the node array.
e.g.

node[j][k].neighbours.add(node[i+1][j][k]);
node[j][k].neighbours.add(node[j+1][k]);
node[j][k].neighbours.add(node[j][k+1]);


The problem is that the neighbours aren't going to as simple as [i+1][j][k] etc. because the nodes are created for traversable tiles only and non traversable tiles are ignored and not added to the final array. This means that indices are not arranged in a true 3D array format. Unless I've misunderstood you.

I could create an array that covers every single part of the entire world and leave the non traversable tiles as null, but this would be a huge waste of memory.

Generally speaking, A* is a graph search algorithm, so any graph representation can be used, not only squarish / cubic tiles. You can use adjacency list, which roguan suggested, or adjacency matrix (i suppose s/he referred to it as visited matrix?) to represent a graph, and to find one node's neighbour is just like what roguan mentioned.

This is one possible way for your case. You can firstly retain the null pointers when defining the neighbours of one node, so if one neighbour is a null, you don't add it to the list of neighbours. You can throw away the null pointers afterwards.

PS: I personally prefer to use std::list, or stdext::hash_map in some occasions, but maybe dynamic array is more suitable for your purpose

The problem is that the neighbours aren't going to as simple as [i+1][j][k] etc. because the nodes are created for traversable tiles only and non traversable tiles are ignored and not added to the final array. This means that indices are not arranged in a true 3D array format. Unless I've misunderstood you.

I could create an array that covers every single part of the entire world and leave the non traversable tiles as null, but this would be a huge waste of memory.

I think I understand what you mean, and I suggest you store the neighbour information in the nodes themselves.

When creating your nodeStructure:

for ( node : allNodes){
for ( possibleNeighbour : allTilesSurroundingNode){
if ( !possibleNeighbour.isImpassable() ){
node.addNeighbour(possibleNeighbour);
}
}
}


Then you'll end up with a nice structure in each node containing which nodes are passable around that node.

This is good if your tiles almost never change from passable to impassable or visa-versa.

Thanks for the help guys, I think I understand now. When creating a node, I can have an array of neighbouring nodes:

Maximum of 8 for 2D/2.5D navigation
Maximum of 26 for 3D navigation

The neighbouring nodes are determined after using the algorithm I originally posted and a reference to each neighbour is stored in an array. Each node is a struct which contains information about the node as a bunch of bit field flags or similar.

This leaves me with a large memory problem...

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?