【阴阳师妖怪屋】你的式神是怎么被剪出来的？

发表于 更新于 分类于
阴阳师妖怪屋游戏中，关于抽卡时剪纸路径的算法。

前言

玩过阴阳师妖怪屋的小伙伴们都知道，妖怪屋的一个核心玩法就是抽卡。和阴阳师不一样，妖怪屋的“抽卡”是通过剪纸的方式进行的。话不多说，我们看一下游戏规则吧。

游戏规则

基本规则

基本规则就是给一个可可爱爱没有脑袋的小纸人剪出它的头。玩家拿着一把剪刀，在有效区域内，从起点开始，一笔画出任意一条路径到达终点。用剪刀沿着起点到终点的这一条路径剪过去，得到的最终路径，就是小纸人的脑袋啦。然后，小纸人的脑袋上会冒出来两朵红色的小啾啾，然后它就变成了你的式神。

如果还没有明白我的意思的话，那就看一下下面这个视频叭：

注意事项

尽管看视频好像很简单的样子，但是仔细思考一下，发现事情好像并没有这么简单——

酒吞

通过大量的实验（其实就十次，因为没剪刀了），我们可以得到以下结论：

  1. 路径的起点是固定的，在起点周围的一个范围内滑动屏幕的时候会触发开始剪纸；而如果在范围外滑动则不会记录路径;
  2. 路径的终点也是固定的，我们可以看到当我们的画笔在任意一个位置停下来的时候，它会自动的连一条从当前位置到小纸人的脖子和右脸的交叉点的线。
  3. 只能在小纸人的脖子上方开剪，超出这个区域的路径是不会被记录的；而路径的起点和终点，恰好在这个可剪区域的边界上（以实际一张纸为例的话，就是说起点和终点在这张纸的某一条边上，玩家只能在纸上沿任意路径从起点剪到终点）。
  4. 无论怎么乱七八糟的剪，最终剪出来的效果都与你真真正正的拿着一张纸从起点沿着你画的路径剪过去一直到终点的效果是一样的。并且呢，剪刀剪出来的路径一定是你画出来路径的一部分。
  5. 第五点是具体实现时的小细节：当我们在这个画布上画画（剪纸）的时候，其实它并没有把我们所有的路径都完整的存下来，而是隔一段时间获取一下当前触摸点的位置，然后用直线近似的代替曲线路径。换句话说，我们剪纸的路径，其实是坐标系中一个个的坐标点，相邻的坐标点使用直线进行连接。为了体现这一点呢，我们可以以单身18年的手速画一个曲线，可以发现，最终展示到屏幕上的却是一个直线。
  6. 小纸人头顶的小啾啾始终在沿着小纸人裆部竖直向上的最高点位置冒出。

分析

到此为止，我们知道了游戏规则和一些注意的点。我们需要做的，其实只是需要在玩家绘制的路径中挑选出最靠内的，或者说剪出的形状内部不存在其他路径的一条路径。那么我们如何将这条路径挑选出来呢？

根据注意事项小节中的第五点，玩家绘制的路径实际上可以看作一个拥有两个固定点（起点、终点）的无向图，我们要做的是在这个无向图上挑选部分边构成目标路径。我们做个假设，假如说有一个小蚂蚁要从起点沿着目标路径爬向终点，在当前只有一条路的时候，目标路径的可能选择是唯一的，但是当遇到分叉路口时，我们就需要考虑一下怎么选择了。于是问题又进一步的简化成了：在无向图中，从起点走向终点时，当前结点的下一个结点的选择问题。
路径示意图

这个时候，我们观察到，以上图为例，我们在挑选目标路径的时候，为了挑出最靠内的一条路径，我们可以与选取与当前前进方向顺时针夹角最大的方向为目标方向，即可解决问题。用图中的例子说就是：对于从$A$点爬到$B$点的小蚂蚁，由于边$\vec{BC}$与$\vec{AB}$之间的的顺时针夹角比边$\vec{BD}$与$\vec{AB}$之间的的顺时针夹角大，因此小蚂蚁的下一个目标点是$D$点。直观的想一下，对于每一个结点来说，它的下一个结点肯定是弯的越狠越好，因为在它外边的肯定就被剪掉了嘛。这种策略其实是一种贪心策略，从初始结点出发，每一次选择都是当前看来最好的选择。

不过我们知道，贪心策略可能得到的并不是最优解，我们需要想办法证明我们的贪心策略的正确性。证明过程也很容易理解，利用反证法：

证明
对于任意结点$B$，假如结点$C$是$B$的所有邻居结点中与$B$的连线和$\vec{AB}$顺时针夹角最大的结点，如果存在一个结点$D$，使得：$\langle\vec{AB}, \vec{BC}\rangle > \langle\vec{AB}, \vec{BD}\rangle$，但是结点$D$是$B$结点的下一个目标结点。此时：

根据注意事项2，我们知道无论经由$C$结点还是$D$结点，最终都会通往相同的终点。因此对于$B \rightarrow C$和$B \rightarrow D$方向的路径来说，总会在至少一个结点交叉。对于第一个交叉结点$X$，考虑由$BCDX$构成的闭合图形，如果$D$结点在目标路径上，那么$C$结点一定在目标路径内，这就与我们的要求：起点经由目标路径到终点的内部不存在其他路径相矛盾。

实现

实现步骤

简单实现一下这个过程，我们把以上描述梳理成如下步骤：

  1. 对玩家绘制的一系列线段，求两两之间的交点，并根据结点将线段拆分成除了线段的起点或终点外不互相交的线段；
  2. 根据步骤1得到的结果构建一个无向图；
  3. 从起点开始按照贪心策略寻找后继结点，直到终点；
  4. 将得到的一系列路径按次序连接起来，得到最终的路径；
  5. 给小纸人画上小啾啾。

对于第一步，我们可以通过快速排斥实验快速排除不交叉的两条线段，再将通过快速排斥实验的两条线段进行跨立实验，如果存在交点则计算交点。

对于第二步，设计一个数据结构进行存储：

1
2
3
4
5
interface Node {
    point: Point, // 坐标
    neighbor: Node[], // 相邻结点
    status?: boolean
}

对于第三步，只需要对第二步中neighbor数组内的结点进行判定即可。

第四步就是一个简单的canvas绘制过程。

第五步其实就遍历一遍就好啦。

整个实现过程由于涉及到了向量的计算，因此使用到了mathjs库，除此之外，项目使用了pixijs渲染框架。具体代码中，用到的比较多的是两条线段点积和叉积的计算，以及一些简单的判断和循环，逻辑还是很清楚的。实现的demo效果如下，感觉和游戏中的剪纸还是有几分相似的(但是!!有bug!!!不知道是上边思路的漏洞还是实现有问题。。但是没空检查就这样8)：

剪纸路径demo

剪纸路径

剪纸效果demo

抽卡demo

体验地址及代码地址

体验地址在这里：妖怪屋抽卡

代码地址： gitee地址戳这里, github地址戳这里