写点什么

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

2011 年 3 月 07 日

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

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

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

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

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

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

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

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

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

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

首先考虑简单的近似实现

老外的东西总是能有惊喜。老外的思路常常都很单纯,过度设计的情况很少见。不管怎么说,他们的经验还是要丰富一些的。虽然一个需求怎么都能实现,但细微之处的积累依然会产生大的变化。这次嘛,是关于一个同事在玩的 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 序号。

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

2011 年 3 月 07 日 21:532416

评论

发布
暂无评论
发现更多内容

让你的产品更懂世界:如何提升场景文本识别中的语言模型

华为云开发者社区

神经网络 文字 语义

“懂行人”携手互联网,创造未来无限可能

Geek_459987

你确定你会算数吗?老大说:你连这个都不知道还敢面试电商公司?

小Q

Java 学习 编程 程序员 面试

synchronized 是王的后宫总管,线程是王妃

Java架构师迁哥

官方活动 | 日更挑战(初阶)——七日更,挑战百元京东E卡!

InfoQ写作平台官方

活动专区 七日更

Java 并发编程:volatile能否保证数据的同步

码农架构

Java Java并发

需求管理的6个最佳方法

PingCode

项目管理 程序人生 敏捷开发

红着眼连续肝了一个月淦出的20w字的《Java核心技术总结》和3w字的《面试题总结》PDF文档,希望能够帮到你!

Java成神之路

Java 程序员 架构 面试 编程语言

一次资源泄露问题排查纪录

AI乔治

Java 架构 JVM 内存泄漏

ROS 机器人操作系统进阶实战

Geek_3cc3ec

Python 人工智能 学习 ROS

校园恋爱新技能:智慧琴房恋爱助攻手册

IoT云工坊

物联网 API sdk 智慧琴房 智慧校园

为了SpringBoot提交Tomcat执行,我总结了这么多

996小迁

Java tomcat 架构 springboot

看完这份文档我吊打了BATJ面试官,他问的我全都会:Spring+逻辑算法+MySQL+Java+Redis+并发编程+JVM+RabbitMQ等

Java架构之路

Java 程序员 架构 面试 编程语言

字节跳动总监亲自整理,在知乎高达5716赞的Java开发手记。

Java架构之路

Java 程序员 架构 面试 编程语言

9年技术面试官讲解:计算机专业应届生怎样写简历

Java架构师迁哥

Techo | 大数据专场报名盛启!12月20日欢迎莅临!

小小的一朵云

大数据 数据仓库 大数据架构

“懂行”为舟,助互联网驶向“新蓝海”

Geek_459987

我把2020年GitHub上最火最牛b的Java进阶教程和实战项目等整理成了一个PDF文档,免费分享给大家。

Java成神之路

Java 程序员 架构 面试 编程语言

5年Java开发经验,7面阿里历经千辛万苦成功斩获P7及Offer!

Java成神之路

Java 程序员 架构 面试 编程语言

万万没想到我也能挤进阿里定级P7,美团架构师总结整理的这份GitHub标星150K+的Java神仙笔记是我成功的关键。

Java成神之路

Java 程序员 架构 面试 编程语言

【变与不变】架构中的边界划定

soolaugust

编程 架构 设计

A Guide for Accidental Project Managers

Geek_ed0696

pmp project manager role of PMP PMP Certification greycampus

LeetCode题解:127. 单词接龙,BFS+生成所有可能新单词再匹配,JavaScript,详细注释

Lee Chen

算法 LeetCode 前端进阶训练营

升级redhat6的yum源替换为centos源

Bruce Xiong

在算力“沃土”上,种植互联网下一个奇迹十年

Geek_459987

朋友不讲武德急催我给他Java干货教程,我劝他耗子尾汁并丢给他一份GitHub上标星115k+的Java教程,他看了之后连忙向我道歉!

Java架构之路

Java 程序员 架构 面试 编程语言

太狠了阿里技术专家撰写的电子版JVM&G1 GC实战,颠覆了传统认知

Java架构之路

Java 程序员 架构 面试 编程语言

盘点2020 | 技术圈里的这些热名词

xcbeyond

微服务 DDD 金融科技 新基建 盘点2020

免费分享!GitHub标星15k的Java编程思想最新中文版,肝了一周整理成1539页的PDF文档!

Java架构之路

Java 程序员 架构 面试 编程语言

冒着被劝退的风险免费分享给大家一份阿里内部绝密《百亿级并发系统设计》实战教程。

Java成神之路

Java 程序员 架构 面试 编程语言

2020年第11期公有云性能评测:盛大云-华东实现“三冠”,百度云虎视眈眈

博睿数据

百度云 腾讯云 阿里云 公有云 华为云

演讲经验交流会|ArchSummit 上海站

演讲经验交流会|ArchSummit 上海站

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