【弹幕程序科普计划】 第十二篇 判定形状

【判定形状】

　　上次文章讲了一些和判定关系、判定逻辑相关的问题，本次来介绍一下常用的判定形状及适用场合。正好我之前在弹幕音乐绘·基础教学篇A-2中已经示范大多数的判定形状，本次也就拿这篇的截图进行一些讲解和补充。以下所有子弹中的红**域表示判定区域。

1. 圆形判定

　　在同人STG中最长用的判定形状，也是最容易理解的形状。判定公式只需要计算两点间距离然后减去半径，非常简单，很多非圆形的子弹也会使用圆形判定。但是由于计算公式中需要进行平方、开根的运算，这种判定方法并不是效率最高的，而效率最高的方法是正方形判定。

2. 正方形判定

　　这里所说的正方形是指不旋转的正方形，一直正放的正方形。上图将中玉和自机改为正方形判定做了一个示例。类似的，也可以用不旋转的矩形做判定。这种判定形状只需要计算两点在X方向和Y方向的距离，不需要平方开根，因此效率最高，缺点是判定形状和可视形状不一致，对于一圈子弹来说，斜方向的缝会比正方向小，子弹越大问题越明显，如下图。因此这种正方形判定常用于小子弹，在街机上广泛使用。在东方原作中，自机子弹和敌机、Boss的判定也是方形判定。

3. 椭圆判定

　　通用性比圆形判定强，当椭圆的长轴和短轴相等时就等于圆形判定形状。我将这种形状用于射线激光和魔炮的判定，如上图。虽然通用，但是椭圆判定的计算量比圆形大很多。如果椭圆正放还好说，点在椭圆内的判定公式也不难写，但是椭圆旋转以后，就需要求各种投影距离，不仅需要平方、开根，还需要用三角函数。因此这种形状的子弹最好不要同屏出现太多，避免过高的计算量。

4. 点序列判定

　　通过记录一系列上一状态的位置点，或者说是运动轨迹点，然后逐点进行圆形判定。这种判定方式主要是针对曲线激光，我为了统一将线段激光的判定也写成了这样（其实是在偷懒）。可能需要说明一下，曲线激光和线段激光的显示原理是完全不同的，线段激光只是将贴图直接画上去就可以了，而曲线激光需要使用到网格变形，和PhotoShop中的“操控变形”工具原理类似。出于曲线激光显示原理方面的原因，本身曲线激光就需要记录一系列的轨迹点，供网格变形用，所以用这些点进行判定计算也顺理成章。

　　关于点序列判定的缺点，一方面是计算量大，因为相当于一系列的物体在判定；另一方面点和点间存在空隙，当空隙足够大以后就会出现自机神穿了。去年夏天东方吧Rep楼活动中，音乐绘Rep楼特别版出现了E-4天星激光神穿事件，就是因为激光速度太快造成判定点间距过大引起的。（所以说没事不要用弹速大于6的子弹【手动捶地】）

5. 矩形判定

　　这里的矩形指的是可旋转的矩形。

　　前面说到的线段激光，我没有使用椭圆判定主要是考虑到椭圆中间比较宽，可能会出现擦激光擦到一半突然暴毙的尴尬场面；另一方面由于希望线段激光具有随速度增加而拉长的效果，所以线段激光也需要记录一系列轨迹点，所以索性用了点序列判定，和曲线激光也统一。但是实际上用矩形判定肯定会更好，无论是直角矩形、圆角矩形还是完全倒圆角的矩形，都是可以的。这样不但计算量会减少，也不会出现神穿现象。不过话虽如此，矩形判定公式的复杂程度远比一个循环语句加圆形判定来得复杂。

　　以上依次为直角矩形、圆角矩形、完全倒圆角的矩形。你问为什么会扯出这三种形状？主要由于自机判定点是圆的。。。

6. 像素图判定

　　对于一些形状非常不规则的物体，可能会用到像素图来标记判定区域的方法。比如说立绘杀，一张立绘要与自机判定，对于立绘这种不规则形状的物体就可能需要通过图片像素颜色来标记判定区域。但是立绘的分辨率较高，如果逐点计算必然计算量巨大，因此最好还是用另一张降低分辨率的二值图来进行判定计算，或者使用隔点采样之类的方法降低计算量。这种判定方式不是很常用，这里就不展开了。

7. 正交圆判定

　　东方原作从TH11《东方地灵殿》开始采用的判定形状。与普通圆形判定公式相比，如果圆形的判定公式是D<? R1+R2，则正交圆判定公式为D^2<? R1^2 + R2^2。其中D为两物体中心的距离，R1、R2分别为两物体的半径。

　　之所以将这种判定形状最后讲，是因为我实在不理解神主为什么会使用这个方法。虽说从公式中可以看出，本身计算距离D时需要开根，用正交圆判定时可以省去这个开根的运算，但是这能带来多少性能上的提升，实在有待商榷。相反的，这个判定形状会带来一系列衍生问题。我可能会视情况，下一期文章单独分析一下正交圆这个判定形状。

　　以上总共介绍了七种判定形状。在此之外，对某些复杂形状物体进行判定时，常通过多种基础形状组合使用。比如街机里的大型机，可能将多个判定矩形组合起来判定。

关于优化

　　以上介绍的基本形状中，东方及其同人STG常使用圆形（正交圆虽然公式不同，但也算是一种圆），但是正方形效率最高。其实，完全可以对所有物体先进行正方形预判定，或者说先进行粗略判定，再进行精确判定。以圆形判定为例，可以先使用圆形的外切正方形进行判定，仅当正方形判定相交后，再进行圆形判定。考虑到全屏上千颗子弹中，与自机发生碰撞的子弹可能只有1颗，因此这样几乎可以在方形判定计算量下达到圆形判定的精度。对于椭圆、点序列等判定形状，也可以类似地求出外包络矩形来进行预判定，将大大减少计算量。此外，通过空间划分、四叉树、八叉树以及一些更先进算法进行优化的手段也是存在的。

关于三维物体的判定

　　三维物体判定方法和二维有很大区别，很多时候是通过计算三角面之间的关系来判定。对于曲线激光虽说应该也可以通过三角面来计算判定，但是效率未必会比点序列来得高。

以上就是STG中常用判定形状的大致情况，那么本次科普就到这里。

本次贴吧原贴下方有比较多有营养的回复，所以补个原贴链接https://tieba.baidu.com/p/5062993283?pid=106045069746&cid=0#106045069746