gpt4 book ai didi

algorithm - 迷宫中的最短路径

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:59:24 24 4
gpt4 key购买 nike

我正在开发一款类似于 Pacman 的游戏:考虑这个迷宫:

maze.

每个白色方 block 都是迷宫中的一个节点,其中位于 P 的对象(比如 X)正沿从右到左的方向向节点 A 移动。 X 不能切换到相反的方向,除非它遇到死胡同,例如 A。因此,连接 P 和 B 的最短路径通过 A,因为 X 不能将其方向反转到最右下角的节点(称为 C)。一个常见的 A* 算法会输出:

从P到B先向右,再向上;

这是错误的。所以我想:好吧,我可以在运行 A* 之前将 C 的 visited 属性设置为 true,让算法找到路径。显然这种方法对链接迷宫不起作用,除非我允许它重新发现一些节点(问题是:哪些节点?如何区分无用节点?)。我的第一个想法是:使用之前的方法始终跟踪最后访问的单元格;如果生成的路径不为空,则您已完成。否则,当你到达最后访问的死胡同时,说Y,(这一步之后是A*的失败)转到Y,然后使用标准A*到达目标(我' m 假设迷宫是连通的)。我的问题是:这是否保证始终有效?是否有更高效的算法,例如为此目的修改的 A* 派生算法?你会如何解决这个问题?我将不胜感激解释最佳和非最佳搜索技术的答案(实际上我不需要最短路径,稍长的路径是好的,但我很好奇是否存在像 Dijkstra 算法一样高效运行的最佳算法; 如果是,与非最优算法相比,它的运行时间是多少?)

编辑 对于 Valdo:我添加了 3 个单元格以概括一点:如果我明白了,请告诉我:

sketch.

最佳答案

好问题。我可以建议以下方法。

在有向图上使用 Dijkstra(或 A*)算法。迷宫中的每个单元格都应由多个(最多 4 个)图形节点表示,每个节点表示特定状态中的已访问单元格。

也就是说,在您的示例中,您可能处于 2 种状态之一的 P 表示的单元格中:向左走和向右走。它们中的每一个都由一个单独的图形节点表示(尽管在空间上它是同一个单元格)。这 2 个节点之间也没有直接链接,因为您无法在此特定单元格中切换方向。

根据您的规则,您只能在遇到障碍物时改变方向,这是您在表示不同状态的同一单元格的节点之间放置链接的地方。

您也可以将图形视为复制成 4 层的迷宫,每一层代表吃 bean 人的状态。在表示向右移动的层中,您只放置向右的链接,也 w.r.t.到你迷宫的几何形状。在无法向右移动的具有障碍物的单元格中,您将链接指向不同层的相同单元格。

更新:

关于您在草图中描述的场景。它实际上是正确的,你的想法是正确的,但它看起来很复杂,因为你决定在不同的单元格和状态之间放置链接。

我建议下图: Maze diagram

这个想法是拆分您的单元间和状态间链接。现在有两种边:单元间边,用蓝色标记,状态间边,用红色标记。

蓝色边总是连接相邻单元之间相同状态(箭头方向)的节点,而红色边连接同一单元内的不同状态。

根据您的规则,在遇到障碍物时可能会发生状态变化,因此如果没有障碍物,每个状态节点都是蓝色边缘的来源,如果遇到障碍物则为红色边缘(即不能发出蓝色边缘) .因此,我还将状态节点绘制为蓝色和红色。

如果根据你的规则状态转换立即发生,没有延迟/惩罚,那么红色边缘的权重为 0。否则你可以为它们分配一个非零权重,红色/蓝色边缘之间的权重比应该对应于时间转/行程周期比。

关于algorithm - 迷宫中的最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46717482/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com