0

我一直在研究一个项目，简而言之，它将生成一个二维数字矩阵，其中“空”空间由 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;
}
4

1 回答 1

0

您可能有一个导致堆栈溢出的无限递归循环，因为您在每次递归时都会创建新的局部变量，尤其是在观察到的振荡行为时。我假设您对小矩阵没有这个问题。它只是在黑暗中拍摄:-)

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

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

祝你好运！

于 2013-03-21T12:23:21.993 回答