带有寻路算法的堆栈溢出

Question

我一直在做一个项目，简而言之，它将生成一个2D数字矩阵，其中“空”空格由0表示。每个数字由一个节点列表连接。节点包含数值、数字的X和Y位置以及与其相邻的所有空间(其“邻居”)的列表，但与该点对角线相邻的空间除外，因为算法只允许向上、向下、向左和向右移动。我遇到的问题是，正如标题所暗示的那样，我正在经历一些堆栈溢出问题。我将在下面发布我的代码，如果有人可以帮助，我将非常感激。

CoordList* Puzzle::GeneratePath(CoordList* Path, int GoalX, int GoalY)
{
int CurrX;
int CurrY;

CurrX = Path->NeighborX;
CurrY = Path->NeighborY;

if(CurrX == GoalX && CurrY == GoalY)
{
    return(Path);
}
else
{
    int NewX;
    int NewY;
    double NewDistance;
    int OldX;
    int OldY;
    double OldDistance;
    CoordList* PointNeighbors = NULL;
    CoordList* BestChoice = NULL;

    for(int i = 0; i < NumDirections; i++)
    {
        CoordList* NewNeighbor = new CoordList;
        NewX = CurrX + DirectsX[i];
        NewY = CurrY + DirectsY[i];
        if(IsPossible(NewX, NewY))
        {
            NewNeighbor->NeighborX = NewX;
            NewNeighbor->NeighborY = NewY;

            if(PointNeighbors == NULL)
            {
                NewNeighbor->next = NULL;
                PointNeighbors = NewNeighbor;
            }
            else
            {
                NewNeighbor->next = PointNeighbors;
                PointNeighbors = NewNeighbor;
            }
        }
        //delete NewNeighbor;
    }

    while(PointNeighbors != NULL)
    {
        if(BestChoice == NULL)
        {

            CoordList* AChoice = new CoordList;
            AChoice->next = NULL;
            NewX = PointNeighbors->NeighborX;
            NewY = PointNeighbors->NeighborY;
            AChoice->NeighborX = NewX;
            AChoice->NeighborY = NewY;
            BestChoice = AChoice;
            PointNeighbors = PointNeighbors->next;
            //delete AChoice;
        }
        else
        {
            NewX = PointNeighbors->NeighborX;
            NewY = PointNeighbors->NeighborY;
            NewDistance = DetermineDistance(NewX, NewY, GoalX, GoalY);

            OldX = BestChoice->NeighborX;
            OldY = BestChoice->NeighborY;
            OldDistance = DetermineDistance(OldX, OldY, GoalX, GoalY);

            if(NewDistance < OldDistance)
            {
                BestChoice->NeighborX = NewX;
                BestChoice->NeighborY = NewY;
            }
            PointNeighbors = PointNeighbors->next;
        }
    }
    BestChoice->next = Path;
    Path = BestChoice;
    return(GeneratePath(Path, GoalX, GoalY));
}
}

我被要求提供我的确定距离函数。这只是传统的点距离公式的一个简单实现。如下所示。

double Puzzle::DetermineDistance(int OneX, int OneY, int TwoX, int TwoY)
{
int DifX;
int DifY;
double PointSum;

DifX = (TwoX - OneX);
DifY = (TwoY - OneY);
DifX = (DifX * DifX);
DifY = (DifY * DifY);
PointSum = (DifX + DifY);
return (sqrt(PointSum));
}

以下是IsPossible函数，该函数确定X和Y值是否位于可能的栅格空间内。

bool Puzzle::IsPossible(int x, int y)
{
if(x + 1 > Size - 1 || x - 1 < 0 
    || y + 1 > Size - 1 || y - 1 < 0)
{
    return false;
}
return true;
}

Answer 1

你可能有一个无限的递归循环，它会导致堆栈溢出，因为你在每次递归中都会创建新的局部变量，特别是在你观察到振荡行为的时候。我假设你在处理小矩阵时不会有这个问题。这只是黑暗中的一枪:-)

振荡问题表明你没有检查你是否已经在一个地方了？

无论如何，也许你想重新考虑使用另一个寻路算法。我建议使用基于代理的解决方案。我曾经使用以下解决方案来解决类似结构的迷宫:我用一个包含了它所在位置的"PositionsList“开始了一个代理，所以在一开始只有一个起点。然后，它将自己复制到不在他自己的PositionList中的每个可到达的位置，将新位置添加到该列表中，然后销毁自己。对所有新代理重复该模式，直到第一个代理达到目标。这样你就能保证找到最优路径。但对于大型矩阵来说，它可能会占用大量内存，特别是当有很多不同的方法可以到达目标，每个位置有很多可能的方向时！但是有很多其他非常好的寻路算法。也许其中一个很适合你:-)

祝好运!