Pathfinding: Searching through 3D neighbours given certain parameters.

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;

    }

How about creating those lists beforehand? Looks like accessibility of your nodes doesn’t change during gameplay, other than being empty or occupied. For each node, you could create a list of accessible neighbours. During gameplay, you would just access a node’s neighbors list and filter that based on your criteria (empty? movement options?)

Your nodes probably have 3D grid coordinates, so you can use the y-pos for filtering in order to include/exclude up and down movement.