查找最长路径网格

问题描述 投票:6回答:1

我正在使用仅允许在正交方向上移动的统一成本网格。这被用作游戏蛇的基础,在游戏蛇必须不断移动并尝试在棋盘上吃苹果。食物的位置和避免碰撞是使用经典的AStar算法完成的,以找到蛇头和食物之间的最短路径。但是,这种方法有时会导致蛇去觅食,从而使蛇没有通往下一个食物的明确路径。这条蛇最终被卡在一个不规则形状的矩形中,目前还没有进一步的模拟。

我的问题是:有没有办法找到不规则矩形内最长的移动链,以便保持最长的生命,并可能使蛇的尾巴停止阻塞通往下一个食物的路径?我已经看过汉密尔顿算法来尝试访问所有节点,但是似乎没有解决不规则形状的方法。解决方案不一定是完美的,但应始终尝试使蛇有最大机会从陷阱中逃脱。

有什么想法吗?

algorithm hamiltonian-cycle
1个回答
0
投票

board [] [](让我们将板视为2D数组)

现在标记板[i] [j] ='S'表示蛇所占据的细胞

标记板[i] [j] =''(空闲单元格的空白)

现在您的A *应该给您一条从蛇头到食物的路径。将此路径中的所有单元格标记为“#”。 (可选:取消标记从蛇尾开始的n-1个“ S”细胞的数量,其中n是从蛇头到食物的最短路径。这是因为经过n步,蛇尾也会移动)

现在为所有将来的职位(在木板上随机抽取10个空白点),看看您是否可以仅使用空白的空间单元从食物位置到达所有这些职位。 (您可以在单个DFS中执行此操作)。如果您可以访问,则可以安全使用所选的路径。否则,请采用其他路径。

© www.soinside.com 2019 - 2024. All rights reserved.