A*寻路算法无限WHILE LOOP(c#)(单位)

Question

我正在努力想出我的"拥有"；a*路径查找算法，遵循本文的解释：https://www.redblobgames.com/pathfinding/a-star/introduction.html

但我的寻路代码似乎遇到了某种中篇while循环，这会间接破坏Unity。但我真的不知道我做错了什么

这是我的代码

EDIT：unity编辑器似乎由于OutOfMemory异常而崩溃。我不知道发生了什么事公共类PathFinding｛

List<PathNode> openList;
List<PathNode> closedList;
Grid_Ian<PathNode> grid;


public PathFinding(Grid_Ian<PathNode> grid)
{
openList = new List<PathNode>();
closedList = new List<PathNode>();
this.grid = grid;
}
public List<PathNode> makePath(PathNode startNode, PathNode endNode)
{
if (startNode == null || endNode == null)
{
return new List<PathNode>();
} 
if(grid.getGridObject(startNode.x,startNode.y) == null
|| grid.getGridObject(endNode.x, endNode.y) == null)
{
return new List<PathNode>();
}
startNode.hCost = calculateDistanceCost(startNode, endNode);
startNode.gCost = 0;
startNode.calculateFCost();
startNode.cameFrom = null;
openList.Add(startNode);
PathNode currentNode = startNode;
while (openList.Count > 0)
{

Debug.Log("LOOPING");
currentNode = getLowestFcost(openList);
openList.Remove(currentNode);
closedList.Add(currentNode);
if (currentNode.x == endNode.x &&
currentNode.y == endNode.y)
{
return getPath(currentNode);
}
foreach (PathNode next in getNeighbors(currentNode))
{
int newCost = currentNode.fCost + calculateDistanceCost(currentNode, next);
if (closedList.Contains(next)) continue;
if (next.cameFrom == null || newCost < next.fCost)
{
Debug.Log("NUEVO VECINO");
int nextCost = calculateDistanceCost(currentNode, next);
next.gCost = currentNode.gCost + nextCost;
next.hCost = currentNode.hCost + nextCost;
next.calculateFCost();
next.cameFrom = currentNode;
openList.Add(next);
}
}

}
return new List<PathNode>();



}
public List<PathNode> getNeighbors(PathNode currentNode)
{
List<PathNode> neighborNodes = new List<PathNode>();
if (currentNode.x - 1 >= 0)
{
//left
neighborNodes.Add(getNode(currentNode.x - 1, currentNode.y));
}
if (currentNode.x + 1 >= 0)
{
//right
neighborNodes.Add(getNode(currentNode.x + 1, currentNode.y));
}
//up
if (currentNode.y + 1 >= 0)
{
neighborNodes.Add(getNode(currentNode.x, currentNode.y + 1));
}
//down
if (currentNode.y - 1 >= 0)
{
neighborNodes.Add(getNode(currentNode.x, currentNode.y - 1));
}
return neighborNodes;
}
public PathNode getNode(int x, int y)
{
if(grid.getGridObject(x,y) == null)
{
}
return grid.getGridObject(x, y);
}
private PathNode getLowestFcost(List<PathNode> nodeList)
{
PathNode lowestNode = getNode(0,0); // TODO : ARREGLAR
int fCost = 0;
foreach (PathNode node in nodeList)
{
if (fCost > node.fCost)
{
fCost = node.fCost;
lowestNode = node;
}
}
return lowestNode;
}
private int calculateDistanceCost(PathNode a, PathNode b)
{
return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}
private List<PathNode> getPath(PathNode currentNode ){
List<PathNode> path = new List<PathNode>();
path.Add(currentNode);
while (currentNode.cameFrom != null)
{
currentNode = currentNode.cameFrom;
path.Add(currentNode);

}
path.Reverse();
return path;
}
public void getXY(Vector3 worldPosition, out int x, out int y)
{
grid.GetXY(worldPosition, out x, out y);
}
}
public class PathNode {
public int x, y;
public int hCost, gCost,fCost;
public PathNode cameFrom;
// G = start
// H = end
// F = G + H 
public PathNode(int x,int y)
{
this.x = x;
this.y = y;

}
public void calculateFCost()
{
fCost = hCost + gCost;
}
}

Answer 1

我试着用我的和2个你可以尝试的想法来检查你的代码。

首先，我认为你不应该在foreach中在if之前设置newCost。所以你可以尝试：

foreach (PathNode next in getNeighbors(currentNode))
{

if (closedList.Contains(next)) continue;

int newCost = currentNode.fCost + calculateDistanceCost(currentNode, next);

if (next.cameFrom == null || newCost < next.fCost)
{
Debug.Log("NUEVO VECINO");
int nextCost = calculateDistanceCost(currentNode, next);
next.gCost = currentNode.gCost + nextCost;
next.hCost = currentNode.hCost + nextCost;
next.calculateFCost();
next.cameFrom = currentNode;
openList.Add(next);
}
}

或者还有一件事。由于某些原因，我又有一个openList。在我将其添加到openList之前包含检查。我不知道为什么我又这样做了，但我想也许你可以试试，不知道这是否有帮助。我很久以前就做了：

foreach (PathNode next in getNeighbors(currentNode))
{
int newCost = currentNode.fCost + calculateDistanceCost(currentNode, next);
if (closedList.Contains(next)) continue;
if (next.cameFrom == null || newCost < next.fCost)
{
Debug.Log("NUEVO VECINO");
int nextCost = calculateDistanceCost(currentNode, next);
next.gCost = currentNode.gCost + nextCost;
next.hCost = currentNode.hCost + nextCost;
next.calculateFCost();
next.cameFrom = currentNode;

if(!openList.Contains(next))
{
openList.Add(next);
}
}
}

Answer 2

我又发现了两件事。

首先，你的getNode函数不应该是这样的：

public PathNode getNode(int x, int y)
{
if(grid.getGridObject(x,y) == null)
{
}
return grid.getGridObject(x, y);
}

应该是：

public PathNode getNode(int x, int y)
{
if(grid.getGridObject(x,y) != null)
{
return grid.getGridObject(x, y);
}
return null; //need error handling
}

第二件事是为了你的getNeighbors。我不知道你是如何创建节点的，但例如，它们在网格中，你应该检查是否有X和Y的东西，而不是OutOfIndex。在这里，我检查出了一个邻居节点的代码：

if (checkX >= 0 && checkX < gridSizeX)
{
if (checkY >= 0 && checkY < gridSizeY)
{
neighborList.Add(nodeArray[checkX, checkY]);
}
}

由于添加到openList NULL 的getNode函数