Archive

Posts Tagged ‘算法’

北京车牌摇号的概率计算

March 25th, 2011 No comments

根据“北京小客车指标调控管理信息系统”,也就是著名的北京缓解拥堵(或者北京还将拥堵)网站上公布的数据,11年1月至3月实际获得参与摇号资格的人数人别为11714页,18268页和24847页(每页16人),之所以只能精确到“页”是因为这个系统只告诉我们有多少页,我们只能一页一页翻到最后,看到最后一页有多少人才知道一共确切有多少人,我想这么干大概会耗尽我的鼠标的点击次数寿命,所以放弃了尝试的念头。

不过没关系,我们都用页来计算好了,也不需要太精确。前两个月中签的都是1100页,有理由相信后面每个月也都是这个数字。有意思的是2月和3月新增的参与摇号人数分别是18268-11714=6554和24847-18268=6579,这两个数字相差只有0.38%,看来非常符合等差数列的特点(如果不是有意控制人数的话),也就是说可以认为每月新增的摇号人数是固定的。

代码大概是这样的:

 

 

 

 

 

Read more…

Categories: 程序/算法 Tags:

zpack:一个简单的文件打包格式

January 18th, 2011 5 comments

最近实现了一个简单的文件打包格式

一向很喜欢简单高效的东西,所以非必要的加密,压缩功能一概欠奉。反正也开源了,用户很容易自行添加。

文件以文件名的hash作为检索,为了防止hash冲突的情况,除了用来建立hash table的主hash以外,索引表里还另外保存了两个用不同算法算出来的hash值。这样一来,读取包内文件时并不需要原始的文件名信息,只要根据输入的文件名算出来的3个hash值都和hash table里保存的相应值一致,就基本可以认定是用户所需要的。当然,对于32bit的hash来说冲突的情况实际上很少,而计算hash也有一定开销(虽然和磁盘io相比基本可以忽略),如果包内文件又很少,可以只比较两个,甚至一个hash值。 Read more…

Categories: 程序/算法 Tags:

D3D9的Pixel和Texel(续)

December 13th, 2010 No comments

前一篇只说了屏幕坐标和纹理坐标一一对应,也就是说没有缩放的情况。实际上有时候会需要把图素进行缩放后渲染,举个例子,把3×3像素的纹理(注意,不是整张纹理3×3,而是取一张纹理上3×3大小的一部分)渲染成屏幕上的4×4像素大小,如下图。和以前一样,红色的线框代表纹理像素的边界,灰色线框代表屏幕像素的边界,由于纹理被放大了,所以只有在图素边界处二者才是重合的。

这里有个不容易觉察到的问题,估计已经让很多程序员抓狂过,也就是放大后的图素的边界像素上会多出一些来历不明的颜色,放大倍数越大就越明显。实际上,这是采样到边界以外的纹理像素了。

Read more…

Categories: 程序/算法 Tags: ,

骨骼动画的数据压缩(二)

June 13th, 2010 4 comments

上一篇遗留了一个问题没有说完,就是关于绝对变换和相对变换。我们的骨架一般是以树形结构存储的,一个骨骼会有一个父骨骼(根骨骼除外)和若干个子骨骼。所以对于骨骼的变换我们可以存储在模型空间中的绝对变换,也可以存储相对于其父骨骼的相对变换,二者是可以相互转换的。

用相对变换形式存储的好处主要是便于拆分成不同类型的变换从而使动画插值成为可能;而保存绝对变换的好处首先是效率较高,因为在蒙皮计算的时候我们真正需要的是骨骼的绝对变换,如果保存的是相对变换就需要根据骨骼的父子关系先计算出绝对变换矩阵,每块骨骼都多出一个矩阵乘法的开销。另外直接保存绝对变换还能避免因为逐层相对变换引起的累积误差。

言归正传,我们继续来看动画数据的压缩,前文已经把200k的数据压缩到60k左右,还有办法继续压缩吗?

用过Max(Maya和XSI不太熟悉,但想来也应该差不多,下文只讨论Max)的同学会发现,虽然我们的动画定的是30fps的标准,但是美术实际摆放的关键帧要远远低于这个密度,对于简单的动画,某些骨骼可能在两秒的时间内只有3~4个关键,其它时间的骨骼方位实际上是导出时Max自动插值得到的。于是小算盘就开始打了,既然我们保存的骨骼关键帧大部分都是Max自动生成的,那么我们能不能只保存真正由美术摆放的关键帧,剩下的也象Max所做的那样自动插值出来呢?如果可以的话,无疑将再次大幅减小动画文件的尺寸。

