3.3 生物的特殊操作

在游戏中，生物不仅需要移动，不同生物还有属于它们自己的特殊操作（比如说苦力怕和僵尸会跟随仇恨生物然后攻击，小白会向仇恨生物射箭等）。那么这些功能又是如何实现的呢

【资料图】

实现这些功能的代码都在控制生物移动的函数mov_ani()中。在这个函数中，我们在遍历每个生物的时候，不仅需要控制这个生物随机移动，还要判断当前的情况是否会触发这个生物的特殊操作，如果可以触发，则做出相应反应。下面我们就挑选三种生物，大概讲一下它们的特殊操作都是如何触发的。

3.3.1 猪

猪碰到草方块就会停下来吃草。

为了实现这个功能，我们需要随时监测猪是否在草方块上，如果在，则让这只猪停下来一会，再把这个草房快改成泥土方块即可。

检测猪是否在草方块上时，我使用了一个如下命令，其中world是存储世界的列表，qux和quy表示当前玩家所在的区块的坐标，i.x和i.y表示当前这只猪所在的相对于当前区块的坐标：

if world[qux][quy][0][int((i.x-i.x%20)/20*15)+int((i.y-i.y%20)/20)].obj_type=='grass':

可以看到，这个判断语句的时间复杂度是O(1)，也就是说，执行这个判断语句的时间始终为常量，与qux、quy、i.x、i.y的值无关。

这个语句能够被这样设计主要是因为区块内的方块是按照一定顺序生成的（具体顺序如下图），这样一来只要我们知道了猪的坐标，就可以在常量时间内确定猪所在的那个方块位于列表中的位置。当然，像这种使用位置坐标去反推存储地址的方法对边界值处理的要求非常高，稍有不慎就会出现下标越界的情况（就非常考验心态

检测到猪在草方块上后，我们该如何实现“吃草”的效果呢？

我们可以在存储猪的类里面定义一个新的变量eatmark，表示第一次检测到猪在草方块上的时间（这里的时间不是时分秒的时间，而是游戏的主循环进行的次数，下文中的所有“时间”都是这个意思）。这样一来，我们就可以通过检测eatmark所记录的时间与当前时间的差值来判断什么时候该让猪停下来，什么时候该把草方块改成泥土方块。

3.3.2 僵尸，苦力怕

僵尸和苦力怕类似，都是在检测到仇恨生物距离自己过近时跟随仇恨生物，并在满足一定条件之后开始攻击。这里的代码没有什么特别难的地方，检测距离、面向某个点后前进这些策略在之前的项目中也都被运用过，所以不过多赘述。

3.3.3 小白

小白在检测到仇恨生物距离自己过近的时候会向着仇恨生物射箭。

为了实现这个功能，我不得不创建一个新的类bullet来表示子弹。

实现子弹功能的代码与之前的项目中类似，就是创建一个子弹列表，把所有的子弹都放进去，然后每次循环遍历一遍所有子弹，把它们往前移一点，并且检测是否有生物被子弹击中。

但是玩过我之前编写的坦克动荡的读者都知道，在那个游戏中，一旦子弹个数过多游戏就会有明显的卡顿，非常影响游戏体验。

为了不让子弹个数影响游戏性能，我在上述子弹算法的基础上做了一些优化：

3.3.3.1 判断子弹击中玩家

为了有效地判断子弹是否击中了玩家，我设计了如下算法：

首先，给子弹的类中增加一个变量叫做distance。每次检测子弹击中玩家的时候，先遍历一遍所有的子弹，把每个子弹的distance变量赋上当前时刻子弹到玩家的距离

其次，把子弹按照distance从小到大排序，然后按照distance值从小到大的顺序遍历所有子弹，判断该子弹是否击中玩家。由于distance值是从小到大排序的，因此只要我们遍历到一个没有击中玩家的子弹，就可以停止遍历。这样可以大大节省计算量。

最后，把击中玩家的子弹删掉，并给玩家扣除相应的血量。

这个算法中最难的部分就是把bullet类的实例按照distance排序。虽然说python中自带给列表排序的函数，但是我就是不用那个函数好像没有办法按照实例的某个关键字排序。但是学过C++的读者都知道，C++的algorithm头文件中有一个叫做sort的排序函数，可以非常方便地按照结构体的某个变量排序。

因此，我在程序的主文件外另外创建了一个文件，将C++的algorithm头文件中的sort函数写了进来。这里我写的这个sort函数和C++中的sort函数用法完全一样，有需要的读者可以拷贝拿去用。

有读者可能会问为什么要另外创建一个文件来写排序函数。这是因为这样做比较灵活。python在引用第三方库的时候不仅可以引用从官网上下载的官方第三方库，也可以自己编写第三方库使用。具体方法就是在程序主文件的同一文件夹下新建一个.py文件，并在其中写入你想要引用的函数和类，再在主文件中写from 新建的文件的文件名（不包含扩展名） import *，这样新建的.py文件中包含的所有的类和函数都可以在主文件下调用了，非常的方便。

这里还要介绍一下C++中的sort函数。

sort函数的本质是快速排序。快速排序是众多排序算法中的一个，其平均时间复杂度和最好时间复杂度都是O(n*lgn)，而最坏时间复杂度则是O(n^2)，其中n是要排序的列表的长度。这里时间复杂度会有波动的原因是快速排序的时间复杂度还和输入的列表的打乱程度有关。下图展示了快速排序和冒泡排序（另一种排序算法）排序相同的列表时调用比较函数的次数，可以看到快速排序的比较次数远小于冒泡排序。

这里我选择使用快速排序的主要原因是它比较适合我的程序。由于在每次循环中我们都需要检测子弹，也就是说在每次循环中我们都需要给列表排序，因此在排序的时候这个待排序的列表基本上是已经排好序了的。因此在使用快速排序的时候，我们的时间复杂度大概率会是O(n*lgn)，这样做可以大大节省排序的时间。

最后，sort函数还需要一个cmp函数（即上面我提到的比较函数）。就是通过这个函数使得编程者可以设置按照某个关键字排序。

3.3.3.2 判断子弹击中其它生物

在判断子弹击中其它生物的时候，我还是选择了使用区块算法。

我们在之前提到过区块算法，但是那时我没有把区块算法用的很彻底（只在地图上划分了四个区块）。这次，我把当前加载的区块划分成900个小区块，先把子弹和生物对应到它所在的小区块中，再对处在同一小区块中的子弹和生物进行检测。由于一个区块内存在两个子弹的概率极低，因此检测每个生物是否被击中的时间复杂度基本上就是O(1)，达到了降低游戏对性的能要求的目标。

后续内容将在下期公示

注：

我已经将这个项目目前的源文件和exe文件上传到百度网盘，请使用下面的链接下载 

链接：https://pan.baidu.com/s/1gC_bmWiX1desLPUez7rVDQ?pwd=in8i 

提取码：in8i

从网页版bilibili复制链接时系统会自动加上出处和作者。请确保在把链接粘贴到搜索栏的时候去掉出处和作者，否则会显示链接无效

为了帮助我调试代码，我增加了一个检测程序报错并记录的功能。程序报错时会弹出一个窗口作为提示，同时程序文件所在文件夹下会出现一个名为error.log的文件，内有报错信息。请出现报错情况的用户及时将error.log发送到Jerrywriting公众号后台或者b站账号Jerrycjk的私信，谢谢配合。

更多系列文章，请关注微信公众号Jerrywriting

标签： 时间复杂度 快速排序 子弹击中