- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我在一个简单的 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/
例如,我有一个父类Author: class Author { String name static hasMany = [ fiction: Book,
代码如下: dojo.query(subNav.navClass).forEach(function(node, index, arr){ if(dojo.style(node, 'd
我有一个带有 Id 和姓名的学生表和一个带有 Id 和 friend Id 的 Friends 表。我想加入这两个表并找到学生的 friend 。 例如,Ashley 的 friend 是 Saman
我通过互联网浏览,但仍未找到问题的答案。应该很容易: class Parent { String name Child child } 当我有一个 child 对象时,如何获得它的 paren
我正在尝试创建一个以 Firebase 作为我的后端的社交应用。现在我正面临如何(在哪里?)找到 friend 功能的问题。 我有每个用户的邮件地址。 我可以访问用户的电话也预订。 在传统的后端中,我
我主要想澄清以下几点: 1。有人告诉我,在 iOS 5 及以下版本中,如果您使用 Game Center 设置多人游戏,则“查找 Facebook 好友”(如与好友争夺战)的功能不是内置的,因此您需要
关于redis docker镜像ENTRYPOINT脚本 docker-entrypoint.sh : #!/bin/sh set -e # first arg is `-f` or `--some-
我是一名优秀的程序员,十分优秀!