2

我在一个简单的 Winforms 应用程序中实现了 A*-pathfinding。还可以在网格上定义障碍物，以便代理可以在它们周围导航。

问题是我的代理无法预见路径。这就是为什么他并不总是选择最佳路径的原因。

在这里你可以看到我的确切问题。

如何让探路者预测较短的路径？一旦代理走错了路，也会出现死胡同的问题。

此方法获取相邻单元格并计算值：

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);
                }
            }

            }

        }
    }

下面是计算 G 和 H 值的代码：

    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;

    }

最后我计算下一个我想踩的单元格：

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();
    }
4

4 回答 4

3

Dijkstra也有类似的问题，尽管他是基于权重的。

它可能有助于 Peek() 位置，然后评估其在所有位置从 Peek().Peek() 移动的能力。与可导航路径相比，任何无法使用的位置都可能具有极高的权重。

但是这些算法可以完全使用递归来解决，然后从中选择最佳路线。

（我还注意到您在视频中沿对角线移动，这实际上是一个有效的移动，因为直接向上移动将具有相同的 2 个方格的净距离）。

于 2013-06-11T12:55:12.157 回答
3

您的实现问题在于您尚未完全实现 A* 算法。您只实现了（在您的step方法中）算法中单个步骤的下一个最佳猜测。

该算法旨在完全执行，直到达到终点并且您的打开列表中不再有较短的路径（估计）。完成此操作后，您可以根据结果构建最短路径。然后你可以采取正确的步骤。

在没有实际计算整个路径的情况下，A* 从来没有打算立即给出下一步应该做什么的答案。如果实施正确，它将为您提供最佳路径，只要您从给定点估计剩余部分的启发式方法永远不会高估实际剩余距离。

我建议进一步阅读应该如何实现 A* 算法。一个好的开始可能是维基百科。

于 2013-06-11T13:13:15.900 回答
2

A* 不是找到最佳路径的算法 - 如果最佳路径是您所追求的，那么您将不得不使用蛮力方法。A*（基于启发式函数的质量）找到接近最优的路径。

于 2013-06-11T12:54:00.597 回答
2

如果正确实施的 A* 正在生成非最优路径，我认为你有一个不可接受的启发式。一个可接受的启发式算法必须永远不要高估到目标的剩余距离。如果是这样，就会发生像您在视频中展示的那样的事情。

于 2013-06-11T12:57:16.007 回答