如何使用以下地图的A *

Question

我正在使用ROS和C ++开发机器人模拟。

我创建了一张地图，这是一个封闭的房间中的免费位置列表，如下所示：

0.1,0;0.2,0;0.3,0;...

它们是由;分隔的（x，y）位置。该列表中的所有位置都是地图中的空闲位置。如果某个位置有障碍物，该位置将不在列表中。

如何将该列表用作A *搜索算法的地图？

我曾想过将该列表转换为2D矩阵，但我不知道在矩阵的单元格中放入什么。

Answer 1

实际上，听起来你可以简单地通过解析文本文件将列表转换为2D矩阵（将x设置为逗号前的字符序列，跳过逗号，将y设置为分号前的字符序列，跳过分号，将x / y转换为数字和相应的更新矩阵使用x / y作为索引等）。

至于矩阵本身，只考虑房间的鸟瞰图，其中单元格中的“0”表示自由空间，而“1”表示障碍物（或者反过来;值是任意的） ，只要你一直使用它们）。对于A *算法，任何单元基本上与4个相邻单元（或您正在使用的任何移动方案）“相邻”。

Answer 2

您必须将数据转换为图形（如在节点和边缘中，而不是在函数图中）。为了做到这一点，你不仅需要转换为节点（a.k.a.顶点）而是边缘的位置。当您可以从一个节点直接移动到另一个节点时，两个节点之间存在边缘。换句话说，两者之间没有节点，也没有妨碍移动的障碍。将该部分放下后，可以轻松地在结果图上运行A *算法。

脚步：

1. 读取并解析输入数据。
2. 将数据存储为节点列表。
3. 定义两个节点之间存在边缘的要求。
4. 创建具有先前定义的条件和节点的边列表。
5. 在图表上运行A *。

笔记：

• 我不会为你做实际的工作，因为我猜它只是功课。这里没有人希望这样做。
• 您可以单独解决每个步骤，甚至可以跳过它并使用硬编码值替换其结果。
• 您也可以跳过完全生成边缘。您只需调整A *算法即可在其访问的每个节点上按需生成边缘。这可能会也可能不会更简单。