# 如何用迷宫位图数组生成有向图规划路径

> 原文链接：https://robotics.hellobike.com/pitfalls/2015-06-22-robotics-se-7438
> 频道：pitfalls | 更新日期：2015-06-22 | 标签：auto, stackexchange, arduino, mobile-robot, localization, mapping
> 核心摘要：将可通行位图转为邻接矩阵，再用 Dykstra 算法求最短路径和路点。

# 如何用迷宫位图数组生成有向图规划路径

::: v-pre
> 本文由 AI 根据公开内容整理，可能有误，请以原文为准：[How to make a directed graph?](https://robotics.stackexchange.com/questions/7438/how-to-make-a-directed-graph)（Robotics Stack Exchange #7438）

**状态**：已解决

## 问题

提问者已有迷宫单色位图并读成二维 bit 数组，但不知道如何基于该数组为机器人规划穿越迷宫、避障的路径。

## 环境

单色迷宫位图；示例尺寸 `64x96`，`N=6144`；提到 Matlab 线性索引和 C++ `sub2ind` 实现。

## 解决办法

1. 将地图中可通行位置记为 `1`、墙记为 `0`，按规则为每个格点分配线性索引。
2. 建立大小为 `N x N` 的 `Digraph` 邻接矩阵，遍历每个格点并检查左、右、上、下邻居是否存在且可通行。
3. 若当前点与邻居都可通行，则令 `Digraph(currentPos,destPos)=1`，否则为 `0`。
4. 为相邻点设置距离，并用 `Dykstra` 算法从图中求起点到终点的最短路径，输出总距离和逐邻居路点。

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

## 原始参考来源 (Sources)

- [Robotics Stack Exchange #7438：How to make a directed graph?](https://robotics.stackexchange.com/questions/7438/how-to-make-a-directed-graph)