我在一个简单的 Winforms 应用程序中实现了 A* 寻路。人们还可以在网格上定义障碍物，以便代理可以绕过它们。
问题是我的代理无法预见路径。这就是为什么他并不总是走最优路径的原因。
Here you can see my exact problem.
如何让探路者预测更短的路径？一旦代理走错了路，也会出现死胡同的问题。
此方法获取相邻单元格并计算值:
public void addAdjascent(Vector pos)
{
foreach(Cell cell in allCells)
{
bool containedInClosedList = closedList.Any(c => c.id == cell.id);
if (!containedInClosedList)
{
if (cell.positionCR.X == pos.X - 1 && cell.positionCR.Y == pos.Y)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if(!containedInBlockedList)
{
cell.H = calcH(goal,cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
if (cell.positionCR.X == pos.X + 1 && cell.positionCR.Y == pos.Y)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if (!containedInBlockedList)
{
cell.H = calcH(goal, cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
if (cell.positionCR.X == pos.X && cell.positionCR.Y == pos.Y - 1)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if (!containedInBlockedList)
{
cell.H = calcH(goal, cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
if (cell.positionCR.X == pos.X && cell.positionCR.Y == pos.Y + 1)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if (!containedInBlockedList)
{
cell.H = calcH(goal, cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
if (cell.positionCR.X == pos.X - 1 && cell.positionCR.Y == pos.Y - 1)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if (!containedInBlockedList)
{
cell.H = calcH(goal, cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
if (cell.positionCR.X == pos.X - 1 && cell.positionCR.Y == pos.Y + 1)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if (!containedInBlockedList)
{
cell.H = calcH(goal, cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
if (cell.positionCR.X == pos.X + 1 && cell.positionCR.Y == pos.Y - 1)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if (!containedInBlockedList)
{
cell.H = calcH(goal, cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
if (cell.positionCR.X == pos.X + 1 && cell.positionCR.Y == pos.Y + 1)
{
bool containedInBlockedList = blockedList.Any(c => c.id == cell.id);
if (!containedInBlockedList)
{
cell.H = calcH(goal, cell);
cell.G = calcG(start, cell);
cell.F = cell.G + cell.H;
openList.Add(cell);
}
}
}
}
}
下面是计算G和H值的代码:
public int calcG(Vector start,Cell cell)
{
int distance = closedList.Count;
return distance;
}
public int calcH(Vector goal, Cell cell)
{
int distance;
int distanceX = (goal.X) - cell.positionCR.X;
int distanceY = (goal.Y) - cell.positionCR.Y;
if (distanceX < 0)
{
distanceX = distanceX * -1;
}
if (distanceY < 0)
{
distanceY = distanceY * -1;
}
distance = distanceX + distanceY;
return distance;
}
最后我计算了我要踩到的下一个单元格:
public void step()
{
addAdjascent(stepPos);
bool foundDestination = false;
int min = 8000;
foreach(Cell openCell in openList)
{
if (openCell.F < min)
{
min = openCell.F;
}
}
if(openList.Count > 0)
{
foreach (Cell openCell in openList)
{
if (openCell.positionCR.X == goal.X && openCell.positionCR.Y == goal.Y)
{
closedList.Add(openCell);
stepPos = openCell.positionCR;
foundDestination = true;
}
}
}
if(!foundDestination)
{
closedList.Add(openList.First(item => item.F == min));
stepPos = openList.First(item => item.F == min).positionCR;
}
openList.Clear();
}
最佳答案
您实现的问题是您没有完全实现 A* 算法。您只实现了(在您的 step 方法中)算法中单个步骤的下一个最佳猜测。
该算法将完全执行，直到完成并且您的打开列表中不再有更短的路径(估计)。这样做之后，您可以根据结果构建最短路径。然后您就可以采取正确的步骤。
A* 绝不意味着在不实际计算整个路径的情况下立即给出下一步应该做什么的答案。如果正确实现，它将为您提供最佳路径，只要您的启发式估计给定点的剩余部分从不高估实际剩余距离。
我建议进一步阅读有关 A* 算法应该如何实现的内容。一个好的开始可能是 wikipedia .
关于c# - 为什么A*找不到最优路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17044485/