1

我正在做一个关于使用树莓派和激光雷达 2D 扫描仪定位遥控车的研究项目。基本上，一辆汽车将通过扫描仪穿过该地点以获取该地点的 2D 表示，然后它将返回起点。之后，您将能够选择一个适当的点，它会在其中找到一条路径。由于我几乎是编程的初学者，因此在 1 个月内几乎不可能做到这一点，但我会尽力而为 :) 那么我现在想知道的是我应该使用哪种寻路算法？由于 2D 位置的分辨率约为 5000 x 5000“像素”，以厘米为单位表示该位置，我相信我需要一个相当有效的分辨率。是否有任何特定的算法可以在树莓派上运行得足够快，几乎可以立即完成这项工作？如果有，

一些附加信息：我正在使用“像素”二维数组，其中的值表示：

EMPTY_SPACE = 0
FILLED_SPACE = 1
START_POINT = 2
END_POINT = 3
PROCESSING = 4
PROCESSED = 5
VISUAL_ASSISTANCE_POINTS = 6

他们还有第二个可选参数，这意味着到终点的距离，因为我发现这是寻路所必需的。

您可能会发现这是一个骗局：Pathfinding in 2D Arrays，但我并没有真正找到解决我所有问题的方法，因为我正在寻找更具体的答案。

编辑：

我发现这段代码实现了 A* 算法，但我发现它很慢......有什么方法可以加快速度吗？我使用下面相关的图像进行测试，大约需要 80 分钟才能解决。

4

1 回答 1

4

A* 寻路是您最好的选择之一。它广泛用于需要在 2D 网格中找到 A 和 B 之间的路径的游戏。它使用启发式方法来识别有利的节点（如果需要，可以将它们称为像素），从而获得良好的性能（尽管取决于您选择启发式函数的程度）。与任何特定/高度优化的算法相比，该实现很容易。此外，还有各种可用的实现。

至于“几乎立即”的速度，我怀疑你可以单独使用算法来获得它。当需要这样的性能时，将需要应用特定领域的修改。一种解决方案可能是预先计算某些路径。路径可能代表单个节点到每个其他节点的完整映射（在您的情况下，使用 5000x5000 网格是不切实际的）。或者，预先计算的路径可以将网格中的节点块视为单个节点，即从0..10,0..10 中的区域x,y 到10..20,0 中的区域x,y 的任何移动。 .10 使用单个预先计算的路径。这可能不会为您提供最佳路径，但肯定会更快。与计算中的几乎任何事情一样，内存和速度之间总是存在权衡。

还值得澄清的是，您的问题中的“像素”是否指的是汽车的单个运动单元。可能的情况是该区域为 5000x5000，但汽车实际上一次占用 50 个像素。然后，您可以使用单个节点来表示 50 个像素，以加快计算速度并获得更精确的结果。

于 2015-12-31T13:15:21.417 回答