C# A* 算法 StackOverflowException

Question

我在完善我的 A* 算法时遇到了一些麻烦。我工作得很好，但需要一些微调。我在检查我的磁贴是否有效时收到 WhosebugException。异常发生在 aStar() 方法或 isValid() 函数中。这是我的代码：

    private void aStar(int x, int y) { //Problem
        Point[] refPoints = { new Point(x - 1, y), new Point(x, y - 1), new Point(x, y + 1), new Point(x + 1, y) };
        Point lowPoint = new Point(x, y);
        int lowCost = 1000;

        for (int i = 0; i < refPoints.Length; i++) {
            if (isValid(refPoints[i], true)) { //Problem
                map[refPoints[i].X, refPoints[i].Y].H = Math.Abs(refPoints[i].X - player.X) + Math.Abs(refPoints[i].Y - player.Y);
                map[refPoints[i].X, refPoints[i].Y].G = map[x, y].G + 10;
                map[refPoints[i].X, refPoints[i].Y].F = map[refPoints[i].X, refPoints[i].Y].H + map[refPoints[i].X, refPoints[i].Y].G;

                if (map[refPoints[i].X, refPoints[i].Y].F < lowCost) {
                    lowCost = map[refPoints[i].X, refPoints[i].Y].F;
                    lowPoint = refPoints[i];
                }

                map[refPoints[i].X, refPoints[i].Y].AType = AType.OPEN;
            }
        }

        if (!(lowPoint.Equals(player))) {
            map[lowPoint.X, lowPoint.Y].AType = AType.CLOSED;
            path.Add(lowPoint);
            aStar(lowPoint);
        }
    }

    private void aStar(Point p) {
        aStar(p.X, p.Y); //Problem
    }

    private bool isValid(int x, int y, bool aStar) { //Problem
        if (aStar) {
            return (x >= 0 && x < tileX && y >= 0 && y < tileY && !map[x, y].TileType.Equals(TileType.BLOCK) && 
                !map[x, y].AType.Equals(AType.CLOSED) && !map[x, y].AType.Equals(AType.OPEN));
        } else {
            return (x >= 0 && x < tileX && y >= 0 && y < tileY && !map[x, y].TileType.Equals(TileType.BLOCK));
        }
    }

    private bool isValid(Point p, bool aStar) {
        return isValid(p.X, p.Y, aStar); //Problem
    }

我似乎无法追溯问题的根源，但它只是有时会发生（通常是在路上有障碍物时，但并非总是如此）。

我的代码中没有打开和关闭列表，我在地图的每个图块（空白、打开、关闭）中都有一个枚举 (AType)。 OPEN 枚举实际上不会影响任何东西，除了标记已经过测试且不是最佳着法的棋子。 CLOSED 枚举仅应用于所有被识别为最佳移动的 Tiles，从而最终构建路径。 BLANK 枚举只是 Tile 的默认状态（不在打开或关闭列表中）。

Answer 1

A* 没有递归步骤。您应该将工作项从优先级队列中拉出。

你的代码是尾递归的。这里不需要递归。只需将整个方法包装在 while (true) 循环中：

private void aStar(int x, int y) {
    while (true) {
    //...
    if (!(lowPoint.Equals(player))) {
        map[lowPoint.X, lowPoint.Y].AType = AType.CLOSED;
        path.Add(lowPoint);
        continue;
    }
    else break;
}
}

我怀疑 WhosebugEx 在进行此更改后消失了，但该算法将不起作用，因为我在任何地方都看不到优先级队列。

Answer 2

你基本上在做什么：

void foo(Point a)
{
   ...
   foo(a.X, a.Y);
}
void foo(int x, int y)
{
   foo(new Point(x, y));
}

现在，递归可能非常方便，但在本例中并非如此，因为它不是必需的，而且它会被调用太多，导致 Whosebug。所以你需要重新设计这个函数，这样你就不会调用它自己，而是有一个具有特定条件的 while 循环。

像这样：

void aStar(int x, int y)
{
   // just declarations to show you
   Path path;
   Point currentPoint;
   while (true)
   {
      // Your modified function goal. Instead of calling the function, just let the loop continue
      // if node is goal, break
      if (!(lowPoint.Equals(player)))
      {
        map[lowPoint.X, lowPoint.Y].AType = AType.CLOSED;
        path.Add(lowPoint);
        aStar(lowPoint);
      }
      else
      {
        break;
      }
   }

C# A* 算法 StackOverflowException

C# A* Algorithm StackOverflowException

c#

stack-overflow

path-finding