斜方向三消查找算法的原理和实现

本文首发于微信公众号【小蚂蚁教你做游戏】,欢迎关注领取更多学习做游戏的原创教程资料,每天学点儿游戏开发知识。

嗨!大家好,我是小蚂蚁。

昨天的文章中我们讲了三消查找算法的原理和实现,在宝石方块中,除了水平和竖直的三消之外,斜方向上也可以三消,今天这篇就讲一下斜方向上三消的原理和实现。

斜方向查找的原理

斜方向三消查找算法的原理和实现

如图,黑线画出来的红色宝石满足斜方向上的三消条件,所以这些红色宝石也能够消除。

斜方向分为两种,一种是从左下方向右上方倾斜,我们把它叫做“向右斜”,一种是从右下方向左上方倾斜,我们把它叫做“向左斜”。对于斜方向的查找,就是沿着两个方向查找,即“向右斜查找”和“向左斜查找”。

斜方向三消查找算法的原理和实现

首先,仍然是进行一下数据抽象,构建一个由数字组成的表格,这个表格是后续的判断和计算的基础。

整个查找过程是这样的:

从第 1 行第 2 列的宝石开始。

先进行“右斜”查找,检查右上方的宝石是否与自己相同,如果相同就记录下来,然后继续向右上方检查,直到右上方的宝石与自己不同为止。查找完成后,统计找到的相同的宝石数量,如果大于等于 3 个,则记录这些宝石满足消除条件。

再进行“左斜”查找,检查左上方的宝石是否与自己相同,如果相同就记录下来,然后继续向左上方检查,知道左上方的宝石与自己不同为止。查找完成后,统计找到的相同的宝石数量,如果大于等于 3 个,则记录这些宝石满足消除条件。

接着检查第 1 行第 2 列的宝石。

......

直到所有的宝石检查完毕为止。

来看一下第 1 行第 1 列宝石的整个查找过程。

斜方向三消查找算法的原理和实现

斜方向三消查找算法的原理和实现

斜方向三消查找算法的原理和实现

斜方向三消查找算法的原理和实现

接着将剩下的每个宝石都进行一次斜方向的查找,所有的宝石都查找完毕后,这整个过程就结束了。

斜方向三消查找算法的原理和实现如图,“向右斜”的查找用蓝线表示,“向左斜”的查找用绿线表示。其实,在这整个查找遍历的过程中,并不需要将表格中的每个宝石都进行一遍斜方向的查找,例如在对第 1 行 1 列的宝石进行查找的过程中,已经找到了与它相同的第 2 行 2 列的,以及第 3 行 3 列的宝石。所以这两个宝石在遍历的过程中,就不需要再次进行检查了。

可以借助一个列表来记录那些已经检查过的,不需要再次检查的宝石。在检查之前可以先去找一下列表,如果这个宝石已经在里面了,就无需再次检查了。这样可以提升整个遍历检查的效率,即使计算机很擅长计算,也不要让它去做重复的无意义工作。

斜方向三消查找算法的原理和实现

至于怎么找到右上方或者左上方的宝石呢?其实非常的简单,已知当前宝石的行列号,那么它右上方的宝石就是(行号+1,列号+1),左上方的宝石就是(行号+1,列号-1)。

以上就是斜方向查找的理论基础了,要比水平竖直的三消查找简单很多。

斜方向查找的实现

来看一下实现的积木逻辑。

斜方向三消查找算法的原理和实现

右斜查找的函数,其中只包含一个斜方向查找的迭代函数。

斜方向三消查找算法的原理和实现

接着来看一下两个一摸一样的迭代函数。

斜方向三消查找算法的原理和实现

斜方向三消查找算法的原理和实现

除了名字不一样,所有的积木都一样。

以上就是斜方向三消查找的原理和实现了,加上之前讲过的水平和竖直方向上三消的查找,就构成《宝石方块》游戏中完整的消除规则了。

三消的查找算法是一些看似很难,但是实际上并不难的东西。

这里分享一点儿我自己的学习技巧,有些东西,尤其是之前从未接触过的,乍一看,完全看不懂。这时的第一反应往往是抗拒,会产生这样的想法:不要弄了,这个太难了,你学不会,看都看不懂,怎么学呢?

此时,我就会不停的告诉自己:看不懂很正常,那就多看几遍,硬着头皮使劲看,早晚能够看的懂。现实往往也是这个样子,每多看一遍似乎就能够多懂一点点,当看的遍数足够多了,这个东西就变的不再难了。另外,除了看,动手也很重要,我习惯于在纸上画,这能够帮助我更好的理顺思路,更好的理解问题。

其实不大部分学不会的东西,并不是因为它太难了,而是因为我们太懒了。


欢迎关注小蚂蚁的微信公众号【小蚂蚁教你做游戏】,学习更多游戏开发原创教程。

斜方向三消查找算法的原理和实现

发表评论

相关文章