问题标签 [a-star]

所以我目前的项目主要是在 Python 中，但我希望用 C++ 重写计算成本最高的部分，以尝试提高性能。其中大部分我可以通过从 DLL 文件加载的简单函数来实现，但不是全部。我在 Python 中有一个多维数组，我想在 C++ 中执行操作（特别是 A* 寻路），但我不确定如何翻译它们，并且不断地将数据一次一个地发送到加载的函数中似乎真的效率低下（数组的前两个维度只有几百个，函数需要一次处理数组中的数十个元素，如果不是数百个元素）。

我的想法是在 C++ 中创建一个类，它在设置时创建自己的数组副本（性能不是那么大的问题），并具有在数组上执行并将数据返回到主要 Python 程序的方法。但是，我不确定如何做到这一点，即使这是做这件事的正确方法；这似乎意味着 C++ 代码与主 Python 程序并行运行，直觉告诉我这是个坏主意。

除了如何在 Python 中通过 cTypes 加载简单函数之外，我对集成 C++ 和 Python 了解不多，所以我非常感谢这里的一些指针。请记住，我对 C++ 还比较陌生；我的大部分编程经验都是在 Python 中。在这种情况下，将两者结合在一起的最佳方法是什么？

所以我正在尝试编写 A* 算法的 Python 实现。我的算法很容易找到目标的路径，但是当我让程序可视化封闭和开放列表时，我注意到封闭列表，只要障碍有点复杂，就会膨胀成一个大而完美的菱形。换句话说，我的算法将节点添加到封闭列表中，这些节点比“预期”封闭列表的任何邻居都应该远离目标。

为了说明，当封闭列表中的一个点距离目标 (2, 1) 时，但有一堵墙挡住了去路，算法将添加距离目标 (2, 2) 处的两个节点（尝试和翻墙）和 (3, 1) 处的算法远离目标......没有充分的理由，因为它显然更远。

我不确定我做错了什么。这个距离计算是为了使用“曼哈顿方法”（不适合我的目的，但它不应该导致这样的问题），但其他方法继续提供同样的问题（或者确实是更糟糕的问题）。

填充封闭列表的代码如下所示。这里，.score 2是 H 值，使用上面显示的距离方法计算。

“检查”功能将检查的图块添加到关闭列表中，并将其可行的邻居添加到打开列表中，并且似乎工作正常。该算法似乎允许 H 分数为 X 的所有图块（其中 X 取决于设置目标的迷宫的复杂性）。

将其放慢到逐个节点的可视化基本上表明它正在填充大小为 X 的区域，并在迷宫入口被填充物击中时找到路径。我真的不知道我做错了什么，而且我已经试图解决这个问题两天了。

编辑：为了解决问题，这里是更完整的代码摘录。这是检查（）函数：

这是一个较新版本的迭代，它变慢了，所以我可以看到它的进展。它的目的是找到分数最低的节点[0]（分数是 F、G、H 分数的元组）。

以下是说明多余搜索区域的图像，使用self.totalDist = self.diagCost * math.sqrt(pow(self.xDist, 2) + pow(self.yDist, 2))

或者，从等式中删除 TILE_SIZE 常量会得到这个同样低效的搜索区域：

在我看来，它不应该搜索所有额外的区域——只搜索障碍物周围的区域。

好吧，这是我更新的代码。它没有减速，但没有路径出现。

据我了解：

将当前节点添加到关闭列表中。

找到与当前节点相邻的节点，如果它们不是不可行走节点且不在封闭列表中，则将该节点添加到开放列表中，父节点为当前节点，并计算 F、G 和 H 值。如果该节点已经存在于打开列表中，检查是否通过当前节点到达该节点会导致较低的 G 值 - 如果是，则将该节点的父节点设为当前节点。

在打开列表中找到 F 值最高的节点，并将当前节点设为该节点。

重复直到到达目的地，然后通过目的地节点的父节点，您将回到起始节点。那将是最好的道路。

所以，这对我的大脑来说是有意义的，但是当我在图表上实际尝试时，我认为我没有正确理解它。

（从下图）从一开始的绿色瓷砖往下走，F 值为 60 的那一张。那是在打开的列表中，它的 F 值低于右下角的 74 一张。为什么选择 74 而不是 60？

