Improve pathfinding on stairs(Answered).

Behavior & Navigation Navigation
1

Below you can see my pathfinding pretty much working the way I need. I’m using AStar. There is a small issue with the stairs that I can’t seem to think of a solution. As you can see it the path takes a small shortcut and does not go up the stairs correctly.

2946627--218269--Capture.PNG
2946627--218269--Capture.PNG1269×734 125 KB

Below is my logic for adding neighbors to path find and getting a Cost. Sadly my pathfinding is done in a separate thread so I cant use Unity Raycasting.
My main way of pathfinding to proper nodes is doing a height check between nodes and that’s how I implemented my stairs. Any help would be most appreciated.

        public static void Expand(CPath path, CGridNode neighbour)
        {
            //Is neigbour null(Its out of bounds) && Is Walkable Check
            if (neighbour == null || path.closed[neighbour.x, neighbour.y, neighbour.z] || !neighbour.isWalkable)
                return;

            //Height Check
            if (neighbour.grid.GetHeightDiffrence(neighbour, path.best.current) > path.maxHeightToExpand)
                return;

            //Force 4way if we dont allow diganal movement
            if (!path.allowDiagnal && Vector2.Distance(new Vector2(neighbour.x,neighbour.z),new Vector2(path.best.current.x, path.best.current.z)) > 1)
                return;

            //EXPAND
            path.closed[neighbour.x, neighbour.y, neighbour.z] = true;
            path.open.Add(new CExpansion(neighbour, path.best, CalculateCost(path, neighbour)));
        }

        public static float CalculateCost(CPath path, CGridNode gridNode)
        {
            float g = gridNode.grid.GetDistance(gridNode, path.startNode);
            float h = gridNode.grid.GetDistance(gridNode,path.startNode);
            float penalty = 0;

            //Add penalty if Grid nodes is not on same layer to give better pathing
            if (gridNode.y != path.best.current.y)
                penalty += 100 * gridNode.y;

            return g + h + penalty;
        }

Here is a link to full Unity project on GitHub
https://github.com/nickkorta/CSharp-Unity-Pathfinding

2

There is a node at just before the top of the stairs (where the turn occurs)… make sure that its neighbours are ONLY the landing, and going down the stairs.

…

wait… is your code logically determining neighbours on the fly as the AStar calculates? Usually one pre-calculates that, not determines it on the fly every time a path is calculated. That’ll just make your pathfinding slow.

1 Like
3

Are you building the graph in another thread, or just doing the actual pathfinding?

If you can build the graph in your main thread, then here is an idea to perhaps improve your generated graph:

When you detect two nodes of differing heights, do a bunch of raycasts against the ground at close intervals between the nodes to see if it is a smooth ramp, or if it is a discontinuity, such as the edge of the stairs.

As long as it is a discontinuity, then give that section a super-high cost.

Alternately, build the whole graph, then traverse vertical cliff cuts and chop out node connections almost like scissors as you pass through them, a simple 2D line intersection. That would sever your graph at cliffs.

1 Like
4

If you’re using Unity’s built-in Navmesh, this pathfinding issue happens as a result of having a stepheight thats too high. lowering the step height however is typically not the solution and it’d either case accuracy or performance issues.

On option you can do is deselect the meshes for the stairsfrom the nav mesh (thereby disconnecting the floors) and then reconnecting the floors via Navmesh links. This way agents that traverse the map will be forced to follow the link when they want to switch floors. you’d have to worry about traffic issues however.

another option is to include an invisible mesh to serve as a railing or higher cost terrain along the side of a stairway which would encourage or force agents to traverse a stairway to/from the front.

EDIT: on the topic of building your own pathfinding. The way I’ve typically done it is to work it in two stages. The nodes behave as a 2D linked list when node A and node b are placed next to each other they detect each and set them in one of their links (north, south, east or west neighbor). when a stair is placed down its only allowed to have 2 neighbors (forward and backwards) and thus its side neighbors will be null. there still there but as far as pathfinding is concerned that node doesn’t know about the other one.

after a node linkup happens I call the entire roadmap “dirty” and a controller needs to recache and important data it needs that would assist in pathfinding. For example one of my games modeled the map as a bi-connected graph. which allowed me to easily find which nodes are chokepoints and are off limits for obstruction. and it pre-cached that the instant the map became dirty.

then in the 2nd stage the Agents can then perform their cost calculations figure out the path they want to take each update.

2 Likes
5

Thanks for all the replies.

Thanks it’s determined everything time u pathfind. I was thinking it would use to much memory up if I kept a list at all times. Landing seems like a fine idea.

That sounds interesting. No my graph is not created in a thread since it runs once per level loaded. I can combine your idea with the reply above u and i could get it to work.

