# Why is searching through 3D neighbours given certain parameters in my pathfinding algorithm slow?

I'm currently new to the whole pathfinding thing (and coding in general thing), but I seem to have figured it out. It is 3D pathfinding, working on a 3d array of nodes. Everything works, but my problem is the way I check neighbours is very very slow. My game is a grid based, turn based game so while the pauses aren't the worst, it's still a bit noticable. My math skills are pretty much 0, so when coming up with this way to check neighbours based on the parameters/"rules" I want, I pretty much brute forced it. Here are the rules:

Everyone can move north,south,east,west If you can fly, in addition to NSEW, you can also move Up, Down, U+N, U+S, U+E U+W, D+N, D+S, D+E, D+W If you can fall, in addition to NSEW, you can also move D+N, D+S, D+E, D+W If you can climb ladders, you can also go U+N, U+S, U+E U+W, D+N, D+S, D+E, D+W at ladders.

I haven't put in the down portion of the ladders yet as this is already slowing down and I wanted to figure it out before I go ahead and do that.

Anyways, if anyone cares to take a look at this monster block of code and give me some advice/lend a hand I'd truly appreciate it <3

    /// <summary>
/// Return a list of neighbours to specified Node
/// </summary>
/// <param name="node">Node to check</param>

/// <param name="canFall"></param>
/// <param name="canFly"></param>
/// <returns></returns>
private List<Node> ScanNeighbours(Node node, bool canClimbLadders, bool canFall, bool canFly)
{
List<Node> list = new List<Node>();

#region NSEW regular checks

//North
Vector3 west = node.pos;
west.x -= 1;
Node westNode = gridManager.GetNodePos(west);
if (westNode != null && westNode.isEmpty)
{
}

//South
Vector3 east = node.pos;
east.x += 1;
Node eastNode = gridManager.GetNodePos(east);
if (eastNode != null && eastNode.isEmpty)
{
}

//East
Vector3 north = node.pos;
north.z += 1;
Node northNode = gridManager.GetNodePos(north);
if (northNode != null && northNode.isEmpty)
{
}

//West
Vector3 south = node.pos;
south.z -= 1;
Node southNode = gridManager.GetNodePos(south);
if (southNode != null && southNode.isEmpty)
{
}

#endregion

//Flying can check up down and all directions except for diags
if (canFly)
{
//Up
Vector3 up = node.pos;
up.y += 1;
Node upNode = gridManager.GetNodePos(up);
if (upNode != null && upNode.isEmpty)
{
}

//Down
Vector3 down = node.pos;
down.y -= 1;
Node downNode = gridManager.GetNodePos(down);
if (downNode != null && downNode.isEmpty)
{
}

//UpWest
Vector3 upWest = node.pos;
upWest.y += 1;
upWest.x -= 1;
Node upWestNode = gridManager.GetNodePos(upWest);
if (upWestNode != null && upWestNode.isEmpty)
{
}

//UpEast
Vector3 upEast = node.pos;
upEast.y += 1;
upEast.x += 1;
Node upEastNode = gridManager.GetNodePos(upEast);
if (upEastNode != null && upEastNode.isEmpty)
{
}

//UpNorth
Vector3 upNorth = node.pos;
upNorth.y += 1;
upNorth.z += 1;
Node upNorthNode = gridManager.GetNodePos(upNorth);
if (upNorthNode != null && upNorthNode.isEmpty)
{
}

//UpSouth
Vector3 upSouth = node.pos;
upSouth.y += 1;
upSouth.z -= 1;
Node upSouthNode = gridManager.GetNodePos(upSouth);
if (upSouthNode != null && upSouthNode.isEmpty)
{
}
}

//Flying can jump down ledges as well so check
if (canFall || canFly)
{
Vector3 downWest = node.pos;
downWest.y -= 1;
downWest.x -= 1;
Node downWestNode = gridManager.GetNodePos(downWest);
if (downWestNode != null && downWestNode.isEmpty)
{
}

Vector3 downEast = node.pos;
downEast.y -= 1;
downEast.x += 1;
Node downEastNode = gridManager.GetNodePos(downEast);
if (downEastNode != null && downEastNode.isEmpty)
{
}

Vector3 downNorth = node.pos;
downNorth.y -= 1;
downNorth.z += 1;
Node downNorthNode = gridManager.GetNodePos(downNorth);
if (downNorthNode != null && downNorthNode.isEmpty)
{
}

Vector3 downSouth = node.pos;
downSouth.y -= 1;
downSouth.z -= 1;
Node downSouthNode = gridManager.GetNodePos(downSouth);
if (downSouthNode != null && downSouthNode.isEmpty)
{
}

}

//Flying doesnt need to climb ladders, so don't check again
{
{
{
case Direction.west:
Vector3 upWest = node.pos;
upWest.y += 1;
upWest.x -= 1;
Node upWestNode = gridManager.GetNodePos(upWest);
if (upWestNode != null && upWestNode.isEmpty)
{
}

break;

case Direction.east:
Vector3 upEast = node.pos;
upEast.y += 1;
upEast.x += 1;
Node upEastNode = gridManager.GetNodePos(upEast);
if (upEastNode != null && upEastNode.isEmpty)
{
}
break;

case Direction.north:
Vector3 upNorth = node.pos;
upNorth.y += 1;
upNorth.z += 1;
Node upNorthNode = gridManager.GetNodePos(upNorth);
if (upNorthNode != null && upNorthNode.isEmpty)
{
}
break;

case Direction.south:
Vector3 upSouth = node.pos;
upSouth.y += 1;
upSouth.z -= 1;
Node upSouthNode = gridManager.GetNodePos(upSouth);
if (upSouthNode != null && upSouthNode.isEmpty)
{
}
break;
}
}
}
}
return list;

}


