检查移动是否有效的简单游戏算法
Simple game algorithm checking if the move is valid
我正在编写我的第一款游戏，还有最后一个问题要解决。我需要一种算法来检查我是否可以将选定的球移动到选定的位置。
看这张照片：
规则是，如果我拿起白色背景上的蓝色球（在最中间），我可以将它移到所有绿色区域，但我不能将它移到紫色区域，因为它们是有点被其他球围起来了。我自然不能把它移到其他球占的地方。小球只能上下左右移动
现在我知道有两种现有的算法：A* 和 Dijkstra 的算法可能会有帮助，但它们对于我需要的东西来说似乎太复杂了（都使用向量或我还没有教过的东西，我对编程很陌生，这是我的学期项目）。我不需要找到最短的路，我只需要知道选择的目的地是否被其他球围起来。
我在游戏中的棋盘是 9x9 阵列，如果它是空的地方，则简单地用 '/' 填充，如果它被占用，则用 7 个字母之一填充。
有什么方法可以简单地编写算法代码吗？
[我用了flood fill，效果很好，谢谢你的帮助，如果有人有类似的问题-我推荐使用flood fill，它非常简单快捷]
您可以使用 BFS(Breadth First Search) 算法非常简单地做到这一点。
为此你需要研究Graph 数据结构。一旦你理解它，实现起来非常简单。
关键思想
您的单元格将充当 顶点，而 边 将告诉您是否能够从一个单元格移动到另一个。
使用邻接列表或邻接矩阵表示法实现图形后，就可以开始使用BFS算法了做你想做的事。
我建议使用Flood fill算法：
Flood fill, also called seed fill, is an algorithm that determines the
area connected to a given node in a multi-dimensional array. It is
used in the "bucket" fill tool of paint programs to fill connected,
similarly-colored areas with a different color, and in games such as
Go and Minesweeper for determining which pieces are cleared. When
applied on an image to fill a particular bounded area with color, it
is also known as boundary fill.
就复杂时间而言，该算法将等于递归算法：O(N×M)，其中 N 和 M 是输入矩阵的维数。关键思想是在这两种算法中，每个节点最多处理一次。
在此 link 您可以找到算法实施指南。
更具体地说，正如 Martin Bonner 所建议的，实施有一些关键概念：
- 将所有空单元格标记为未知（所有完整单元格都不可访问）
- 将源单元格添加到一组可路由单元格中
- 虽然集合不为空：
- 从集合中弹出一个元素；
- 将所有相邻的未知单元格标记为"reachable"并将它们添加到集合中
- 所有剩余的未知单元格都无法访问。
PS：您可能想阅读 Flood fill vs DFS。
我正在编写我的第一款游戏，还有最后一个问题要解决。我需要一种算法来检查我是否可以将选定的球移动到选定的位置。
看这张照片：
规则是，如果我拿起白色背景上的蓝色球（在最中间），我可以将它移到所有绿色区域，但我不能将它移到紫色区域，因为它们是有点被其他球围起来了。我自然不能把它移到其他球占的地方。小球只能上下左右移动
现在我知道有两种现有的算法：A* 和 Dijkstra 的算法可能会有帮助，但它们对于我需要的东西来说似乎太复杂了（都使用向量或我还没有教过的东西，我对编程很陌生，这是我的学期项目）。我不需要找到最短的路，我只需要知道选择的目的地是否被其他球围起来。
我在游戏中的棋盘是 9x9 阵列，如果它是空的地方，则简单地用 '/' 填充，如果它被占用，则用 7 个字母之一填充。
有什么方法可以简单地编写算法代码吗？
[我用了flood fill，效果很好，谢谢你的帮助，如果有人有类似的问题-我推荐使用flood fill，它非常简单快捷]
您可以使用 BFS(Breadth First Search) 算法非常简单地做到这一点。
为此你需要研究Graph 数据结构。一旦你理解它，实现起来非常简单。
关键思想
您的单元格将充当 顶点，而 边 将告诉您是否能够从一个单元格移动到另一个。
使用邻接列表或邻接矩阵表示法实现图形后，就可以开始使用BFS算法了做你想做的事。
我建议使用Flood fill算法：
Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.
就复杂时间而言，该算法将等于递归算法：O(N×M)，其中 N 和 M 是输入矩阵的维数。关键思想是在这两种算法中，每个节点最多处理一次。
在此 link 您可以找到算法实施指南。
更具体地说，正如 Martin Bonner 所建议的，实施有一些关键概念：
- 将所有空单元格标记为未知（所有完整单元格都不可访问）
- 将源单元格添加到一组可路由单元格中
- 虽然集合不为空：
- 从集合中弹出一个元素；
- 将所有相邻的未知单元格标记为"reachable"并将它们添加到集合中
- 所有剩余的未知单元格都无法访问。
PS：您可能想阅读 Flood fill vs DFS。