我正在开发一个类似于吃 bean 的游戏:考虑这个迷宫:
每个白色方块都是迷宫中的一个节点，其中位于 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 个)图形节点表示，每个节点表示处于特定 状态 的访问单元格。
也就是说，在您的示例中，您可能处于 P 表示的单元格中，处于两种状态之一:向左走时和向右走时。它们中的每一个都由一个单独的图形节点表示(尽管在空间上它是同一个单元格)。这两个节点之间也没有直接链接，因为您无法在此特定单元格中切换方向。
根据您的规则，您只能在遇到障碍物时切换方向，这是您在表示处于不同状态的同一单元格的节点之间放置链接的地方。
你也可以把你的图想象成你的迷宫复制成 4 层，每一层代表你吃 bean 的状态。在代表向右移动的图层中，您只将链接放在右侧，也可以是 w.r.t.到你迷宫的几何形状。在无法向右移动的带有障碍物的单元格中，您可以在不同层放置指向相同单元格的链接。
更新:
关于您在草图中描述的场景。它实际上是正确的，您的想法是正确的，但它看起来很复杂，因为您决定在不同的单元格和状态之间放置链接。
我建议下图:
这个想法是拆分您的单元间和州间链接。现在有 2 种边:inter-cell，用蓝色标记，和 inter-state，用红色标记。
蓝色边总是连接相邻单元格之间相同状态(箭头方向)的节点，而红色边连接同一单元格内的不同状态。
根据您的规则，在遇到障碍物的地方可能会发生状态变化，因此如果没有障碍物，则每个状态节点都是蓝色边缘的来源，如果遇到障碍物则是红色边缘(即不能发出蓝色边缘)。因此，我还用蓝色和红色绘制了状态节点。
如果根据你的规则状态转换立即发生，没有延迟/惩罚，那么红边的权重为 0。否则你可以为它们分配一个非零的权重，红/蓝边之间的权重比应该对应于转弯/旅行。
关于algorithm - 迷宫中的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46717482/