6

I’ll try making a stairs layer and assign stairs with it. I can check which way the stairs is facing and adjust neighbors according to that. Thanks

7

Ok I got it working!!!
Nodes now get neighbors when the grid is created. This really opened up a new world of possibilities.
After nodes get their neighbors each node then gets it raycast function called which edits neighbors. I assign all my stairs to the stair layer. Then if a node hits a stair, it checks which way its facing and then deletes neighbor nodes. This works for what I need but It may seem to not be future proof for games that need higher resolution grid and there can be a lot more nodes on the stairs but no problem. Kurt-Dekker idea about multiple recasting to check if its an edge would fix this.

I really appreciate all the replies and each one has its own solution to the problem, it just depends on the needs of your project. Below is code and here is the GitHub project for others, it was fixed on version 1.65.

https://github.com/nickkorta/CSharp-Unity-Pathfinding

public class CGridNode
    {
        public CGrid grid;
        public int x;
        public int y;
        public int z;
        public Vector3 position;
        public List<CGridNode> neighbours;
        public float[] costs;
        public bool isWalkable = true;

        public CGridNode(CGrid grid, int x, int y, int z)
        {
            this.grid = grid;
            this.x = x;
            this.y = y;
            this.z = z;
            position = new Vector3(x * grid.nodeSize, y * grid.heightPerDimensionY, z * grid.nodeSize);
            isWalkable = false;
        }

        public void GetNeighbours()
        {
            neighbours = new List<CGridNode>();

            for (int xOffset = -1; xOffset <= 1; ++xOffset)
                for (int yOffset = -1; yOffset <= 1; ++yOffset)
                    for (int zOffset = -1; zOffset <= 1; ++zOffset)
                        if (xOffset == 0 && yOffset == 0 && zOffset == 0)
                            continue;
                        else neighbours.Add(grid.GetGridNode(x + xOffset, y + yOffset, z + zOffset));

            neighbours.RemoveAll(item => item == null);
        }

        public void Raycast()
        {
            List<CGridNode> neigboursToRemove = new List<CGridNode>();
            GameObject stairsHitObject = null;

            //Raycast To Ground
            RaycastHit hit;
            if (Physics.Raycast(position + new Vector3(0, grid.heightPerDimensionY, 0), Vector3.down, out hit, grid.heightPerDimensionY, grid.groundMask))
            {
                //Ground
                if ((grid.groundMask == (grid.groundMask | (1 << hit.transform.gameObject.layer))))
                {
                    position.y = hit.point.y;
                    if (position.y <= y * grid.heightPerDimensionY)
                        position.y = y * grid.heightPerDimensionY;
                    isWalkable = true;
                }
                if ((grid.stairsMask == (grid.stairsMask | (1 << hit.transform.gameObject.layer))))
                    stairsHitObject = hit.transform.gameObject;
            }

            ////Wall
            foreach (CGridNode gridNode in neighbours)
            {
                Vector3 rayPosition = position + new Vector3(0,grid.nodeSize * 0.5f, 0);
                if (Physics.Raycast(rayPosition, (gridNode.position + new Vector3(0,grid.nodeSize * 0.5f, 0) - rayPosition).normalized, out hit,grid.nodeSize, grid.wallMask))
                    neigboursToRemove.Add(gridNode);
            }
           
            //Stairs
            if (stairsHitObject != null)
            {
                if (stairsHitObject.transform.rotation.eulerAngles.y != 0)
                {
                    neighbours.Remove(grid.GetGridNode(x - 1, y, z));
                    neighbours.Remove(grid.GetGridNode(x + 1, y, z));
                    if (grid.GetGridNode(x - 1, y, z) != null) grid.GetGridNode(x - 1, y, z).neighbours.Remove(this);
                    if (grid.GetGridNode(x + 1, y, z) != null) grid.GetGridNode(x + 1, y, z).neighbours.Remove(this);
                }
                else
                {
                    neighbours.Remove(grid.GetGridNode(x, y, z - 1));
                    neighbours.Remove(grid.GetGridNode(x, y, z + 1));
                    if (grid.GetGridNode(x, y, z - 1) != null) grid.GetGridNode(x, y, z - 1).neighbours.Remove(this);
                    if (grid.GetGridNode(x, y, z + 1) != null) grid.GetGridNode(x, y, z + 1).neighbours.Remove(this);
                }
            }

            //Remove
            while (neigboursToRemove.Count > 0)
            {
                neighbours.Remove(neigboursToRemove[0]);
                neigboursToRemove.RemoveAt(0);
            }
        }
    }
}
8

Here is a picture of it working. Se my previous comment for solution.2948205--218487--Capture.PNG