A* Path-finding is just barely not working

Question

I have my NPC and I have a target location for him. I have placed my A* path-finding algorithm into the code. This created a path, but it is in no way an ideal path, nor is it cohesive. I have written this piece a few times and have found myself facing the same problem.

This picture should show the result of my problem: the final path is all over the place.

To me, it appears that algorithm is finding a connection between every tile on my map instead of locating the best path. I really can't nail down where this is happening, though.

For some clarity, I am defining the tiles (squares) and their neighbors when I load my game scene. When the program reaches GetAdjacentSquares is is using those results to find valid tiles. You will notice that they NPC's path is not centering directly onto any of the green tiles.

List<Path> GetAdjacentSquares(Path p)
{
    List<Path> ret = new List<Path>();
    TileData tile = tManager.GetTileByCoords(new Vector2(p.x, p.y));
    foreach (Vector2 t in tile.neighborLocs)
    {
        TileData n = tManager.GetTileByCoords(t);
        if (n && n.tType == TileTypes.Houses || n.tType == TileTypes.Road)
        {

            ret.Add(new Path(p, n.tTileLoc.x, n.tTileLoc.y));
        }
    }
    return ret;
}

int BlocksToTarget(Vector2 tileLoc, Vector2 targetLoc)
{
    int final = (int)Mathf.Abs((tileLoc.x - targetLoc.x) * (tileLoc.x - targetLoc.x) + (tileLoc.y - targetLoc.y) * (tileLoc.y - targetLoc.y));
    return final;`
}

bool DoesPathContain(List<Path> paths, Vector2 target)
{
    foreach(Path p in paths)
    {
        if (p.x == target.x && p.y == target.y)
            return true;
    }
    return false;
}

int LowestFScore(List<Path> path)
{
    int lowest = int.MaxValue;
    foreach(Path p in path)
    {
        if (p.f <= lowest)
            lowest = p.f;
    }
    return lowest;
}

void GoHome()
{
    Path current = null;
    //target
    Path destination = new Path(null, cData.houseLoc.x, cData.houseLoc.y);
    //start
    Path start = new Path(destination, transform.localPosition.x, transform.localPosition.y);

    //start by adding the original position to the open list
    List<Path> open = new List<Path>() { start };
    List<Path> close = new List<Path>();

    int g = 0;

    while(open.Count > 0)
    {
        //get the square with the lowest F score
        current = open.Last(p => p.f == LowestFScore(open));
        //add the current square to the closed list
        close.Add(current);
        //remove it from the open list
        open.Remove(current);

        //if we added the destination to the closed list, we've found a path
        if(DoesPathContain(close, cData.houseLoc))
            break;

        //The rest of the algorithm evaluates adjacent tiles
        List<Path> adjacentTiles = GetAdjacentSquares(current);
        g++;

        foreach(Path tile in adjacentTiles)
        {
            Vector2 tileLoc = new Vector2(tile.x, tile.y);
            //if this adjacent square is already in the closed list, ignore it
            if (DoesPathContain(close, tileLoc))
                continue;

            if(!DoesPathContain(open, tileLoc))
            {
                //if this adjacent square is already in the closed list, ignore it
                tile.g = g;
                tile.h = BlocksToTarget(tileLoc, cData.houseLoc);
                tile.parent = current;

                //add it to the open list
                open.Add(tile);
            }
            else
            {
                //test if using the current G score makes the adjacent square's F score
                //lower, if yes update the parent because it means it's a better path
                if (g+tile.h < tile.f)
                {
                    tile.g = g;
                    tile.parent = current;
                }
            }
        }
    }

    //foreach (Path p in close)
    //    Debug.Log(p.f + " ("+p.x+", "+p.y+")");

    walkTo = close;
    cData.isWalking = true;
}

`

Answer 1

I have learned that I was getting my final results from the closed list. Once I accessed the correct list, the path was drawn!