BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

Flash务实主义(二)——最短路径原则(上)

| 作者 flashyiyi 关注 0 他的粉丝 发布于 2011年3月8日. 估计阅读时间: 9 分钟 | CNUTCon 了解国内外一线大厂50+智能运维最新实践案例。

最短路径原则,就是将复杂的问题简单化。

达到目标并不是只有一条路,眼前的那条往往也不是最短的一条。所以,解决问题前的第一步,应该是要找实现目标的最短路线。虽然有些人可能会喜欢完成些复杂的算法来获得成就感,但这就是另一个话题了。

要明白,我们是作为实现工具的工人,而不是授命在空中楼阁中研究的学者。

魔术师视角,而不是观众视角

首先是一个比较典型的例子。

那位兄台提出这个问题的时候,问的是碰撞检测。

而且是不规则形状,有凹的也有凸的碰撞检测。判断两个物体是否边缘匹配,可以拼在一起。最后还要在放下时自动检测周围的方块,并自动吸附。必须得说,这个课题真的很困难,倒不是说找不出方法,而是找不出效率可以接受的方法。优化的办法应该是有的,但是我不会,因为这个还得吸附啊,我哪知道哪边才是边。但后来我觉得不对劲,就问了下他实际要做的东西。

才知道这家伙原来是做——拼图。

所谓拼图,就是一个图片被拆成各种不规则形状然后打乱,然后让玩家重拼起来,需求就是这样。好吧,既然是这样,那么记下这些碎片的原始位置,然后判断你手上的碎片目前坐标是否接近这个位置不就好了。

电脑没有必要使用人的思维,设计者没必要使用玩家的思维。完全模拟,并不是最好的方案。

首先考虑简单的近似实现

老外的东西总是能有惊喜。老外的思路常常都很单纯,过度设计的情况很少见。不管怎么说,他们的经验还是要丰富一些的。虽然一个需求怎么都能实现,但细微之处的积累依然会产生大的变化。这次嘛,是关于一个同事在玩的SNS游戏,它里面捡钱会曲线飞到表示钱的数字上这个效果挺别致的。

国内的情况,连做个直线飞就已经多余了,更不要说曲线了。但曲线的效果的确比直线生动很多。然后我就在仔细观察它的轨迹,考虑它是怎么实现的,想做一个类准备着以后来用。一般的想法,是用二次贝尔法曲线公式计算出运动轨迹,虽然需要一定的数学公式但曾经做过应该不成问题,而且TweenMax也提供了这个功能,但既然是曲线就有曲率的问题,而参考的效果并不是固定的1/4圆,况且这种做法有些太小题大作了。然后就是考虑物理移动,但原效果看起来使用了圆缓冲,越接近目标越慢,而且是平行y轴结束,这个用物理模拟会比较困难……

最后我脑子突然灵光了。让X轴方向用匀速移动,Y轴方向减速圆缓冲移动,看起来貌似就是画面里的样子……

也就是代码:

TweenLite.to(target,{x:tx }); 
TweenLite.to(target,{y:ty,ease:Circ.easeIn }); 

其结果就是弧线,和原品一模一样的。很显然,这还要做类会很无聊。

即使有复杂的解决方案,也应该考虑是否有更简单的方案。复杂的方案只是适用范围更广泛而已,但既然有“这么简单”的,何必去费那个事呢。

到现在还不知道TweenLite是什么的参见以下地址:http://www.greensock.com/tweenlite/

“根据需求选择技术”VS“将适用的技术用于需求”

说到这里,正好提下四叉树的问题。四叉树的确是一个很经典的解决屏幕物品筛选遍历的方案。具体是怎么做的可以参考网上的其它资料,可惜原理讲起来有些拗口,实现也比较恶心,所以目前并没有被广泛使用。

但是这东西不就是筛选屏幕内物品用的么?因为有两个坐标,可以将物品按坐标归类。这里我们又犯了“将适用的技术用于需求”而不是“根据需求选择技术”的错误。四叉树的确可以用来快速筛选屏幕内的物品,但并不是说筛选屏幕内的物品就只能用四叉树。要知道四叉树可以处理任意缩放屏幕,以及无限大的坐标系内的快速筛选,但我们实际上需要的就是几十屏以内固定屏幕大小内的筛选。

实际上,有个很好理解的代替方案。我们可以创建一个二维数据,诸如地图是10000*10000的,屏幕大小是1000*1000,我们就创建一个20*20的二维数组,然后将坐标范围在(0-500,0-500)的物品存在数组的(0,0)项内,将(500-1000,0-500)存在数组的(1,0)项内,将(1000-1500,0-500)存在数组的(2,0)项内,将(1000-1500,500-1000)存在数组的(2,1)项内,将(1000-1500,1000-1500)存在数组的(2,2)项内……然后将地图里的所有物品按这个方式保存在二维数组里,物品移动时则更新数组。

