6

我正在使用一个统一的成本网格，它只允许在正交方向上移动。这被用作游戏蛇的基地，蛇必须不断移动并尝试吃板上的苹果。食物的定位和防撞是使用经典的 AStar 算法完成的，以找到蛇头和食物之间的最短路径。然而，这种方法有时会导致蛇去寻找食物，导致它没有明确的路径去下一个食物。蛇最终卡在一个不规则形状的矩形中，此时没有未来的模拟。

我的问题是：有没有办法在不规则矩形内找到最长的移动链，以便最长地存活，并可能让蛇的尾巴停止阻挡通往下一个食物的路径？我查看了 Hamilton Algorithms 以尝试访问所有节点，但似乎没有针对不规则形状的解决方案。解决方案不一定是完美的，但它应该始终尝试让蛇有最好的机会从陷阱中逃脱。

有什么想法吗？

4

1 回答 1

0

board[][] （让我们将 board 视为 2D 数组）

现在为你的蛇占据的单元格标记 board[i][j] = 'S'

为空闲单元格标记 board[i][j] = ' ' (空白空间)

现在你的 A* 应该给你一条从蛇头到食物的路径。将此路径中的所有单元格标记为“#”。（可选：从蛇尾取消标记 n-1 个“S”细胞，其中 n 是从蛇头到食物的最短路径。这是因为经过 n 步后，蛇的尾巴也会移动）

现在对于所有未来的位置（在棋盘上随机取 10 个空点），看看你是否可以仅使用空白单元格从食物位置到达所有这些位置。（您可以在单个 DFS 中执行此操作）。如果您能够访问，那么使用您选择的路径是安全的。否则，走另一条路。

于 2019-02-05T09:27:06.833 回答