Two major improvements you can make here:

1: Do not construct a new List object every time you scan for neighbours

List<Node> list = new List<Node>();


This line needs to allocate memory to hold the list, and update the garbage collector to keep track of it so it can clean it up later. This is expensive.

Instead, either keep one list around as a member variable that you can re-use for every call (clearing it once you've used its benefits), or create one list at the start of the pathfinding query and pass it into the neighbour-finding subroutine as an argument.

2: Check to see if you've already explored this cell before you add it to the list

Basically, whenever you can exclude a cell from consideration, do so. You may already be doing this elsewhere in your code, and the exact logic depends on the type of search you're doing (eg. for Breadth-First Search if you've seen this cell already, it's safe to ignore it entirely, while for Djikstra's algorithm or A* you might have discovered a shorter route to a cell in the open set, so it's only safe to ignore if it's in the closed set).

The other thing you can do to simplify your code is to add the concept of neighbourhoods. Add a few "constant" arrays to define your neighbourhoods up top:

static readonly Vector3Int[] groundNeighbours = new Vector3Int[]{
new Vector3Int(1, 0, 0), new Vector3Int(0, 0, 1),
new Vector3Int(-1, 0, 0), new Vector3Int(0, 0, -1)
}

static readonly Vector3Int[] groundNeighboursWithFall = new Vector3Int[]{
new Vector3Int(1, 0, 0), new Vector3Int(0, 0, 1),
new Vector3Int(-1, 0, 0), new Vector3Int(0, 0, -1),
new Vector3Int(1, -1, 0), new Vector3Int(0, -1, 1),
new Vector3Int(-1, -1, 0), new Vector3Int(0, -1, -1)
}

static readonly Vector3Int[] airNeighbours = new Vector3Int[]{
new Vector3Int(1, 0, 0), new Vector3Int(0, 0, 1),
new Vector3Int(-1, 0, 0), new Vector3Int(0, 0, -1),
new Vector3Int(1, 1, 0), new Vector3Int(0, 1, 1),
new Vector3Int(-1, 1, 0), new Vector3Int(0, 1, -1),
new Vector3Int(1, -1, 0), new Vector3Int(0, -1, 1),
new Vector3Int(-1, -1, 0), new Vector3Int(0, -1, -1)
}


Then your giant collection of if statements can get much more concise - just select your neighbourhood then iterate over it:

Vector3Int[] neighbourhood = groundNeighbours;

if(canFly)
neighbourhood = airNeighbours;
else if (canFall)
neighbourhood = groundNeighboursWithFall;

foreach(var offset in neighbourhood) {
var site = node.pos + offset;
var neighbour = gridManager.GetNodePos(site);
if(neighbour != null && neighbour.isEmpty)
}


It's up to you whether you want to handle each directional ladder case as another neighbourhood, or just cover ladders as a special-case addition at the end.

Here we're spending a little extra on the additions, since we're adding a vector instead of a single component (not sure if this gets vectorized under the hood on some platforms - that would certainly be nice!), but since we're running the same code over and over again in a tight loop, the instruction cache and branch predictor may be able to do a little better for us. So, you might or might not see a performance difference from this code change, but at the very least, it's a lot fewer lines to maintain!

You are working on a grid, which means that it should be easy to achieve fast path finding.

With A*, it is important to get O(1) tests for checking if a node is in CLOSED or OPEN set.

You do not want to iterate these OPEN and CLOSED sets to see if it contains an entry.

Instead, you store OPEN/CLOSED bits on the grid itself. That way, the test and also moving a node in or out of a set is then a simple O(1) operation.

Since you indicated that scanning for neighbours is your bottleneck, and not the testing of the sets, I will assume you already have this covered.

Now on to scanning neighbours:

It would help if you precompute the neighbours for each grid node. That way, you don't have to scan for them on the fly while doing the A* search.

I would also drop the use of dynamic data structures for storing neighbours. You already know the limit of how many neighbours a node can have. Say 20, then just store a fixed sized C array with 20 slots, and a counter in each of your grid node. That way you have very fast access to all your neighbours. A dynamic C++ list just gets in the way: it is slower, and I doubt it is much smaller that a statically sized (for worst case) C array.

• My grid changes dynamically quite a bit, and as I'm quite new to programming and all of this wrapping my head around precomputing the nodes and updating them is giving me anxiety lol. I'm going to try my best to do this though
– Flip
Apr 29, 2019 at 15:21