大家应该都玩过连连看, 游戏规则不多说了, 我们先看看设计思路.
第一件事要根据游戏玩法确定程序的数据结构, 不同的数据结构决定了不同的算法设计, 用错了数据结构可能直接让代码复杂好几倍.
下面是小编整理好的一套 C/C++ 资料, 加小编 C/C++ 编程学习群 825414254, 获取系统性学习 C/C++ 的学习资料
QQ 截图 20190309205647.jpg
连连看中玩家操作的数据是一个个的图片, 多个图片组成一个棋盘式的矩阵界面. 程序根据玩家的点击位置计算两个图片的连接路线, 这要求程序以最快, 最简单的方式获得矩阵中每个格子的数据.
用二维数组表示游戏中的矩阵界面比较合适, 因为数组可以通过索引快速访问数据, 二维数组的两个索引刚好对应矩阵界面的 (x, y) 坐标. 例如:
image.PNG
图中矩阵数据在代码中应该这样表示:
image.PNG
可以用不同的数字代表不同的图片, 比如:
image.PNG
那么上面的矩阵绘制的时候就会是这样:
image.PNG
0 表示空格, 不显示图片. 初始化时的空格或消除后的空格, 都会被设置为 0.
image.PNG
接下来要初始化数据, 我打算用 8 种不一样的图片, 每种 6 张, 随机放入矩阵中, 矩阵最外一圈是空的. 这个算法可以用标准库函数 std::random_shuffle 来完成. std::random_shuffle 用于把容器内的数据随机打乱, 因此按顺序把数据放入数组中, 然后调用 std::random_shuffle 就可以完成初始化.
image.PNG
断点运行观察数组数据, 和我们设计的一样:
image.PNG
贴上图片看起来还不错:
image.PNG
现在来分析游戏玩法. 这个游戏的难点是两个图片连接的判定算法, 要求连接线只能转折两次.
我的第一反应这是一个寻路算法, 要求找到转折两次以下的最短路径. 教科书上常见的广度优先搜索, 深度优先搜索, DijKstra 算法或是游戏中常用的 A 星算法, 稍作修改加上两次转折的限制都能解决这个问题.
但是如果我用这些比较复杂的算法来教新手, 显然是在劝退. 所以还是考虑找一找连线判定的算法有没有简单的规律.
多玩几次游戏, 把不同种类的连线记录下来, 总结后可以发现总共有 3 种连线类型, 分别是不转折连接, 转折一次和转折两次.
还是从最简单的情况开始考虑. 这是解决难题的通用方法: 从最简单的情况开始考虑, 再逐步增加复杂的条件.
最简单的不转折连接, 有两种情况, 横向连线和纵向连线:
image.PNG
这两种情况很容易处理, 横向, 竖向依次检查每个格子是否被阻挡即可.
image.PNG
最后把这两个合并就是不转折的情况下:
image.PNG
转折一次:
image.PNG
转折一次的算法也是比较明显的, 像上图中的两种情况, 找到绿色点的位置, 如果这个点可以不转折连到两个红色的图片, 那么这两个红色的图片就可以通过一次转折连接.
绿点的位置是由两个红点决定的, 只有上图中的两种可能.
image.PNG
转折两次的情况就多了, 下图同样是连接红色图片, 要绕过绿色图片.
image.PNG
转折两次的情况很多, 这里无法一一列举, 但是仔细思考可以发现和转折一次本质上是一样的, 就是找到两个点, 这两个点可以分别和红色图片无转折连接, 并且这两个点也可以无转折连接.
这两个点需要位于经过红色图片的十字线上, 并且只要确定一个了其中一个点, 就能对应地找到另一个点:
image.PNG
因此只要遍历其中一个图片的两条十字线经过的所有的点, 并计算出另一个图片十字线上对应点的位置, 检查这两个点和两个红色图片是否可以无转折连接:
image.PNG
代码码完了, 添上图片和鼠标检测的代码跑一跑试试.
image.PNG
右边显示临时显示字符用于测试连通性, 多次测试没有问题.
最后加上连线, 并清除被点击的两个格子, 就完成了连连看的核心逻辑:
image.PNG
来源: http://www.jianshu.com/p/26845519c113