三消游戏查找算法的原理和实现

嗨！大家好，我是小蚂蚁。

今天这篇文章分享一下三消查找算法的原理和实现，其实三消的机制最早源于宝石方块这款经典游戏，如今三消已经属于一个游戏品类了。

三消的查找算法是通用的，可以用于几乎所有的三消游戏（完全基于物理的游戏除外），如果你之前不知道的话，那么今天的这篇教程就可以好好的研究研究了。

原理性的东西很重要，值得你花点儿时间好好的学习，一旦你掌握透彻了，以后会发现它们可以用于各种各样的地方，不论你到时候是用的是什么样的游戏引擎，什么样的开发语言，原理都一样，放之四海而皆准，相信我，这一点我深有体会。

三消查找的原理

如图，是一个典型的消除游戏的画面。这里一共有 4 种不同的宝石，图中第一行的前三个红色宝石是相邻的，满足三消的条件（相邻的 3 个宝石相同，就可以消除）。

这是我们直观看到的画面，以及通过这个画面做出的判断。但是对于计算机来讲，它看不到我们所看到的这些不同的形状以及颜色，它能看到的只是数据。

想要用计算机编写程序实现查找算法，首先要将我们所看到的这些东西转化成计算机能够理解的数据。

如图，为四个宝石分配 1，2，3，4 的四个编号数字，每个数字代表一种宝石，空位置就用 0 表示。把所有的宝石和空位置替换成数字，填写到右侧对应的格子中。

这样，我们就得到了一个计算机能看懂，而且也很擅长处理的数据表格。这个数据表格是三消查找算法的基础，后续的所有查找操作都基于这个数据表格。

其实右侧的数据表格完全等同于左侧的这个由不同颜色宝石填充的表格。这个过程也叫做数据抽象，之前专门写过一篇文章介绍它，可以前往【这里】了解。

第一轮检查

有了数据表格之后，就能够进行查找操作了。这里我们先描述一下查找的过程：从第一个宝石开始，依次检查它的左、上、右、下，四个相邻位置的宝石，如果发现相邻位置的宝石跟自己相同，那么就记下这个宝石的位置，并且从这个宝石的位置开始，继续向同一方向检查，直到相邻位置的宝石不相同为止。如果相邻位置的宝石跟自己不同就继续检查下一个相邻位置，直到检查完所有的四个相邻位置。

看不懂是吧？没关系。先看个大概，然后接着看下面的查找过程的图片。

上方是左下角第一个红色宝石的整个查找过程，结合着整个流程图，再去理解一下之前我们说的查找过程。

当然，这只是第一个方块的查找，在整个游戏中，每个格子中的宝石都需要进行这样的检查过程。是不是觉得很多？计算机可是一点儿都不会这么觉得，因为遍历计算就是它所擅长的事（这一点儿计算量对于它来说根本都不值一提）。

这样检查完一遍就完事了吗？当然不是了。

通过第一轮检查，我们找到了上方的这 4 个宝石，但是这四个宝石并不都满足消除条件，只有在同一行或者同一列上相邻的三个才满足消除条件，所以，只有第一行的三个宝石能够消除，第二行的第一个宝石不能够消除。

第二轮检查

接下来我们就要进行第二轮检查了。在第一轮检查中找到了所有（水平/竖直）相邻的方块，第二轮检查要做的就是，找出其中位于同一行或者同一列的宝石，然后判断在同一行或者同一列上是否有三个或者三个以上的宝石，有的话，这些宝石才是最终要消除的宝石。

在第一轮的查找过程中，我们说找到相同的宝石就记录下来，这里记录的信息是这个宝石在表格中的位置，这个位置可以用一个行号和一个列号来表示。如图，四个宝石的行列号位置分别为 (1,1),(1,2)(1,3),(2,1)，第二轮检查就是以这四组数据为基础的。

检查的过程是这样的：拿出第一个位置数据，分别以这个位置数据的行号和列号为准，检查剩余数据的行号或者列号是否与它相等，相等的话就记录下来。待检查完毕后，统计一下位于同一行或者同一列的宝石数量，如果大于等于 3 个，就将这些宝石的数据记录下来，用于后续的消除处理。

这样，在进行第二轮检查之后，就能够找到最终符合消除条件的宝石了。

以上，就是三消查找算法的原理了。你搞明白了吗？什么？没明白？很正常，你又不是天才，多看几遍就会了，这么重要的算法看一遍就会了，那就证明它不重要了。想当初研究三消算法的时候我是看了做了很多遍才能彻底的理解透测，熟记于心，普通人想要学好知识的话，勤奋点儿总是没错的。

三消查找的实现

最后，我们简单的讲一下三消查找算法在微信小游戏制作工具中的实现，其它游戏引擎的实现方式原理都是一样的，就交由你自己摸索了。

对于第一轮查找来讲，其中的一个难点就是“递归”。这里的查找算法使用了递归，即在当前方向上找到相同的宝石后，会继续向前找，直到不相同为止。实现这个不断向前的查找过程，最好的方式就是使用“递归算法”。

第一轮查找放在“水平竖直查找”函数中。

接着来看一下用于递归查找的函数。

“递归查找1”和“递归查找2”其实是两个相同的函数，它们通过互相调用，以此来实现递归查找。

微信小游戏制作工具目前并不支持递归函数，但是却留下了一个可爱的小 bug (不知道是不是有意而为之)，让我们可以使用两个函数互相调用的方式，最终实现递归函数的效果。关于递归函数的实现方法，可以查看【这篇教程】。

在完成了第一轮查找后，我们把所有相同的宝石都放进了“匹配元素的索引”这个列表中了，接下来看一下第二轮查找过程。

在第二轮查找中，我们没有直接使用行列号，而是使用了一个索引，通过索引换算成行列号，然后进行比对，关于索引和行列号的换算，可参见下图。

这些积木看上去很多，实则就是实现了上方原理中讲到的两个查找过程。为什么你会觉得实现起来这么复杂呢？主要是因为你都还没有试过静下心来仔细研究啦！

理解原理很重要，如果你能够在脑袋中将整个查找过程推演出来，那么实现它只不过是将一个清晰明确的想法表达出来而已。至于使用什么游戏开发工具，是使用积木还是使用代码编写逻辑，那都是最终的表达过程。如果连想法都没有的话，那么再好的工具，再厉害的语言也都无济于事。

想要借助一个三消项目结合着教程进行更好的学习？

想要更好的学习游戏开发？从入门到进阶一套课程服务全部搞定，欢迎来与一百多位同学一起学习做游戏，【点击这里】了解全新升级的课程服务内容详情，升级上新特价 699 ，只卖 10 天，10 天后恢复原价。

我是会做游戏也会教你做游戏的小蚂蚁，想学习做游戏的话，关注我的就对啦！

这里是小蚂蚁的小游戏系列，闲暇之余希望能给你带来片刻的放松和愉悦。无需下载安装，点击下方的游戏卡片就可以直接玩啦！

也欢迎加个微信，交个朋友，朋友圈每日分享与做游戏有关的知识和内容，可以来围观。备注“学习做游戏”可免费领取学习做游戏的原创教程资料。接受付费咨询，不闲聊，望见谅。