AStar 在直线的基础上工作，AFAIK。

就我而言，我们有地理坐标，我可以得到航点之间的直线距离。但我想知道这会有多近似？“公路”的实际距离可能会有所不同。

例子。假设 A 和 B 在同一平面上，并且与目标点等距，如果我们考虑 A 和目标点之间的直线，B 和目标点。

A 和目标点之间的“公路”距离可能大于或小于 B。但由于 AStar 以直线为基础工作，因此它将返回两条路线最短。

那是对的吗？

如果是，那么应该考虑哪种算法，如果我们想要以 Km/m 为单位的实际距离为基础的结果？

如果不是，那么我错过的重点是什么？

我正在使用 A* 在我正在处理的 Java 项目中进行寻路。不过，我尝试实施它有一些问题。它不仅有点慢，而且有时会遇到永远找不到路径的无限循环问题。我相信这是我的代码中某个地方的错误的结果。路径查找器在 3d 空间上运行，并使用基本启发式（如果需要，我可以提供代码，但是，它只是计算两点之间的距离平方）。

代码在这里：

路径节点在这里：

Point 只是一个定义整数 x、y、z 值的包装类。

我正在使用 Apache Commons PriorityBuffer 来存储路径节点。帮助将不胜感激 - 在此先感谢！

（对于某些人来说，我的代码中的坐标约定可能非常混乱——这真的很奇怪。除非有人指出这可能是问题所在，否则我不会解释它。我认为问题在于我使用了“漫游”指针[参见下面的回溯]。）

所以我有这个结构：

我在其上运行 A* 搜索地图上的路径：

我的回溯功能是

我将 astarnode 打印为：

我的移动功能模板：

为此，我得到以下跟踪：

地址似乎是正确的，但为什么 xpos' 都变成了 0？我错过了什么？

我目前有一个来自 A* 寻路函数结果的点 (x,y) 数组。设置此数组，以便第一个索引是最接近字符的点，下一个是需要在路径中经过的下一个点。

这些点在一个网格上（目前网格上每个点之间有 8 个像素，这是可以更改的。）

我目前的策略是将角色移动到第一个点，当他到达那个点时，然后移动到下一个点，就这么简单。

我通过创建一个从角色到该点的向量来移动到第一个点，并找出它有多远。然后我找到角度并朝那个方向移动。

absVX并absVy存储剩余的绝对距离，并在每次移动后递减。如果它们都低于或等于零，那么我们已经到达目的地，我们将它从数组中删除，并用下一个点重新计算所有内容。

我有两个问题。

1. 有时角色会跳过一个点，然后他就永远旅行了。这很可能是由于游戏引擎添加到运动中的增量（光滑）并且角色移动得太远，不过我不确定这一点。

2. 当我单击目标时，这很好用，但我需要的是能够按住鼠标按钮。目前，如果我按住鼠标，角色只会在第一点“静止”。

我有一个解决第二个问题的想法，但我不确定这是一个好主意。它是存储您想从最后一次鼠标单击开始的位置，但在您通过移动到的点之前不会实际计算它。

所以，我希望真正聪明有趣的人可以和我谈谈这个：D

从这个链接：http ://www.policyalmanac.org/games/aStarTutorial.htm

如果相邻的方格已经在打开列表中，请检查通往该方格的这条路径是否更好。换句话说，如果我们使用当前方块到达那里，检查那个方块的 G 分数是否更低。如果没有，不要做任何事情。

例子：

父级（已遍历）：O
分支：A、B、C

父（工作）：A
分支：B，D

打开的列表包含 A、B、C，现在是 D。

现在，上面引用中的粗体陈述是比较哪条路径，路径 A 到 B？ 即A 与 B 的比较&& O 与 B 的比较或A 与 B的比较&& A 与 D 的比较

请澄清。

我需要为Peg solitaire / Senku 游戏编写求解器这里
已经有一个问题，但建议的答案是带有回溯的蛮力算法，这不是我正在寻找的解决方案。 我需要找到一些启发式方法来应用 A* 算法。剩余的钉子不是一个好的启发式，因为每一步都会丢弃一个钉子，因此成本始终是统一的。 有任何想法吗？