小球是怎么落入指定球洞的?

2016-01-18 by Dron

Billiards.png

这篇文章首发在 淘宝前端团队博客,现在转发到作者自己(也就是我本人)的博客上。

游戏回顾

不知大家是否还有印象,淘宝玩法平台(一个内部系统)前不久发布了一款新的游戏 —— 小球入洞,该游戏伴随着淘宝技术部去年双 11 当天举办的一次抽奖活动,第一次在大家面前亮相。

Try Button.png

游戏支持预先设定必中奖项:离开发射器的小球在来回弹跳一阵之后,不偏不倚的落入到指定奖项对应的球洞中。体验该功能,可在游戏测试页右侧选项区进行如下的设置:

Options.png

本文试着介绍游戏的这个「掉落至指定球洞」的功能,讲的偏思路,并不涉及公式和代码,我尽可能直白,如果你觉得晦涩,可以在评论处我们接着探讨。在继续之前,为了表达上的方便,我将对游戏在视觉上进行如下图的划分:

Area Division.png

为什么需要指定球洞?

做过抽奖 UI 组件的同学都知道,抽奖结果一定是由后端计算之后返回的,原因主要有两个:1)安全方面考虑,抽奖结果的产生过程不能在前端实现;2)只有中间服务才能更加准确的分配多端的抽奖结果。

鉴于此,所有抽奖 UI 组件都必须满足:可事先抽得结果之后再播放动画(显示结果)。抽奖大转盘便是一个很典型的例子,在转盘滚动的时候,根据 AJAX 请求的返回,JS 其实已经知道它最终会停在哪个扇区上了。

小球入洞是一个抽奖类 UI 组件,所以当然也必须支持指定结果的抽奖,那么问题来了,小球的整个过程并不是一段简单的动画,怎么才能使之落入到指定球洞呢?

小球如何落入指定球洞?

如上图示意,游戏的主场景三面环壁(小球反弹),一面布满小洞(小球穿过),由于重力的关系,小球在有限次碰撞弹跳之后,最终一定会通过下面的小洞穿出。

「落入指定球洞」自然成了完成该游戏的第一个也是最棘手的一个难点,因为小球从发射器射出时(离开黄色区域瞬间),方向是确定的(水平向左),难以从指定球洞开始,逆向地推导运动路径并使之最终以确定的方向(水平向右)进入发射器中,此方法非常容易导致路径太长或者无解,寻路耗时将不可控。基于逆向推导在之前也尝试过多种优化方案,均以失败告终。

最终采用的方式是正向推导路径,即:从离开发射器开始,模拟小球的物理运动,迭代式演算,找出一条刚好能穿过指定球洞的路径。

受场景其它物体影响(碰撞),小球的运动路径并不能用一个公式描述出来,它的整个过程应该由多段的抛物线组成,每一次碰撞都结束一段并开始一段新的路径,所以需要迭代法逐帧推进,才能描绘出完整路径,下图是一条路径的演算过程:

Precalc.png

假设重力加速度、空气阻力以及所有钢体的弹性都是恒定的,并且墙壁和障碍物都静止不动,小球在离开发射器之后,运动路径就固定下来了。换句话说,影响小球轨迹的就只剩下小球离开发射器那一瞬间时的速度(离开瞬间的方向固定水平向左)。

让小球落至指定球洞,起关键决定作用的就是离开发射器时的初始速度。如果能找出落向每个球洞所需的初始速度,问题就解决了。

Ball Init Speed.png

暴破

不知怎么给这个含义扣个名堂,我估且称之为暴破法吧,暴破即暴力破解,通常用于破解密码,拿大量不同的钥匙试开一把锁,如果刚好其中一把钥匙能打开锁,那么暴破就成功了。

包括我在内的多数人,可能会认为暴破的时间成本很高,所以在最开始的思考中首先会自觉地把此方案屏蔽掉,在多次其它方案的实验失败后,我偶然一试此法,发现其实不然。

在本游戏中,我用不断递增的初始速度(钥匙)来试算路径,由于没有 DOM 操作,且计算量并不是很大,很快就可以找出经过指定球洞(锁)的其中一条路径。

下图是根据两个不同初始速度试算出来的两个不同结果:

Scanning Path.png

暴破的耗时有多方面的影响,本例中我用 2000 个不同的速度(从 1315,步进为 0.001),在某一次实验中,跑了 10 万次自动用例,平均一次搜索出结果尝试次数(使用的初始速度的个数)是 11.6 次,平均一次搜索出结果用时只有 4.65ms,这个数值让我很意外,几乎没有优化的必要。

在以上的 Demo 中,「搜索路径」这个动作发生在玩家释放弹簧之后,小球弹出之前,5ms 就消耗在这里,可以体会体会 :)

暴破有时可以成为迅速解决问题的有效手段,比起折腾 AI 来说更加节省研发成本,对于复杂度不高的小游戏,可行性还是满高的,也因为没有 DOM 操作,甚至可以放在 WebWorker 里面进行。

人机对战的台球游戏,机器的 AI 就完全可以使用此法。

路径拼接

搜索路径解决了,剩下的问题就简单得多,小球的整个运动,在本游戏中我将之分成三个阶段:

  • 小球弹出后,来到发射器右上拐角之前,此为第一阶段,为了简便,下文记为 A 阶段;
  • 小球经过拐角后,离开发射器之前,此为第二阶段,也就是 B 阶段;
  • 小球离开发射器,直到落洞结束,此为第三阶段,C 阶段;

三个阶段如下图所示:

Animation Segments.png

前面探讨的搜索路径一直指的都是 C 阶段,为了使整个动画看起来连贯,小球的速度变化一定得平稳,也就是:C 阶段开头的瞬时速度,等于 B 阶段结尾的瞬时速度;B 阶段开头的瞬时速度,等于 A 阶段结尾的瞬时速度。

如果不考虑磨擦和撞击后的动能衰减,其实阶段 A 加阶段 B 在速度变化上就是自由落体的逆过程,为了简便,我将阶段 A 和阶段 B 做了合并,以同一个抛物线公式(自由落体)表示,根据 C 开头的瞬时速度,可以生成 AB 的完整路径,这样就得到小球的整个运动路径了,这个过程应该好理解,不再赘述。

小插曲

由于必须落入指定球洞,所以 A 阶段的初始速度自然也是固定的了,慢着!这里似乎有点儿不对劲?

弹簧的存在增加了整个过程的违合,正常人的理解,应该是弹簧压缩得越厉害,小球射出时的初始速度越大,这跟合成路径所需的初始速度不匹配:一个是变化的,一个是固定的。

有两个解决办法:

  • 1)使阶段 A 的初始速度受弹簧影响,利用阶段 A 或阶段 AB 的路程来逐渐消除该影响,使之看起来变化是平滑的;
  • 2)分两种情况:弹簧压缩比小于 0.75 时(轻轻拉),小球初始速度受弹簧影响,但使小球弹射不成功(发出去又掉回来);弹簧压缩比大于 0.75 时(用力拉),小球初始速度直接等于合成路径所需的初始速度(正常发出去);

我采用的是后一种解决办法,因为前一种在动画上看起来反物理,似乎重力加速度是在变化的;而后一种方案至少弹簧压缩比在 0-0.75 区间时都是正常的,而 0.75 以上实际体验后违合感并不太明显。

最后的这个问题其实正是因为非得「射入指定球洞」这件事情引起的,将这一枚小瑕疵掩藏于弹簧的这 25% 的空间里,个人感觉不算太破坏完美,所谓一快遮百丑,这就是现实版弹珠台和电子版的区别。

(本文完)