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

本文正在参加「金石计划」

嗨！大家好，我是会做游戏也会教你做游戏的小蚂蚁。欢迎关注微信公众号【小蚂蚁教你做游戏】，每天学点儿做游戏的知识。

今天我们继续消除游戏系列教程，来看一下点消游戏中查找算法的原理和实现，什么是点消游戏呀？消星星听说过吗？没有的同学可以去查一下。

如图，在点消游戏中，当我们点击任何一个图标后，它周围的所有与它相同的图标会被同时消除掉。这个就是点消游戏的基础规则和核心玩法。

点消游戏的查找算法是如何实现的呢？如果你有好好研究过之前的三消游戏查找算法的原理和实现，就会发现这个点消的查找算法只不过是一个精简的三消查找算法，它只需要查找一轮即可，因为只要相邻的有两个相同的图标，就能够满足消除条件。

先理论

我们还是先看理论。整个点消查找算法的过程是这样的：从点击的图标位置开始，依次查找其左，上，右，下四个方向的相邻图标，如果发现相邻图标跟自己一样，就以这个相邻的图标为中心，继续查找其左，上，右，下四个方向的相邻图标（这里用到了递归查找）……直到查找到的图标跟自己不同为止，再继续查找另一个相邻图标，直到所有的相邻图标查找完毕。

过程描述看不懂，没关系，我们来看图解的整个过程。

假设在这个示例中，玩家点击了中间的绿色三角形图标，整个查找过程将会是下面这样：

在上方的示例中，玩家点击一个图标后，一共是需要进行 23 步查找操作，才能够把所有满足条件的图标都找出来。其中比较难以理解的地方就是递归查找，找到一个相同的图标，就要以这个图标为中心继续查找。你可以把整个查找过程想象成找一个树的每一个分支，从树的主干开始找，每当遇到一个树叉的时候，都会沿着这个树杈继续向前找，只要按照这种方式找下去，那么最终回到主干的时候，就能够将整棵树的每一个分叉都找遍。

推导整个算法的查找过程是一件蛮有意思的事，如果觉得文字描述不好理解的话，你不妨也试试把整个查找过程画出来，画出来就容易理解了。

后实践

接下来，我们就来看一下整个查找算法在具体游戏中的实现。以下为使用微信小游戏制作工具的实现，其它游戏引擎的实现原理也是类似的。

如图，要比三消的查找算法简单很多，其实最主要的就是一个递归查找函数。我们来看一下这个递归查找函数中的积木逻辑。

如果当前的图标跟要匹配的图标相同，并且还没有被查找过，就将其加入匹配列表，并且以它为中心，查找其左，上，右，下四个相邻位置的图标。

至于“递归查找2”这个函数，跟“递归查找1”是一模一样的。因为微信小游戏制作工具不支持递归函数，所以只能以这种讨巧的方式来实现。

如何在微信小游戏制作工具中实现递归函数，可以参考【这篇教程】。

至此，整个消除系列教程又完成了一步，下一个是连线消除，你准备好了吗？

写这个消除游戏系列教程是一件吃力不讨好的事情，花费大量的时间精力写一篇，阅读者却寥寥无几，远不及一篇不用花费多少时间精力写出来的水文。不过，我们总是要为一件事情赋予一种特殊的意义，否则遇到投入产出不成正比的时候，就不再有动力做下去了。

我为这件事找到的意义就是，这是一件投入产出不成正比的，极少有人愿意做但是又必须有人去做的事，而我就是那个必须之人，有能力做，而且还能把它做好。

我相信这个系列教程一定能够帮助到一些人的，哪怕是几个也足矣！