上一篇遗留了一个问题没有说完，就是关于绝对变换和相对变换。我们的骨架一般是以树形结构存储的，一个骨骼会有一个父骨骼（根骨骼除外）和若干个子骨骼。所以对于骨骼的变换我们可以存储在模型空间中的绝对变换，也可以存储相对于其父骨骼的相对变换，二者是可以相互转换的。
用相对变换形式存储的好处主要是便于拆分成不同类型的变换从而使动画插值成为可能；而保存绝对变换的好处首先是效率较高，因为在蒙皮计算的时候我们真正需要的是骨骼的绝对变换，如果保存的是相对变换就需要根据骨骼的父子关系先计算出绝对变换矩阵，每块骨骼都多出一个矩阵乘法的开销。另外直接保存绝对变换还能避免因为逐层相对变换引起的累积误差。
言归正传，我们继续来看动画数据的压缩，前文已经把200k的数据压缩到60k左右，还有办法继续压缩吗？
用过Max（Maya和XSI不太熟悉，但想来也应该差不多，下文只讨论Max）的同学会发现，虽然我们的动画定的是30fps的标准，但是美术实际摆放的关键帧要远远低于这个密度，对于简单的动画，某些骨骼可能在两秒的时间内只有3～4个关键，其它时间的骨骼方位实际上是导出时Max自动插值得到的。于是小算盘就开始打了，既然我们保存的骨骼关键帧大部分都是Max自动生成的，那么我们能不能只保存真正由美术摆放的关键帧，剩下的也象Max所做的那样自动插值出来呢？如果可以的话，无疑将再次大幅减小动画文件的尺寸。
Read more…
这里说的骨骼动画数据，是指美术用Max，Maya或者XSI之类的3d工具制作的角色动画，通常要导出成引擎可以读取的特殊格式，为游戏所用。对于目前越来越强调动作感的网络游戏来说，动画资源占整个安装包尺寸的比例在不断上升，动画数据的压缩也在变得原来越重要，更不用说采用大量实时渲染过场动画的次世代Console游戏了。
每个引擎都有自己独特的动画文件格式，但里面的内容都大同小异。所谓动画，就是一系列关键帧的集合，每个关键帧可以描述了角色整个骨架的完整姿态信息，也就是每一块骨骼在3d空间中的位置和方向。
假设我们有一个包含50块骨骼的骨架，采用30fps的帧率，一个长度为两秒的动画需要占用多大的空间呢？我们来计算一下。我们知道空间的方位可以用一个矩阵来描述，一个矩阵包含4 x 4 = 16个浮点数，也就是64字节；我们有50块骨骼，那么每个关键帧就需要50 x 64 = 3200字节，另外关键帧还需要一个4字节的时间值，那么就是3204字节；两秒的30fps动画一共包含60个关键帧，于是可以算出最终的大小是3204 x 60 = 192240字节，不到200k的样子。这就是未经压缩的数据大小，当然这里忽略了一些诸如骨骼名字之类的信息，和我们要讨论的动画压缩关系不大，就不算在内了。
Read more…
这篇是03年写的，那时候还没有进入游戏圈，现在回想起来游戏里很多问题的处理比之前想象的要简单。
一提起游戏中的寻路,很多人就会想起A*算法. 的确,A*无疑是当前用的最多的寻路算法,在比较简单的地图上它的速度非常快,能很快找到最短路径(确切说是时间代价最小路径),而且使用A*算法可以很方便地控制搜索规模以防止程序阻塞.
关于A*算法的文章已经很多了,上google随便一搜就能找到好多,但是国内网友原创的似乎不是很多,建议英文不太差的爱好者上国外的网站查找相关资料,比如这个Amit’s Game Programming Information.
A*算法本身表述起来很简单,程序写起来也不难,两三百行轻松搞定.关键是要在代码优化上下功夫,这就很考验程序员的算法功底了.基本的思路一般都是以空间(也就是内存的占用)换取时间(搜索速度),另外还有一些地图预处理(包括人工的预处理和用程序预处理)的技术比如多级地图精度或者地图分区域搜索等等,但我今天要讨论的不是A*算法本身,关于这方面有兴趣的网友可以另外和我交流.
不管怎么优化,寻路总是一项非常费时的工作,并且工作量和地图的大小基本成线性关系(不限制搜索规模的前提下).现在的rts往往允许每方生产200个以上的移动单位,同时可能会有大量的移动物体需要寻路.如果同时选定100个单位点并向他们下达远程行军命令,假设每次寻路需要5ms(在复杂地图上,这个数值一点都不夸张,我是说在我的机器上),那么就需要0.5秒的时间在寻路上,也就是说整个游戏将因此停顿0.5秒.你受的了么?
哈希表（hash table）是比较常用的数据结构，它能提供接近常量时间复杂度的数据插入和查找性能。哈希表的本质是利用一个哈希函数（hash function）将一个较大的取值范围映射到一个较小的取值范围，从而一方面节省了存储空间，另一方面又没有失去随机存取的性能。
举个简单的例子，比如我们手里有全班30个学生每个人的生日的数据表格，我要求快速的找出某一天有没有人，有哪些人过生日。最容易（或者说最笨）的算法是在表格里挨个查找，看谁的生日和指定的日期一致，显然这种算法是线性时间复杂度的，换句话说平均所需要的时间和全班人数成正比。
如果想快一点怎么办呢？可以事先把所有同学的名字填到一张有365个格子的大表里，每格代表一年中的一天，这样要知道某一天谁生日只要找到对应的格子，那天过生日的同学名字就在里面了。这个算法是常量复杂度的，就是说不管全班有多少人，我都能在几乎同样的时间里找到指定日期生日的人。
Read more…
Spline曲线应用很广，在3d游戏领域，一般会被用在摄像机运动，骨骼动画压缩等方面。
Spline的生成一般是采用分段Bezier曲线拼接，这里有一个pdf文件，是我目前为止看到的关于spline生成和插值的最详细，最易懂的文档。
Spline拟合是另一个课题，也就是用尽量少的控制点，生成Spline曲线拟合给定的数据点，并把误差控制在一定范围以内。目前貌似还没有出现广泛采用的，特别有效又浅显易懂的方法。 附件里是这几天写的一个demo，采用了比较简单的算法，也就是只从给输入据点中挑选控制点，每次迭代添加一个误差最大的点，直到所有数据点的拟合误差都小于要求的值。 为了演示拟合的过程，按一次“Fit”按钮进行一次迭代，支持一次undo
蓝色曲线是输入，红色曲线是拟合曲线。
下载demo
如果无法运行，你可能还需要microsoft.vc90.crt.zip
续上篇。前面有4个小问题没有解决。具体的问题可以在上篇搜“子问题n”
这实际上是一个寻路问题，最简单的用一个广度优先搜索就可以找到最短路径。从角色当前位置开始，每次向所有可能方向展开一层，如下图直到扩展到目标位置。根据节点的父子关系能反推出移动步骤。如下图
Read more…
只有算法，没有代码，希望不会编程的也能看懂（俺每次都这么说，但结果每次都很受伤……）
推箱子游戏大家都玩过吧，在封闭的关卡里分布着若干箱子，玩家控制主角把所有箱子推到指定位置即可过关。
以下是关于游戏规则的一些表述：
- 关卡中的每一格要么是墙，要么是空地
- 主角和箱子只能呆在空地上，不能穿墙
- 主角不能穿过箱子
- 箱子的目标位置在空地上
- 箱子数量和目标位置数量相等（但每个箱子并不和唯一的目标位置一一对应）
- 主角只能往前推动箱子，不能向后或向侧面拉箱子
这是个典型的递归/回溯（好像是这个字吧）搜索问题，栈数据结构的典型应用。和算法课上常常举的老鼠走迷宫的例子差不多，只是一些细节上稍稍复杂一点。
Read more…
以前一直不知道开平方是可以手工计算的，直到昨天晚上心血来潮开始看别人毕业的时候不要被我收藏的《数学手册》 ，BTW是77年出版的，比我还老！
是这么算的：
