DOI:10.16707/j.cnki.fjpc.2019.01.008 福 建 电 脑 福 建 电 脑 福 建 电 脑 UJIANCOMPUTER UJIANCOMPUTER UJIANCOMPUTER F F F 基于深度优先搜索的连连看游戏路径查找算法 黎利辉 （广西民族师范学院 广西 崇左 ） 532200 【摘 要】 针对目前连连看游戏路径查找算法不够精练的问题 ，基于深度优先搜索和栈的思想 ，设计了一个全新的路 径查找算法 。有别于其它查找路径与记录路径轨迹需要分两步进行的算法 本算法判断两个点之间如果存在路径 ，则同时 , 会记录有效路径的轨迹 。 本算法向东南西北四个方向递归探测路径时 ，各方向的探测原理是一样的 ，故算法非常精练 。 同 时还设计了布局算法 、死局判断算法和游戏提示算法 、重排算法 ，故这是一套非常完备的连连看游戏算法 ，具有很强的实 际应用价值 。 【关键词】 连连看游戏 ；路径 ；深度优先搜索 ；栈 ；轨迹 0.引言 然后循环判断这些公共列在垂直方向能否连通 ，如 果 能 够 连 通 连连看游戏的游戏界面是一个由许多带有图像的小方块组 就代表存在有效路径 。 在垂直方面的判断跟水平方向的判断一 成的大矩形 所有小方块对象必须成对出现 ，选择两个图像相同 样 。 但这些文献提到的算法在判断是否存在路径时 ，没 有 同 时 , 的小方块对象 如果它们可以被三条以内的水平或者垂直线段 求出具体的路径轨迹 。 部分文献基于广度优先的思想设计出一 , 连接 ，并且在这些线段经过的路径上不存在图像小方块 那么 自 种连连看路径判断算法 ，以求最小转弯数是否小于 或 等 于 作 , 2 动消去这两个对象 在规定的时间段内 ，重复这个过程 直到界面 为 搜 索 目 标 ， 将 查 找 两 点 间 路 径 的 问 题 转 化 为 一 个 最 优 化 问 , , 上的所有对象都被消去 ， 则游戏进入下一关 。 如果在玩的过程 题 。 同样这类算法判断是否存在路径和求取具体路径轨迹是分 中 ，任意的一对同类型图片都不存在有效路径 ，则自动重排剩余 两步进行的 。 本文基于深度优先和栈的思想 ，设计 的 算 法 可 以 的图片 ，并保证至少有部分成对同类型图片存在有效路径 。 目 在 判 断 是 否 存 在 有 效 路 径 时 ，顺 便 求 出 具 体 路 径 轨 迹 ，具 体 算 [1] 前连连看游戏与具体的某一领域的知识相结合 ， 成为了一类集 法如第 节所示 。 2 益智与休闲于一体的游戏 。 如文献 ［ ］、文献 ［ ］和文献 ［ ］均为 2 3 4 2.核心算法分析 连连看游戏的基本思想与各自领域相结合的经典应用 。 游戏初始化算法 2.1 1.相关工作及存在的问题 当游戏界面为矩形时 ，不论游戏界面的水 平 方 向 与 垂 直 方 目前对连连看游戏的研究主要集中在布局 算 法 ，路 径 判 断 向 上 元 素 的 个 数 是 多 少 ，只 要 元 素 总 个 数 为 偶 数 ，就 不 影 响 游 算法 ，死局判断算法 ，死局后的重新布局算法等几个方面 。 其中 戏的核心算法 。 假设游戏的界面上包括 个图标 ，排列成 100 10 路径判断是研究的重点 ，因为其它三个算法一般需 要 用 到 路 径 行 列 ，按 游 戏 规 则 ，在 游 戏 界 面 的 外 围 存 在 通 路 ，故 定 义 一 10 判 断 算 法 。 很 多 论 文 并 没 有 全 面 介 绍 连 连 看 游 戏 的 一 整 套 算 个 行 列的二维数组 ， 数 组 元 素 的 值 为 代 表 游 戏 12 12 board 0 法 ，文献 ［ ］对这个游戏的算法介绍得比较全面 ，但 是 也 没 有 说 界面的对应位置上没有图标 ，数组元素的值为 分别代表 游 5 1-8 明死局后的重新布局算法 ， 并且文献中的布局算法 存 在 漏 洞 ， 戏界面上的八种图案 。 本文算法用 语言 实现 ，数组的下标 Java 它只 考虑了图片需要成对出现这一方面 ，而没有解决 即 使 图 片 从 开始 ，下标为 的行与下标为 的行 ，全部赋值为 ，下标 0 0 11 0 均 是 成 对 出 现 的 布 局 也 可 能 是 死 局 的 这 一 问 题 ，文 献 ［ ］介 绍 为 的 列 与 下 标 为 的 列 ，全 部 赋 值 为 ，代 表 游 戏 界 面 的 外 6 0 11 0 的布局 算法规定每一类图片出现的次数是相同的 ，但 是 同 样 没 围可以存在通路 。 二维数组中下标从 到 的行 ，以及下标从 1 10 有解决开局即为死局的问题 。 本文在第 小节介绍的游戏初 到 的列 ，共 个元素代表界面上的 个图标 。 赋值算 2.1 1 10 100 100 始化算法 ，综合考虑了图片成对出现与避免死局这两个方面 。 法要考虑以下三个因素 ：代表游戏图标类型的元素 值 应 当 是 成 在 路 径 判 断 方 面 现 在 出 现 了 几 种 典 型 的 算 法 ，文 献 ［ ］中 对 出 现 ；每 个 元 素 的 值 要 随 机 出 现 ；生 成 的 游 戏 布 局 应 当 避 免 5 的 路 径 判 断 算 法 分 为 直 接 连 接 情 形 、一 个 拐 点 情 形 、在 边 界 侧 死局 。 具体算法如下 ： 面的两个 拐点情形 、在游戏盘面内部两个拐点情形这 四 种 可 能 第 步 ： 给长度为 个元素的临时一维数组 赋 1 100 tempArr 性 ，游戏算法不够精练 ，通过算法判断两个点是否存在 路 径 时 ， 值 。循环五十次 ，循环的第 次 ，生成一个值为 的随机数 ，将 i 1-8 不能同时获得具体的路径轨迹 。 部分网络文献上介绍了一种比 这个随机数存放在下标为 和 的这两个位置上 。 通过 2*i 2*i+1 较 精 巧 的 判 断 是 否 存 在 路 径 的 算 法 ：从 水 平 方 向 ，以 第 一 个 点 这一步即保证数组元素是随机的又是成对出现的 。 为中心 ，向左右延伸 ，以一维数组 记录它能到达的空白列 ；同 第 步 ：将 里的值随机打乱顺序 。 循环多次 ，每次 A 2 tempArr 样在 水平方向 ，以第二个点 为 中 心 ，向 左 右 延 伸 ，以 一 维 数 组 循环随机选择两个数组元素 ，并将这两个元素的值交换 。 B 记录它能到达的空白列 ，然后在这两个一维数组中 找 两 个 点 在 第 步 ：将一维数组的值从前往后 ，移到二维数组 上 3 board 水平方向上能到达的公共列 ， 把公共列记录在一维数组 里 ， 去 。 C 基金项目： 2016 年度广西高校中青年教师基础能力提升项目（KY2016YB516） 广西民族师范学院中青年骨干教师科研启动项目（2016ZQGG002）， 广西民族师范学院科研项目（SXYB2014003,SXZD2016002）。 16· · 福 建 电 脑 福 建 电 脑 2019 年第 1 期 2019 年第 1 期 

福 建 电 脑 福 建 电 脑 福 建 电 脑 UJIANCOMPUTER UJIANCOMPUTER UJIANCOMPUTER F F F 第 步 ： 判断通过以上三步生成的游戏局 面 是 否 是 死 局 ？ 当 前 点 进 入 方 向 4 if(dir == EAST || dir == NO_DIR ){// 如 果 不 是 死 局 ，游 戏 初 始 化 算 法 结 束 ，如 果 是 死 局 ，跳 转 到 第 向东 ，或无方向 1 步继续 。 findPath(row,col+1,EAST,corners); 2.2 }else if ((dir == NORTH || dir == SOUTH) && cor鄄 有效路径查找算法 这一部分是整个游戏的核心 ，本节算法基 于 深 度 优 先 的 思 ners<=1){ 想 ，用递归的机制 ，从第一个点向东南西北四个方向进 行 探 测 ， findPath(row,col+1,EAST,corners+1); 直到到达第二个点为止 。 先设五个变量 、 、 、 EAST SOUTH WEST } NORTH NO_DIR } 、 分别代表每个点的进 入 方 向 ：东 、南 、西 、北 和 无方向 ，通过探测路径上临近两点的进入方向来 判断 临 近 两 点 向西 、南 、北探测的代码与向东探测的代码类似 ，省略 // 间是否转弯 。 定义四个变量 ， ， ， 分别记录起始 四个方向探测都没有找到路径 row1 col1 row2 col2 if(! hasPath) // 点的行坐标 、起始点的列坐标 、终止点的行坐标 、终止 点 的 列 坐 stack.pop(); 标 。 设一个全局开关变量 ， 记录是否找到有效路径 ，构 hasPath } 建一个全局的栈 ，用来保存路径上各个点的轨迹 。 因为用 stack } 递 归 机 制 向 东 南 西 北 四 个 方 向 进 行 探 测 时 ， 每 个 方 向 是 对 等 以 上 方 法 的 形 参 和 代 表 当 前 点 的 行 坐 标 与 列 坐 row col 的 。 现在以向东为例进行说明 。 标 ， 代表当前点的进入方 向 ， 代 表 探 测 过 程 中 已 经 经 dir corners 探测到当前点时 ，将当前点进栈 。 历过的转弯数 。 该方法在 初次调用前 ，需要将终点的 元 素 值 设 如果当前点为终止点 ，开关变量 设置为真 ，代表 路 置为 ，否则不可能探测到终点 ，因为算法中规定只有下一个探 hasPath 0 径已经找到 ，提前终止本次递归 。 当前点不是终止 点 但 满 足 下 测 点 上 没 有 图 标 时 才 继 续 递 归 探 测 ，如 果 没 有 路 径 ，则 将 终 点 面 四 个 条 件 时 ，分 两 种 情 况 进 行 讨 论 ：继 续 向 东 探 测 时 没 有 超 的元素值恢复为原值即可 。 起点没有进入方向 ，故 初 次 调 用 方 出边界 ；当前结点东边的临近点没有图标 ；有效路径没 有 找 到 ； 式为 ： 。 调用本方法之 前 要 将 存 储 findPath(row1,col1,NO_DIR,0) 当前点的进入方 向不是向西 （如果当前点是通过向西 的 方 向 进 路径轨迹的栈 清空 ，注意 ：如果从起点到终点之间存 在 路 stack 入 的 ，接 下 来 又 向 东 去 探 测 ，则 整 个 探 测 过 程 有 可 能 在 邻 近 的 径 ，则 里保存的路径轨迹是从终点开始到起点结束的 。 stack 两个点上不断往返 ）。 死局判断算法与游戏提示算法 2.3 （ ）如 果 当 前 点 的 进 入 方 向 为 “向 东 ”，或 者 当 前 点 是 起 始 当游戏界面上没有一对有效路径时 ， 该局 面 即 为 死 局 ，死 1 点 无 进 入 方 向 ，下 次 向 东 探 测 时 ，以 转 弯 数 不 变 、行 不 变 ，列 值 局判断算法和游戏提示算法其实是同一个算法 ，具体算法为 ： 加 ，方向为 “向东 ”的方式 ，往下层递归 。 用一个双重循环 ，遍历游戏面板二维数组 上 的 每 一 个 非 零 1 （ ）如 果 当 前 点 的 进 入 方 向 为 向 北 或 者 向 南 ，且 当 前 转 弯 元素 ，针对这 一 元 素 （设 为 元 素 ），再 用 一 个 双 重 循 环 从 元 2 A A 数小于或者等于 时 ，则以转弯数加 、行不变 ，列 值 加 ，方 向 素 所 在 行 开 始 向 下 查 找 到 每 个 与 元 素 值 相 等 的 元 素 ， 调 用 1 1 1 A 为 “向东 ”的方式 ，往下层递归 。 方法 ，判断这两个元素是否存在有效路径 ，判断之 前 将 findPath 从 当 前 点 向 南 、西 、北 三 个 方 向 探 测 的 原 理 与 向 东 探 测 的 存储具体有效路径轨迹 的栈 清空 。 只要有一对点存 在 有 stack 原理类似 。 效 路 径 ，则 当 前 局 面 不 是 死 局 ，如 果 不 存 在 任 意 的 一 对 有 效 路 如果从当前点向东 、南 、西 、北四个方向探测 都 没 有 找 到 路 径 ，则当面局面是死局 。 当某一对图标之间存在有效路径时 ，因 径 ，则当前点肯定不是路径上的点 ，将当前点出栈 。 具体代码如 为是通过调用 方法来判断的 ， 则具体路径轨迹会自动 findPath 下 ： 保存在栈 里 ，需要获得路径提示时 ，只需从栈里去取 出 来 stack public final int NO_DIR = 0; // 无方向 即可 。 具体代码如下 ： public final int EAST = 1; // public boolean isDead(){ 东 public final int SOUTH = 2; // // 南 遍历面板上的每一个元素 public final int WEST = 3; // boolean flag = true;// 0 西 假设局面上每一个元素都是 public final int NORTH = 4; // for (int r = 1; r <= LEN; r++) { 北 public boolean hasPath = false; for (int c = 1; c <= LEN; c++) { Stack stack = new Stack(); if (board[r][c] ! = 0) { public int row1,col1,row2,col2; flag = false; public void findPath(int row,int col,int dir,int corners){ for (int i = r; i <= LEN; i++) { stack.push(new Point(row,col)); for (int j = 1; j <= LEN; j++) { // board[r][c] 在面板上找所有的值为 的元素 if(row == row2 && col == col2){ if (board[i][j]==board[r][c] && (r! =i || c! =j)){ hasPath = true; hasPath = false; return; row2 = i; }else{ col2 = j; // 向东探测 stack = new Stack(); if (col+1<=LEN+1 && board [row] [col+1]==0 && dir int temp = board[i][j]; ! = WEST && hasPath == false){ board[i][j] = 0; 2019 年第 1 期 2019 年第 1 期 福 建 电 脑 福 建 电 脑 17· · 

福 建 电 脑 福 建 电 脑 福 建 电 脑 UJIANCOMPUTER UJIANCOMPUTER UJIANCOMPUTER F F F findPath(r,c,NO_DIR,0); 本文算法解决了连连看游戏的所 有 问 题 ，核 心 环 节 ———路 board[i][j] = temp; 径 查 找 算 法 ，以 一 种 全 新 的 角 度 ，基 于 深 度 优 先 搜 索 和 栈 的 思 if (hasPath) 想 来 查 找 两 个 点 的 有 效 路 径 ，如 果 存 在 有 效 路 径 ，则 同 时 记 录 return false;// 未死 有效路径的轨迹 。 有别于其它查找有效路径与记录有效路径轨 } 迹需要分两步走的算法 ， 并且向东南西北四个方向 探 测 时 ，各 } 方向的探测原理是一样的 ，故算法非常精练 。 在实 际 测 试 过 程 } 中 ，本文所介绍的各算法稳定性很高 。 死局判断算法 需 要 用 到 } // if end 四重循环的嵌套 ，但在游戏开始阶段 ，局面上有效路径 很 多 ，只 } 有找 到一对有效路径 ，判断死局的方法即提前结束 ，游戏 后 期 ， } 局 面 上 非 零 值 很 少 ，故 这 部 分 的 算 法 效 率 并 不 差 ，但 是 希 望 在 if(flag)// 0 局面上每个元素都是 以后的工作中能设计出更加精美的死局判断算法 。 return false; else 参考文献： return true; ［ ］成 丽 君 张 宇 波 基 于 的 连 连 看 游 戏 的 实 现 ［ ］ 农 业 网 络 信 1 , . Android J . } 息 ,2013.(11):45-47. 2.4 游戏重排算法 ［ ］郑楚萍 衷明华 许越 吴锦伟 “化 合 物 命 名 连 连 看 ”学 习 型 游 戏 软 件 2 , , , . 当局面为死局时 ，应当在原来非零元素出 现 的 位 置 重 排 局 的开发 ［ ］ 广东化工 J . ,2011,38(9):210-212. 面 。 具体算法为 ： ［ ］张志山 生检连连看游戏的设 计与实现 ［ ］ 电脑知识与 技 术 3 . J . ,2015,11 第 步 ：遍历游戏面板数组 里的每一个元素 ，将里面 1 board (7):80-81. 的 非 零 元 素 依 次 保 存 到 一 个 长 度 为 的 一 维 数 组 LEN*LEN ［ ］ 云南大学学报 自然科学版 J . ( ),2012,34(Z2):338-342. ［ ］卜 学 海 任 翔 对 外 汉 语 视 角 下 的 “汉 字 连 连 看 ”游 戏 软 件 设 计 研 究 4 , . temps 里 ，并记录非零元素的个数 。 ［ ］袁 伟 实 现 连 连 看 游 戏 ［ ］ 电 脑 编 程 技 巧 与 维 护 5 .VC++ J . ,2010, (1):78- 第 步 ：将一维数组 里的元素打乱顺序 。 2 temps 84. 第 步 ： 将一维数组 里的非零元素依次替换游戏面 3 temps ［ ］王 文 举 语 言 开 发 连 连 看 游 戏 ［ ］ 电 脑 编 程 技 巧 与 维 护 6 .C# J . ,2013 . 板数组 里的每一个非零元素 。 board (17):76-80. 第 步 ： 判断通过以上三步生成的重置局 面 是 否 是 死 局 ？ 4 如果不是死局 ，游戏重排算法结束 ，如果是死局 ，跳转 到 第 步 1 作者简介： 继续 。 黎利辉 （ 年 月 ）男 ，湖 南 汨 罗 人 ，硕 士 ，副 教 授 ，以 机 器 学 1980 10 - 3.总结及展望 习与图像处理为主要研究方向 。 ： 。 E-mail 598438170@qq.com 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 （上接第 182 页） 项目考核 分 。 包括 个子项目完成 情 况 和 动 手 能 力 逐 入 大 量 时 间 和 精 力 ，一 个 教 师 带 多 个 学 生 ，往 往 力 不 从 心 ， 40 8 40 一考核 ，每个项目计 分 。 高质量的职业教育需要小班化教学 。 5 期末考试 分 ，包括一些基本常识和概念 、常 用 的 命 令 以 40 及 项 目 完 成 情 况 的 描 述 等 。 采 用 笔 试 ，开 卷 考 试 ，考 试 时 间 60 参考文献： 分钟 。 ［ ］傅 峰 ，徐 玉 莲 ，田 秀 芳 ， 《 操 作 系 统 》工 学 结 合 教 学 设 计 研 究 与 1 linux 从 年开 始 ，我 们 组 织 部 分 同 学 参 加 机 构 （开 放 2008 LUPA 实践 ，电脑知识与技术 ，第 卷 ，第 期 ， 年 月 。 8 26 2012 9 源代码全国高校推进联盟 ）的 网络管理员认证考试 ，一次 Linux ［ ］姜大源 ，职业教育学研究新论 ，教育科学出版社 ， 2 2007 性通过率达到 以上 。 90% 4、结语 ［ ］戴士弘 ，职业教育课程教学改革 ，清华大学出版社 ， 3 2007. ［ ］柴 艳 宾 ， 《 操 作 系 统 》课 程 教 学 改 革 探 索 ，职 业 教 育 研 究 ， 4 linux 2012 项 目 驱 动 教 学 法 ，是 一 种 以 项 目 覆 盖 知 识 面 ，以 项 目 体 系 年 月 。 11 ［ ］ 王 文 ， 项 目 驱 动 的 “ 操 作 系 统 ” 课 程 教 学 改 革 ， 计 算 机 教 育 ， 5 linux 进行教学的新方法 。 在实践过程中 ，我们采用真实 的 企 业 项 目 2007 9 年 月 。 宁波职业技术学院数字科技园的 服务器管理 ， 请企业专 Linux ［ ］杨丕华 ，高职 高 专 操 作 系 统 实 验 教 学 改 革 初 探 ，计 算 机 时 代 ， 6 linux 家参加课程的整体设计和项目设计 ， 组织部分同学参加 LUPA 2014 4 ，第 期 。 机构的 网络管理员认证考试 ，激发了学生学习兴趣 ，提高 Linux ［ ］竺士蒙 ， 操作系统 ，清华大学出版社 ， 年 月 。 7 linux 2010 2 了课堂教学质量 。 但是 ，毋庸讳言 ，项目驱动教学法在实施过程 中也遇到一些困难 。 比如 ， 个子项目的实施和考核需要教师投 8 18· · 福 建 电 脑 福 建 电 脑 2019 年第 1 期 2019 年第 1 期