我正在编写我的第一款游戏,还有最后一个问题需要解决。我需要一种算法来检查我是否可以将选定的球移动到选定的位置。
看这张照片:
规则是,如果我拿起白色背景上的蓝色球(在最中间),我可以将它移到所有绿色区域,但我不能将它移到紫色区域,因为它们有点像被其他球围起来。我自然不能把它移到其他球占的地方。球只能上下左右移动。
现在我知道已经存在两种算法:A* 和 Dijkstra 的算法可能会有帮助,但它们似乎对我需要的东西来说太复杂了(两者都使用 vector 或我还没有教过的东西,我'我对编程很陌生,这是我的学期项目)。我不需要找到最短的路,我只需要知道选择的目的地是否被其他球围起来。
我在游戏中的棋盘是 9x9 阵列,如果它是空的地方,则简单地用 '/' 填充,如果它被占用,则用 7 个字母之一填充。
有没有一种方法可以用简单的方式编写算法代码?
[我选择了 flood fill,它工作得很好,感谢你的所有帮助,如果有人有类似的问题 - 我推荐使用 flood fill,它真的很简单和快速]
最佳答案
我建议使用 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 所建议的,实现有一些关键概念:
- 将所有空单元格标记为未知(所有完整单元格都不可访问)
- 将源单元添加到一组可路由单元
- 当集合不为空时:
- 从集合中弹出一个元素;
- 将所有相邻的未知单元标记为“可达”并将它们添加到集合中
- 所有剩余的未知单元格都无法访问。
PS:您可能想阅读 Flood fill vs DFS .
关于c++ - 检查移动是否有效的简单游戏算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45977361/