Archive

Archive for February, 2010

Grandpa SDK 0.7发布

February 25th, 2010 No comments

下载Grandpa SDK 0.7

Grandpa主页

主要修改:

  • Max插件能自动保存最后一次成功导出的设置
  • 添加IVertexStream接口,顶点数据分为静态和动态两个stream
  • 完善IEventHandler接口,支持任意用户自定义动画事件
  • 添加IProperty接口,用户可以在模型,部件和材质文件中添加自定义属性
  • 添加ISkin接口,支持GPU蒙皮

详情请见更新历史

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: