真实二维区域中的Java寻路

Question

我正在做一个研究项目，使用 raspberry pi 和激光雷达 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 ，但我并没有真正找到所有问题的解决方案，因为我正在寻找更具体的答案。

编辑:

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

Answer 1

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

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

同样值得澄清的是，您问题中的“像素”是否指汽车的单个运动单位。可能是面积是 5000x5000 但汽车实际上一次占据了 50 个像素。那么您可能会使用单个节点来表示 50 个像素，以加快计算速度并获得更精确的结果。