Unity A* 寻路崩溃
Unity A* Pathfinding Crashes
所以我试图实现 A* 算法。基本逻辑几乎完成了,但有一个问题我无法解决。
当请求路径时,Unity 停止响应并且我的 PC 变得越来越慢,直到它挂起,我不得不强制关闭。
这里是简化的代码:
public static List<Node> ReturnPath(Vector3 pointA, Vector3 pointB)
{
/* A Bunch of initializations */
while (!pathFound)
{
//add walkable neighbours to openlist
foreach (Node n in GetNeighbours(currentNode))
{
if (!n.walkable)
continue;
n.gCost = currentNode.gCost + GetManDist (currentNode, n);
n.hCost = GetManDist (n, B);
openList.Add (n);
n.parent = currentNode;
}
//check openList for lowest fcost or lower hCost
for (int i = 0; i < openList.Count; i++)
{
if ((openList [i].fCost < currentNode.fCost) || (openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost))
{
//make the currentNode = node with lowest fcost
currentNode = openList [i];
}
openList.Remove (currentNode);
if(!closedList.Contains(currentNode))
closedList.Add (currentNode);
}
//Check if the currentNode it destination
if (currentNode == B)
{
Debug.Log ("Path Detected");
path = RetracePath (A, B);
pathFound = true;
}
}
return path;
}
只要目的地在两个节点之外,这就可以正常工作。如果不止于此,则会出现上述问题。这是为什么?我的第一个猜测是我在 openList 中投入了太多。
注意:我将一个 30 x 30 单位的平台(地板)分成 1x1 的正方形,称为 "nodes"
GetManDist() 获取两个节点之间的曼哈顿距离。
更新:这是工作代码。评论太长了
public List<Node> ReturnPath(Vector3 pointA, Vector3 pointB)
{
List<Node> openList = new List<Node>();
List<Node> closedList = new List<Node>();
List<Node> path = new List<Node> ();
Node A = ToNode (pointA);
Node B = ToNode (pointB);
Node currentNode;
bool pathFound = false;
A.hCost = GetManDist(A, B);
A.gCost = 0;
openList.Add (A);
while (!pathFound) // while(openList.Count > 0) might be better because it handles the possibility of a non existant path
{
//Set to arbitrary element
currentNode = openList [0];
//Check openList for lowest fcost or lower hCost
for (int i = 0; i < openList.Count; i++)
{
if ((openList [i].fCost < currentNode.fCost) || ((openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost)))
{
//Make the currentNode = node with lowest fcost
currentNode = openList [i];
}
}
//Check if the currentNode is destination
if (currentNode.hCost == 0) //Better than if(currentNode == B)
{
path = RetracePath (A, B);
pathFound = true;
}
//Add walkable neighbours to openlist
foreach (Node n in GetNeighbours(currentNode))
{
//Avoid wasting time checking unwalkable and those already checked
if (!n.walkable || closedList.Contains(n))
continue;
//Movement Cost to neighbour
int newGCost = currentNode.gCost + GetManDist (currentNode, n);
//Calculate g_Cost, Update if new g_cost to neighbour is less than an already calculated one
if (n.gCost > newGCost || !openList.Contains (n))
{
n.gCost = newGCost;
n.hCost = GetManDist (n, B);
n.parent = currentNode; //So we can retrace
openList.Add (n);
}
}
//We don't need you no more...
openList.Remove (currentNode);
//Avoid redundancy of nodes in closedList
if(!closedList.Contains(currentNode))
closedList.Add (currentNode);
}
return path;
}
问题出在 currentNode 的值上。由于我们正在检查 openlist 中具有最低 f_Cost 或更低 h_Cost 的节点与 currentNode,在某些情况下寻路遇到墙,必须返回或转弯,导致增加f_Cost和h_Cost(都大于currentNode)。因此,openlist 中不再有任何节点具有较低的 f_Cost/h_Cost,从而导致无限循环。简单的解决方案是每次都将 currentNode 设置为 openList 中的任意元素。
正在添加
currentNode = openlist[0];
在循环的开始。
所以我试图实现 A* 算法。基本逻辑几乎完成了,但有一个问题我无法解决。
当请求路径时,Unity 停止响应并且我的 PC 变得越来越慢,直到它挂起,我不得不强制关闭。
这里是简化的代码:
public static List<Node> ReturnPath(Vector3 pointA, Vector3 pointB)
{
/* A Bunch of initializations */
while (!pathFound)
{
//add walkable neighbours to openlist
foreach (Node n in GetNeighbours(currentNode))
{
if (!n.walkable)
continue;
n.gCost = currentNode.gCost + GetManDist (currentNode, n);
n.hCost = GetManDist (n, B);
openList.Add (n);
n.parent = currentNode;
}
//check openList for lowest fcost or lower hCost
for (int i = 0; i < openList.Count; i++)
{
if ((openList [i].fCost < currentNode.fCost) || (openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost))
{
//make the currentNode = node with lowest fcost
currentNode = openList [i];
}
openList.Remove (currentNode);
if(!closedList.Contains(currentNode))
closedList.Add (currentNode);
}
//Check if the currentNode it destination
if (currentNode == B)
{
Debug.Log ("Path Detected");
path = RetracePath (A, B);
pathFound = true;
}
}
return path;
}
只要目的地在两个节点之外,这就可以正常工作。如果不止于此,则会出现上述问题。这是为什么?我的第一个猜测是我在 openList 中投入了太多。
注意:我将一个 30 x 30 单位的平台(地板)分成 1x1 的正方形,称为 "nodes" GetManDist() 获取两个节点之间的曼哈顿距离。
更新:这是工作代码。评论太长了
public List<Node> ReturnPath(Vector3 pointA, Vector3 pointB)
{
List<Node> openList = new List<Node>();
List<Node> closedList = new List<Node>();
List<Node> path = new List<Node> ();
Node A = ToNode (pointA);
Node B = ToNode (pointB);
Node currentNode;
bool pathFound = false;
A.hCost = GetManDist(A, B);
A.gCost = 0;
openList.Add (A);
while (!pathFound) // while(openList.Count > 0) might be better because it handles the possibility of a non existant path
{
//Set to arbitrary element
currentNode = openList [0];
//Check openList for lowest fcost or lower hCost
for (int i = 0; i < openList.Count; i++)
{
if ((openList [i].fCost < currentNode.fCost) || ((openList [i].fCost == currentNode.fCost && openList [i].hCost < currentNode.hCost)))
{
//Make the currentNode = node with lowest fcost
currentNode = openList [i];
}
}
//Check if the currentNode is destination
if (currentNode.hCost == 0) //Better than if(currentNode == B)
{
path = RetracePath (A, B);
pathFound = true;
}
//Add walkable neighbours to openlist
foreach (Node n in GetNeighbours(currentNode))
{
//Avoid wasting time checking unwalkable and those already checked
if (!n.walkable || closedList.Contains(n))
continue;
//Movement Cost to neighbour
int newGCost = currentNode.gCost + GetManDist (currentNode, n);
//Calculate g_Cost, Update if new g_cost to neighbour is less than an already calculated one
if (n.gCost > newGCost || !openList.Contains (n))
{
n.gCost = newGCost;
n.hCost = GetManDist (n, B);
n.parent = currentNode; //So we can retrace
openList.Add (n);
}
}
//We don't need you no more...
openList.Remove (currentNode);
//Avoid redundancy of nodes in closedList
if(!closedList.Contains(currentNode))
closedList.Add (currentNode);
}
return path;
}
问题出在 currentNode 的值上。由于我们正在检查 openlist 中具有最低 f_Cost 或更低 h_Cost 的节点与 currentNode,在某些情况下寻路遇到墙,必须返回或转弯,导致增加f_Cost和h_Cost(都大于currentNode)。因此,openlist 中不再有任何节点具有较低的 f_Cost/h_Cost,从而导致无限循环。简单的解决方案是每次都将 currentNode 设置为 openList 中的任意元素。
正在添加
currentNode = openlist[0];
在循环的开始。