Why does A* not find the optimal path?

Question

I implemented the A*-pathfinding in a simple Winforms application. Where one can also define obstacles on the grid so the agent can navigate around them.

The Problem is my agent can't foresee paths. This is why he does not always take the optimal path.

Here you can see my exact problem.

How can I make the pathfinder anticipate the shorter paths? There is also an issue with dead ends once the agent took the wrong path.

This Method gets the adjascent cells and calculates the values:

public void addAdjascent(Vector pos) 
    {

        foreach(Cell cell in allCells)
        {
            bool containedInClosedList = closedList.Any(c => c.id == cell.id);

            if (!containedInClosedList)
            {


            if (cell.positionCR.X == pos.X - 1 && cell.positionCR.Y == pos.Y)
            {

                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if(!containedInBlockedList)
                {
                    cell.H = calcH(goal,cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }



            }

            if (cell.positionCR.X == pos.X + 1 && cell.positionCR.Y == pos.Y)
            {
                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if (!containedInBlockedList)
                {
                    cell.H = calcH(goal, cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }
            }

            if (cell.positionCR.X == pos.X  && cell.positionCR.Y == pos.Y - 1)
            {
                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if (!containedInBlockedList)
                {
                    cell.H = calcH(goal, cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }


            }

            if (cell.positionCR.X == pos.X && cell.positionCR.Y == pos.Y + 1)
            {
                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if (!containedInBlockedList)
                {
                    cell.H = calcH(goal, cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }                    
            }

            if (cell.positionCR.X == pos.X - 1 && cell.positionCR.Y == pos.Y - 1)
            {
                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if (!containedInBlockedList)
                {
                    cell.H = calcH(goal, cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }
            }

            if (cell.positionCR.X == pos.X - 1 && cell.positionCR.Y == pos.Y + 1)
            {
                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if (!containedInBlockedList)
                {
                    cell.H = calcH(goal, cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }
            }

            if (cell.positionCR.X == pos.X + 1 && cell.positionCR.Y == pos.Y - 1)
            {
                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if (!containedInBlockedList)
                {
                    cell.H = calcH(goal, cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }
            }

            if (cell.positionCR.X == pos.X + 1 && cell.positionCR.Y == pos.Y + 1)
            {
                bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);

                if (!containedInBlockedList)
                {
                    cell.H = calcH(goal, cell);
                    cell.G = calcG(start, cell);
                    cell.F = cell.G + cell.H;
                    openList.Add(cell);
                }
            }

            }

        }
    }

Here is the code for the calculation of G and H values:

    public int calcG(Vector start,Cell cell) 
    {
        int distance = closedList.Count;

        return distance;
    }

    public int calcH(Vector goal, Cell cell) 
    {

        int distance;

        int distanceX = (goal.X) - cell.positionCR.X;
        int distanceY = (goal.Y) - cell.positionCR.Y;

        if (distanceX < 0)
        {
            distanceX = distanceX * -1;
        }

        if (distanceY < 0)
        {
            distanceY = distanceY * -1;
        }

        distance = distanceX + distanceY;

        return distance;

    }

And finally I calculate the next cell I want to step on:

public void step() 
    {
        addAdjascent(stepPos);
        bool foundDestination = false;
        int min = 8000;

        foreach(Cell openCell in openList)
        {
            if (openCell.F < min) 
            {
                min = openCell.F;
            }
        }

        if(openList.Count > 0)
        {
            foreach (Cell openCell in openList)
            {
                if (openCell.positionCR.X == goal.X && openCell.positionCR.Y == goal.Y)
                {
                    closedList.Add(openCell);
                    stepPos = openCell.positionCR;
                    foundDestination = true;
                }
            }
        }            

        if(!foundDestination)
        {
            closedList.Add(openList.First(item => item.F == min));
            stepPos = openList.First(item => item.F == min).positionCR;

        }

        openList.Clear();
    }

Answer 1

The problem with your implementation is that you've not fully implemented the A* algorithm. You've only implemented (in your step method) the next best guess for a single step in the algorithm.

The algoritm is meant to be executed in full until the finish has been reached and no more shorter paths (estimate) are in your open list. After doing this, you can construct the shortest path from the results. And then you can take the right step.

A* was never meant to give a an immediate answer as of what your next step should be without actually calculating the entire path. If implemented correctly, it will give you the optimal path, as long as your heuristic to estimate the remainder from a given point never overestimates the actual remaining distance.

I would suggest doing some further reading on how the A* algorithm is supposed to be implemented. A good start would probably be wikipedia.

Answer 2

Dijkstra had a similar problem, although his are based on weightings.

It might help to Peek() the location and then assess its ability to move from a Peek().Peek() in all locations. Any locations that cannot be used could have an extremely high weighting, compared to a navigable path.

But these algorithms can be solved entirely using recursion and then select the best route from there.

(I also notice you moved diagonally in your video, which is actually a valid move as moving directly upwards would have the same net distance of 2 squares).

Answer 3

If correctly implemented A* is generating non-optimal paths, I think you have an inadmissible heuristic. An admissible heuristic must NEVER overestimate the remaining distance to the goal. If it does, things like you showed on your video can happen.

Answer 4

A* is not algorithm to find optimal path - if optimal path is what you're after you'll have to use brute force approach. A* (based on quality of heuristic function) finds path that is close to optimal.