Read more…

Categories: 程序/算法 Tags: , ,

骨骼动画的数据压缩(一)

June 12th, 2010 No comments

这里说的骨骼动画数据,是指美术用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…

Categories: 程序/算法 Tags: , ,

RTS游戏的行军算法

February 10th, 2010 No comments

这篇是03年写的,那时候还没有进入游戏圈,现在回想起来游戏里很多问题的处理比之前想象的要简单。

一提起游戏中的寻路,很多人就会想起A*算法. 的确,A*无疑是当前用的最多的寻路算法,在比较简单的地图上它的速度非常快,能很快找到最短路径(确切说是时间代价最小路径),而且使用A*算法可以很方便地控制搜索规模以防止程序阻塞.

关于A*算法的文章已经很多了,上google随便一搜就能找到好多,但是国内网友原创的似乎不是很多,建议英文不太差的爱好者上国外的网站查找相关资料,比如这个Amit’s Game Programming Information.

A*算法本身表述起来很简单,程序写起来也不难,两三百行轻松搞定.关键是要在代码优化上下功夫,这就很考验程序员的算法功底了.基本的思路一般都是以空间(也就是内存的占用)换取时间(搜索速度),另外还有一些地图预处理(包括人工的预处理和用程序预处理)的技术比如多级地图精度或者地图分区域搜索等等,但我今天要讨论的不是A*算法本身,关于这方面有兴趣的网友可以另外和我交流.

不管怎么优化,寻路总是一项非常费时的工作,并且工作量和地图的大小基本成线性关系(不限制搜索规模的前提下).现在的rts往往允许每方生产200个以上的移动单位,同时可能会有大量的移动物体需要寻路.如果同时选定100个单位点并向他们下达远程行军命令,假设每次寻路需要5ms(在复杂地图上,这个数值一点都不夸张,我是说在我的机器上),那么就需要0.5秒的时间在寻路上,也就是说整个游戏将因此停顿0.5秒.你受的了么?

Categories: 程序/算法 Tags:

算法基础–哈希表(hash table)

August 14th, 2009 2 comments

哈希表(hash table)是比较常用的数据结构,它能提供接近常量时间复杂度的数据插入和查找性能。哈希表的本质是利用一个哈希函数(hash function)将一个较大的取值范围映射到一个较小的取值范围,从而一方面节省了存储空间,另一方面又没有失去随机存取的性能。

举个简单的例子,比如我们手里有全班30个学生每个人的生日的数据表格,我要求快速的找出某一天有没有人,有哪些人过生日。最容易(或者说最笨)的算法是在表格里挨个查找,看谁的生日和指定的日期一致,显然这种算法是线性时间复杂度的,换句话说平均所需要的时间和全班人数成正比。

如果想快一点怎么办呢?可以事先把所有同学的名字填到一张有365个格子的大表里,每格代表一年中的一天,这样要知道某一天谁生日只要找到对应的格子,那天过生日的同学名字就在里面了。这个算法是常量复杂度的,就是说不管全班有多少人,我都能在几乎同样的时间里找到指定日期生日的人。

Read more…

Categories: 程序/算法 Tags: ,

三次样条曲线拟合

June 15th, 2009 4 comments

Spline曲线应用很广,在3d游戏领域,一般会被用在摄像机运动,骨骼动画压缩等方面。

Spline的生成一般是采用分段Bezier曲线拼接,这里有一个pdf文件,是我目前为止看到的关于spline生成和插值的最详细,最易懂的文档。

Spline拟合是另一个课题,也就是用尽量少的控制点,生成Spline曲线拟合给定的数据点,并把误差控制在一定范围以内。目前貌似还没有出现广泛采用的,特别有效又浅显易懂的方法。 附件里是这几天写的一个demo,采用了比较简单的算法,也就是只从给输入据点中挑选控制点,每次迭代添加一个误差最大的点,直到所有数据点的拟合误差都小于要求的值。 为了演示拟合的过程,按一次“Fit”按钮进行一次迭代,支持一次undo

spline

蓝色曲线是输入,红色曲线是拟合曲线。

下载demo

如果无法运行,你可能还需要microsoft.vc90.crt.zip

Categories: 程序/算法 Tags: