寻找最长路径网格

Question

我正在使用一个仅允许直角方向移动的统一费用网格，并将其用作贪吃蛇游戏的基础，贪吃蛇必须不断移动并尝试在棋盘上吃苹果。食物的位置和碰撞避免是使用经典的AStar算法来找到蛇头和食物之间的最短路径完成的。然而，这种方法有时会导致蛇去吃食物，从而导致它没有清晰的下一个食物路径。蛇最终被困在一个不规则形状的矩形中，在这一点上已经没有未来的模拟了。

我的问题是：是否有一种方法可以找到不规则矩形内最长的移动链，以便尽可能长时间地存活，并可能使蛇的尾部停止阻挡通往下一个食物的路径？我已经查看了哈密顿算法以尝试访问所有节点，但似乎对于不规则形状没有解决方案。解决方案不需要完美，但它应该始终尝试为蛇提供逃脱陷阱的最佳机会。

您有什么想法吗？

- Cobey Hollier

Answer 1

board[][]（假设board是一个二维数组）

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

对于空闲单元格，将board[i][j] = ' '（空格）

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

现在对于所有未来的位置（在板子上随机选择10个空白点），看看是否可以仅使用空白单元格从食物位置到达所有这些位置（您可以在单个DFS中完成此操作）。如果您能够访问，则可以安全地使用您选择的路径。否则，请选择其他路径。

- cegprakash