A*路径查找几乎不起作用

Question

我有我的鼻咽癌和他的目标位置。我已经将我的A*路径查找算法放入了代码中。这创造了一条路径，但它绝不是一条理想的路径，也不具有内聚力。我已经写了这篇文章几次，并发现自己面临着同样的问题。

这张图片应该显示了我的问题的结果:最终的路径是到处都是。

​

​

对我来说，算法似乎是在我的地图上找到每个瓦片之间的连接，而不是定位最佳路径。不过，我真的不能确定这是在哪里发生的。

为了清晰起见，我在加载游戏场景时定义了tiles (正方形)和它们的邻居。当程序到达时，GetAdjacentSquares正在使用这些结果来查找有效的磁贴。你会注意到NPC的路径并不是直接以任何绿色的瓦片为中心。

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

我了解到我是从封闭列表中获得最终结果的。一旦我访问了正确的列表，路径就被绘制出来了！

​