简单的游戏算法检查移动是否有效

Question

我正在编写我的第一个游戏,我还有最后一个问题需要解决.我需要一个算法来检查我是否可以将选定的球移动到选定的位置.

看这张图片:

规则是,如果我在白色背景上拾取蓝色球(在正中间),我可以将它移动到所有绿色空间,我无法将其移动到紫色球,因为它们被其他人围起来球.我自然不能把它移到其他球的地方.球只能向上,向下,向左和向右移动.

现在我知道有两个已经存在的算法:A*和Dijkstra的算法可能会有所帮助,但它们看起来太复杂了我需要的东西(都使用我没有教过的矢量或东西,我很新编程,这是我的学期项目).我不需要找到最短路,我只需要知道所选目的地是否被其他球围起来.

我在游戏中的主板是9x9阵列,如果它是一个空的地方,只需填充'/',如果它被采取,则为7个字母中的一个.

有没有办法可以用简单的方法编写算法代码？

---

[我去了洪水填充,它工作得很好,谢谢你的帮助,如果有人有类似的问题 - 我建议使用洪水填充,它真的很简单快捷]

Answer 1

我建议使用Flood填充算法:

洪水填充(也称为种子填充)是一种算法,用于确定连接到多维数组中给定节点的区域.它被用在油漆程序的"桶"填充工具中,用于填充具有不同颜色的连接的,颜色相似的区域,并且在诸如Go和Minesweeper之类的游戏中用于确定哪些块被清除.当应用于图像以用颜色填充特定的有界区域时,它也被称为边界填充.

就复杂性时间而言,该算法将等于递归的算法:O(N×M)其中N和M是输入矩阵的维数.关键的想法是,在两种算法中,每个节点最多只处理一次.

在此链接中,您可以找到算法实施的指南.

更具体地说,正如Martin Bonner所说,实施有一些关键概念:

1. 将所有空单元标记为未知(所有完整单元格都无法访问)
2. 将源单元添加到一组可路由单元
3. 虽然该集合不为空:
   • 弹出集合中的元素;
   • 将所有相邻的未知单元格标记为"可达"并将它们添加到集合中
4. 所有剩余的未知单元都无法访问.

PS:您可能想要阅读Flood填充与DFS.