Hey there,
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="canClimbLadders"></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)
{
list.Add(westNode);
}
//South
Vector3 east = node.pos;
east.x += 1;
Node eastNode = gridManager.GetNodePos(east);
if (eastNode != null && eastNode.isEmpty)
{
list.Add(eastNode);
}
//East
Vector3 north = node.pos;
north.z += 1;
Node northNode = gridManager.GetNodePos(north);
if (northNode != null && northNode.isEmpty)
{
list.Add(northNode);
}
//West
Vector3 south = node.pos;
south.z -= 1;
Node southNode = gridManager.GetNodePos(south);
if (southNode != null && southNode.isEmpty)
{
list.Add(southNode);
}
#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)
{
list.Add(upNode);
}
//Down
Vector3 down = node.pos;
down.y -= 1;
Node downNode = gridManager.GetNodePos(down);
if (downNode != null && downNode.isEmpty)
{
list.Add(downNode);
}
//UpWest
Vector3 upWest = node.pos;
upWest.y += 1;
upWest.x -= 1;
Node upWestNode = gridManager.GetNodePos(upWest);
if (upWestNode != null && upWestNode.isEmpty)
{
list.Add(upWestNode);
}
//UpEast
Vector3 upEast = node.pos;
upEast.y += 1;
upEast.x += 1;
Node upEastNode = gridManager.GetNodePos(upEast);
if (upEastNode != null && upEastNode.isEmpty)
{
list.Add(upEastNode);
}
//UpNorth
Vector3 upNorth = node.pos;
upNorth.y += 1;
upNorth.z += 1;
Node upNorthNode = gridManager.GetNodePos(upNorth);
if (upNorthNode != null && upNorthNode.isEmpty)
{
list.Add(upNorthNode);
}
//UpSouth
Vector3 upSouth = node.pos;
upSouth.y += 1;
upSouth.z -= 1;
Node upSouthNode = gridManager.GetNodePos(upSouth);
if (upSouthNode != null && upSouthNode.isEmpty)
{
list.Add(upSouthNode);
}
}
//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)
{
list.Add(downWestNode);
}
Vector3 downEast = node.pos;
downEast.y -= 1;
downEast.x += 1;
Node downEastNode = gridManager.GetNodePos(downEast);
if (downEastNode != null && downEastNode.isEmpty)
{
list.Add(downEastNode);
}
Vector3 downNorth = node.pos;
downNorth.y -= 1;
downNorth.z += 1;
Node downNorthNode = gridManager.GetNodePos(downNorth);
if (downNorthNode != null && downNorthNode.isEmpty)
{
list.Add(downNorthNode);
}
Vector3 downSouth = node.pos;
downSouth.y -= 1;
downSouth.z -= 1;
Node downSouthNode = gridManager.GetNodePos(downSouth);
if (downSouthNode != null && downSouthNode.isEmpty)
{
list.Add(downSouthNode);
}
}
//Flying doesnt need to climb ladders, so don't check again
if (canClimbLadders && !canFly)
{
if (node.nodeType == NodeType.ladder)
{
switch(node.ladderDirection)
{
case Direction.west:
Vector3 upWest = node.pos;
upWest.y += 1;
upWest.x -= 1;
Node upWestNode = gridManager.GetNodePos(upWest);
if (upWestNode != null && upWestNode.isEmpty)
{
list.Add(upWestNode);
}
break;
case Direction.east:
Vector3 upEast = node.pos;
upEast.y += 1;
upEast.x += 1;
Node upEastNode = gridManager.GetNodePos(upEast);
if (upEastNode != null && upEastNode.isEmpty)
{
list.Add(upEastNode);
}
break;
case Direction.north:
Vector3 upNorth = node.pos;
upNorth.y += 1;
upNorth.z += 1;
Node upNorthNode = gridManager.GetNodePos(upNorth);
if (upNorthNode != null && upNorthNode.isEmpty)
{
list.Add(upNorthNode);
}
break;
case Direction.south:
Vector3 upSouth = node.pos;
upSouth.y += 1;
upSouth.z -= 1;
Node upSouthNode = gridManager.GetNodePos(upSouth);
if (upSouthNode != null && upSouthNode.isEmpty)
{
list.Add(upSouthNode);
}
break;
}
}
}
}
return list;
}