到时候要取屏幕范围,就以屏幕中心坐标开始,除以500获得一个区块的坐标,然后取他周围的九个区块,这些区块内保持的物品实例肯定覆盖了整个屏幕。虽然会多出一些屏幕外的物品,但这点多余消耗是可以接受的。

这和使用四叉树的结果是相同的,都可以快速定位屏幕内物品,做到游戏中存在大量物体,但只要不同时出现在同屏,就不会耗费过多遍历性能的目的。

关于四叉树遍历可以参考衰人的日志:(http://wxsr.blogbus.com/logs/60788934.html

特殊情况应当使用特殊处理

子弹会穿墙,这是个经典问题。

现实的子弹是线性移动的,电脑中的却不是。子弹的移动一定是间隔进行的,而子弹的速度很快,体积小,墙壁薄的时候,就有几率正好跨过去导致碰撞检测失效。这其实是满经典的问题,像以前玩沙罗曼蛇,全部吃加速吃到一定程度就可以玩穿墙了,毕竟碰撞检测是一个高消耗的操作,能简化就简化,尤其是在飞行射击游戏出现大量子弹的情况下,采用复杂的判断逻辑实在不合算。

需要注意到,在设定好的环境里,子弹穿墙的几率实际上是很低的。这种游戏子弹是要能看到并躲避的,速度就不能太快。就算那子弹的确比较快,只要你墙壁别薄到看不到,一般也是穿不过去的。如果这两个条件都满足,我只能认为你游戏设计稍微有点问题。

好吧,说到解决方案,最彻底的当然是计算移动轨迹并判断是否和障碍物的边缘相交,这并不算困难,但是性能消耗会翻倍,仅仅是为了特殊状况,确实有这样做必要么?

如果游戏里所有子弹都是会穿墙的速度,这游戏基本就不用玩了。所以,能穿墙的只会是某些特定的高速弹。仅仅为了这个而使其它正常速度的子弹的碰撞判断降低性能,这个做法并不妥当,那实际上可以怎么做呢?

你只要将你的特定子弹尾部延长就可以,就是修改子弹素材,在尾部添加一条透明的尾巴并参与碰撞。虽然看起来是点,却是线。这样要想穿墙难度就高很多了。而这个延长部分是感受不出来的,因为它是高速弹,来无踪去无影,不可能抓得到尾巴。

步骤的对调可能大幅简化逻辑

当时是心血来潮想做个爆炸效果。就是那种哐啷一声一块玻璃被切成一片片散落的样子。例子可以参考FFX的战斗切换,以及DMC3关卡结束的切换动画。

这个效果其它部分都很简单,难点在于切割。碎裂的方式是随机的,首先是创建一堆随机的点,然后三点组合成三角形,问题就在于如何组合。三角形当然是不能交叠的,所以你需要将接近的点组合成三角形,而且保证它们不会叠在一起,问题就转变为“什么样的点才叫接近的点”。这个算法倒是在哪看到过,不过我不记得就是了……

查也查不到,所以我就找个了近似方案代替。这里关键的问题在于点的随机性,只要点不是随机的,组合三角形就可以用((0,0),(0,1),(1,0)),((0,1),(1,0),(1,1))这个约定的组合,然后保证随机的时候不会交叉就可以了。

首先是创建出不考虑随机的状况,差不多就像下面这样,平均切成矩形,矩形再分成两个三角形。此时顶点到三角形的组合规律是固定的。

把这个作为原始状态,再调整顶点的位置,可以看到,即使将各个顶点分开移动,每个顶点只要还在矩形范围内活动,三角形就不会交叠。

其结果就是这样,虽然不是完全随机,但基本可以符合要求。

除去必须在边缘上的点之外,中间自由活动的点的坐标可以这样简单地求出来

x = dx * (i + Math.random()) 
y = dy * (j + Math.random()) 

其中dx,dy是分割的小矩形的长宽,i,j是顶点的x,y序号。

换个思路,就有新的方向。先创建顶点再组合三角形,和创建三角形再调整顶点,难易程度就会完全不同。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

看后,简单并快乐 by xue gang

从业软件好几年了,很多都是business logic 方面的东东。看后,又感觉回到玩积木,画漫画,学数学的年代。

不错 by 吴 茜

根据需求选择技术是个很不错的方案。。。

几个问题 by Kraft Bai

第一个为何不用对应边匹配?这个确实不是碰撞问题
第二个可以用抛物线方程吧
后面2个处理确实很赞:)

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

3 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT