# 未知障碍网格如何高效遍历所有可达格

> 原文链接：https://robotics.hellobike.com/pitfalls/2019-01-12-robotics-se-952
> 频道：pitfalls | 更新日期：2019-01-12 | 标签：auto, stackexchange, algorithm, coverage, planning
> 核心摘要：用迭代式 Flood Fill，并用 A* 在已访问格子中移动到栈中下一个位置。

# 未知障碍网格如何高效遍历所有可达格

::: v-pre
> 本文由 AI 根据公开内容整理，可能有误，请以原文为准：[What's an efficient way to visit every reachable space on a grid with unknown obstacles?](https://robotics.stackexchange.com/questions/952/whats-an-efficient-way-to-visit-every-reachable-space-on-a-grid-with-unknown-ob)（Robotics Stack Exchange #952）

**状态**：已解决

## 问题

在未知障碍的粗粒度二维网格中，需要访问所有可达格并建图；障碍只能通过尝试移动失败来发现。提问者担心 DFS 回溯过多，效率过低。

## 环境

Linux / ROS 机器人软件与控制通用开发环境

## 解决办法

1. 采用 Flood Fill 思路遍历可达网格。
2. 使用基于栈的迭代实现，而不是递归实现。
3. 对物理移动做适配：从当前位置到栈中下一个位置时，用 A* 搜索路径。
4. A* 只使用已经访问过的网格，因为这些格子之间保证存在路径。

原问题作者：Ian；采纳答案作者：Ian。原内容依 CC BY-SA 4.0 授权，本页摘要同样依 CC BY-SA 4.0 授权。
:::

## 原始参考来源 (Sources)

- [Robotics Stack Exchange #952：What's an efficient way to visit every reachable space on a grid with unknown obstacles?](https://robotics.stackexchange.com/questions/952/whats-an-efficient-way-to-visit-every-reachable-space-on-a-grid-with-unknown-ob)