迷宫中的最短路径
Shortest path in a maze
我正在开发一款类似于 Pacman 的游戏：考虑这个迷宫：
每个白色方块都是迷宫中的一个节点，其中位于 P 的对象（比如 X）正在从右到左的方向向节点 A 移动。 X 不能切换到相反的方向，除非它遇到死胡同，例如 A。因此，连接 P 和 B 的最短路径通过 A，因为 X 不能将其方向反转到最右下角的节点（称为 C）。常见的 A* 算法会输出：
从P到B先向右，再向上；
这是错误的。所以我想：好吧，我可以在 运行 A* 之前将 C 的 visited 属性设置为 true，让算法找到路径。显然这种方法对链接迷宫不起作用，除非我允许它重新发现一些节点（问题是：哪些节点？如何区分无用节点？）。我的第一个想法是：使用之前的方法始终跟踪最后访问的单元格；如果生成的路径不为空，则您已完成。否则，当你走到最后访问的死胡同时，说Y，（这一步后面是A*的失败）转到Y，然后使用标准A*到达目标（我'假设迷宫是相连的）。我的问题是：这是否保证始终有效？是否有更高效的算法，例如为此目的修改的 A* 派生算法？你会如何解决这个问题？我将不胜感激解释最佳和非最佳搜索技术的答案（实际上我不需要最短路径，稍长的路径是好的，但我很好奇这样的最佳算法 运行 是否有效因为 Dijkstra 算法存在；如果存在，与非最优算法相比，它的 运行 时间是多少？）
编辑 对于 Valdo：我添加了 3 个单元格以便概括一点：如果我明白了，请告诉我：
好问题。我可以建议以下方法。
在有向图上使用 Dijkstra（或 A*）算法。迷宫中的每个单元格应由 多个 （最多 4 个）图形节点表示，每个节点表示特定 状态 中的访问单元格。
也就是说，在您的示例中，您可能处于 2 种状态之一的 P 表示的单元格中：向左走和向右走。它们中的每一个都由一个单独的图形节点表示（尽管在空间上它是同一个单元格）。这 2 个节点之间也没有直接 link，因为您无法在此特定单元格中切换方向。
根据你的规则，你只能在遇到障碍物时改变方向，这是你在节点之间放置 links 表示不同状态的相同单元格。
您也可以将图表想象成复制成 4 层的迷宫，每一层代表吃豆人的状态。在表示向右移动的层中，您只向右放置 links，还有 w.r.t。到你迷宫的几何形状。在有障碍物且无法向右移动的单元格中，您将 links 放入不同层的相同单元格。
更新：
关于您在草图中描述的场景。它实际上是正确的，你的想法是正确的，但它看起来很复杂，因为你决定在不同的单元格和状态之间放置 links。
我建议下图：
我们的想法是拆分您的单元间和状态间 link。现在有两种边：细胞间，用蓝色标记，状态间，用红色标记。
蓝色边始终连接相邻单元格之间相同状态（箭头方向）的节点，而红色边连接同一单元格内的不同状态。
根据您的规则，遇到障碍物时可能会发生状态变化，因此如果没有障碍物，每个状态节点都是蓝色边缘的来源，如果遇到障碍物则为红色边缘（即不能发出蓝色边缘）边缘）。因此我也把状态节点涂成蓝色和红色。
如果根据你的规则状态转换立即发生，没有 delay/penalty，那么红色边的权重为 0。否则你可以为它们分配一个非零权重，权重比 red/blue edges应该对应turn/travel.
的时间段比例
我正在开发一款类似于 Pacman 的游戏：考虑这个迷宫：
每个白色方块都是迷宫中的一个节点，其中位于 P 的对象（比如 X）正在从右到左的方向向节点 A 移动。 X 不能切换到相反的方向，除非它遇到死胡同，例如 A。因此，连接 P 和 B 的最短路径通过 A，因为 X 不能将其方向反转到最右下角的节点（称为 C）。常见的 A* 算法会输出：
从P到B先向右，再向上；
这是错误的。所以我想：好吧，我可以在 运行 A* 之前将 C 的 visited 属性设置为 true，让算法找到路径。显然这种方法对链接迷宫不起作用，除非我允许它重新发现一些节点（问题是：哪些节点？如何区分无用节点？）。我的第一个想法是：使用之前的方法始终跟踪最后访问的单元格；如果生成的路径不为空，则您已完成。否则，当你走到最后访问的死胡同时，说Y，（这一步后面是A*的失败）转到Y，然后使用标准A*到达目标（我'假设迷宫是相连的）。我的问题是：这是否保证始终有效？是否有更高效的算法，例如为此目的修改的 A* 派生算法？你会如何解决这个问题？我将不胜感激解释最佳和非最佳搜索技术的答案（实际上我不需要最短路径，稍长的路径是好的，但我很好奇这样的最佳算法 运行 是否有效因为 Dijkstra 算法存在；如果存在，与非最优算法相比，它的 运行 时间是多少？）
编辑 对于 Valdo：我添加了 3 个单元格以便概括一点：如果我明白了，请告诉我：
好问题。我可以建议以下方法。
在有向图上使用 Dijkstra（或 A*）算法。迷宫中的每个单元格应由 多个 （最多 4 个）图形节点表示，每个节点表示特定 状态 中的访问单元格。
也就是说，在您的示例中，您可能处于 2 种状态之一的 P 表示的单元格中：向左走和向右走。它们中的每一个都由一个单独的图形节点表示（尽管在空间上它是同一个单元格）。这 2 个节点之间也没有直接 link，因为您无法在此特定单元格中切换方向。
根据你的规则，你只能在遇到障碍物时改变方向，这是你在节点之间放置 links 表示不同状态的相同单元格。
您也可以将图表想象成复制成 4 层的迷宫，每一层代表吃豆人的状态。在表示向右移动的层中，您只向右放置 links，还有 w.r.t。到你迷宫的几何形状。在有障碍物且无法向右移动的单元格中，您将 links 放入不同层的相同单元格。
更新：
关于您在草图中描述的场景。它实际上是正确的，你的想法是正确的，但它看起来很复杂，因为你决定在不同的单元格和状态之间放置 links。
我建议下图：
我们的想法是拆分您的单元间和状态间 link。现在有两种边：细胞间，用蓝色标记，状态间，用红色标记。
蓝色边始终连接相邻单元格之间相同状态（箭头方向）的节点，而红色边连接同一单元格内的不同状态。
根据您的规则，遇到障碍物时可能会发生状态变化，因此如果没有障碍物，每个状态节点都是蓝色边缘的来源，如果遇到障碍物则为红色边缘（即不能发出蓝色边缘）边缘）。因此我也把状态节点涂成蓝色和红色。
如果根据你的规则状态转换立即发生，没有 delay/penalty，那么红色边的权重为 0。否则你可以为它们分配一个非零权重，权重比 red/blue edges应该对应turn/travel.
的时间段比例