Java 真实二维区域寻路
Java pathfinding in a real 2D area
我正在做一个研究项目，使用 raspberry pi 和激光雷达 2D 扫描仪定位遥控车。基本上，汽车将 运行 通过带有扫描仪的地点以获得该地点的 2D 表示，然后它将 return 到达起点。之后，您将能够 select 一个地方，它会在其中找到一条路径。由于我几乎是编程的初学者，所以在 1 个月内几乎不可能做到这一点，但我会尽力而为 :) 那么我现在想知道的是我应该使用哪种寻路算法？由于 2D 位置的分辨率约为 5000 x 5000 "pixels"，这将以厘米为单位表示位置，我相信我需要一个非常高效的分辨率。是否有任何特定算法可以在 raspberry pi 上以足够快的速度几乎立即完成工作？如果有，有没有高效的实现方式？
一些附加信息：
我使用的是“像素”二维数组，其中的值表示：
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 分钟才解决。
A* pathfinding 是您最好的选择之一。它广泛用于需要在 2D 网格中找到 A 和 B 之间路径的游戏中。它使用启发式方法来识别有利的节点（如果需要，可以将它们称为像素）并因此获得良好的性能（尽管取决于您选择启发式函数的程度）。与任何 specific/heavily 优化算法相比，实施起来非常简单。此外还有各种可用的实现。
至于 "almost instantly" 速度，我怀疑仅靠算法无法达到。当需要这样的性能时，需要应用 domain-specific 修改。一种解决方案可能是 pre-compute 某些路径。这些路径可能表示单个节点到每个其他节点的完整映射（在您使用 5000x5000 网格的情况下，这是不切实际的）。或者 pre-computed 路径可以将网格中的节点块视为单个节点，即从 0..10,0..10 区域 x,y 到 10..20 区域 x,y 的任何移动,0..10 使用单个 pre-computed 路径。这可能不会为您提供最佳路径，但肯定会更快。与计算中的几乎所有事物一样，内存和速度之间始终存在 trade-off。
同样值得澄清的是，您问题中的"pixel"是否指的是汽车的单个移动单元。可能是面积是 5000x5000 但汽车实际上一次占据了 50 个像素。那么你可能会用一个节点代表50个像素来加速计算并获得更精确的结果。
我正在做一个研究项目，使用 raspberry pi 和激光雷达 2D 扫描仪定位遥控车。基本上，汽车将 运行 通过带有扫描仪的地点以获得该地点的 2D 表示，然后它将 return 到达起点。之后，您将能够 select 一个地方，它会在其中找到一条路径。由于我几乎是编程的初学者，所以在 1 个月内几乎不可能做到这一点，但我会尽力而为 :) 那么我现在想知道的是我应该使用哪种寻路算法？由于 2D 位置的分辨率约为 5000 x 5000 "pixels"，这将以厘米为单位表示位置，我相信我需要一个非常高效的分辨率。是否有任何特定算法可以在 raspberry pi 上以足够快的速度几乎立即完成工作？如果有，有没有高效的实现方式？
一些附加信息： 我使用的是“像素”二维数组，其中的值表示：
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 分钟才解决。
A* pathfinding 是您最好的选择之一。它广泛用于需要在 2D 网格中找到 A 和 B 之间路径的游戏中。它使用启发式方法来识别有利的节点（如果需要，可以将它们称为像素）并因此获得良好的性能（尽管取决于您选择启发式函数的程度）。与任何 specific/heavily 优化算法相比，实施起来非常简单。此外还有各种可用的实现。
至于 "almost instantly" 速度，我怀疑仅靠算法无法达到。当需要这样的性能时，需要应用 domain-specific 修改。一种解决方案可能是 pre-compute 某些路径。这些路径可能表示单个节点到每个其他节点的完整映射（在您使用 5000x5000 网格的情况下，这是不切实际的）。或者 pre-computed 路径可以将网格中的节点块视为单个节点，即从 0..10,0..10 区域 x,y 到 10..20 区域 x,y 的任何移动,0..10 使用单个 pre-computed 路径。这可能不会为您提供最佳路径，但肯定会更快。与计算中的几乎所有事物一样，内存和速度之间始终存在 trade-off。
同样值得澄清的是，您问题中的"pixel"是否指的是汽车的单个移动单元。可能是面积是 5000x5000 但汽车实际上一次占据了 50 个像素。那么你可能会用一个节点代表50个像素来加速计算并获得更精确的结果。