游戏编程，技术讨论 第五章 ： unit design

tensaix2j

前言
-------
这个贴主要是讨论游戏编程的一些应用技巧，演算法（algorithm），还有设计（design）。
但讨论的同时，为了增加趣味，我也有一边做一个小小的RTS 游戏 之所以可以把所讨论的东西 implement 出来。。 希望有兴趣的朋友可以一起参与。。


目录
====
第一章： Collision Detection  #1
第二章： Route Finding         #15
第三章 ：Fog of war             #41
第四章 ：Terrain design         #76
第五章： Unit design             #107.


小游戏的进度：
----------------
以下链接下载 prototype------
Prototype- Rev 11. (340kb)


戳图：
prototype - rev_11






【第一章】： # collision detection

相信 有写游戏 的人 都会遇到的。。。
你们 都用 什么 algorithm 呢？

倘若， 一个 game 的 stage 有 100 个 物件，  任两个物件 collide都要 trigger 一个 function （objA， objB）
那 你们 check for collision among 这 100 个 物件 是否 loop 了  100C2 = 4950 次, 还是有更好的方法呢？

[ 本帖最后由 tensaix2j 于 30-10-2008 12:18 AM 编辑 ]

vicktchong

collision detection 有很多方法
最快的是 sphere collision
最准确的是 k-dop
game 通常用 sphere collision..
因为会比较快。。
100 个 detection 的话。。
就要加入其他方法配合哦！！

文世杰

可否解释一下什么是collision detection ？

tensaix2j

http://www.gamedev.net/reference/articles/article1234.asp

这个是我搜索到的资料关于 sphere collision。。
但还没进入这个sphere collision 演算前， 你要选其中两个物件，out of 100 个物件 来用 sphere collision to detect 这两个 物件是否 collide 。。那是怎么个 loop 法？

geekman

要加速collision detection，你可以使用 scene graph （3D环境）来判断那一些物件在你的判定范围里面，如果距离太远，就不必进行collision test。或者如果你的游戏并没有运用scene graph （例如2D游戏），你可以直接测试该物件和你的距离（其原理和sphere collision相同）。
举例（2D point）：
Object objList[100];
point myLocation;
int myRangePow2 = 16; //由于是2D，可以直接使用int，实际测试距离是4单位，不过为了节省时间，我们直接使用2次方，即16单位，节省计算平方根的时间

for(int i=0; i<100; i++)
{
  if(getDistance(myLocation, objList[ i ]) <= myRangePow2)
  {
      doCollisionDetect();
  }
  else
   {
      //nothing to do
   }
}

int getDistance(point myLocation, Object obj)
{
   //Location 也是point, pow(x, y) = x^y
  return ((myLocation.X - obj.Location.X), 2) + pow((myLocation.Y - obj.Location.Y), 2);
}
直接使用power of 2 除了可以节省计算平方根的时间之外（计算平方根十分耗时的，而且也必须使用浮点运算，使用2次方就不必使用float 或double， 可以直接使用int），也可以解决负数，因为任何负数经过power of 2 之后就会变回正数，节省了一个Math.Absolute()
的呼叫。

*在3D环境，就得加上Z-component 的计算。

**以上pseudo code并没有经过求证，可能有bug存在。

话说回来，你并不需要计算所有object之间的collisiaon 吧？一般游戏都只计算player和enemies之间的碰撞。就拿个射击游戏来说，你只需计算Player against enemies and enemies' bullet， 以及player's bullets against enemies，就足够了，很少会必须计算到100个物件中的每两个物件的碰撞测试，就看你如何optimize你的测试条件罢了。

[ 本帖最后由 geekman 于 7-5-2008 02:22 PM 编辑 ]

tensaix2j

我还没写啦，只是 搭bus时，突然 有所 思考。。。

我是说 如果  这“100 个 物件任两 个碰撞的话”。。。

例如 那种 real time strategy game leh

[ 本帖最后由 tensaix2j 于 7-5-2008 02:49 PM 编辑 ]

geekman

相信那些RTS都是使用 scene graph 来判定距离， 然后才计算碰撞的，其实计算4950次距离并没有你想象的那么耗时，就算每计算一次距离需要消耗1000个clock cycle（这是很夸张的数字，一般上像我之前所写的那种运算，顶多十多个cc就算很不efficient了）， 一台1GHz的电脑每秒有1024（KHz) x 1024 (MHz) x 1024 (GHz) 个 clock cycle（请自行计算那是多少，太多数目字会让我头晕 ），4,950,000个clock cycle 根本是湿湿碎。。。而以现今科技来说，1GHz 的电脑已经算过时了，还双核心 / 四核心的咧。。。

sson

嗯，使用圆的方程来判断是很快，不过总不能整个游戏里的咚咚都这样，虽然目前的电脑是很快，
不过FPS 30 也很耗资源了，不要忘记游戏不只是碰撞测试罢了。

以小章鱼的个人经验来说，圆的判断一般是用在两个物体的碰撞可能性很高的情况下，如果圆的判断成功再依需要使用其它更精准的判断式。

在物件取舍的时候，一般可以用四叉树（2D），或八叉树（3D），2D 中也可以用 grid。

tensaix2j

原帖由 sson 于 7-5-2008 05:29 PM 发表
嗯，使用圆的方程来判断是很快，不过总不能整个游戏里的咚咚都这样，虽然目前的电脑是很快，
不过FPS 30 也很耗资源了，不要忘记游戏不只是碰撞测试罢了。

以小章鱼的个人经验来说，圆的判断一般是用在两个物体的 ...

四叉树 = recursive partitioning?

tensaix2j

对了， 如果 有什么 值得 分享 的 algorithm
欢迎 指教。。。

tensaix2j

用 tree 的话， 差不多也要 n log n   。。。

sson

原帖由 tensaix2j 于 7-5-2008 06:21 PM 发表
四叉树 = recursive partitioning?

不晓得是不是 recursive partitioning， 小章鱼的 E 文不行……
四叉树是一种数据结构，用在游戏中就是把场景一分为四，一直细分到“满意”为止。
不过有更新慢的缺点。

原帖由 tensaix2j 于 12-5-2008 11:45 AM 发表
用 tree 的话， 差不多也要 n log n   。。。

你是说四叉树、八叉树？
需要一对一的情况也是会有，不过那可能性很小了，加上游戏的设计（关卡、规则）去限制，可能性就更小了，基本上 == 不可能。


tensaix2j 你之前的游戏都是一对一做碰撞测试的？

[ 本帖最后由 sson 于 12-5-2008 06:06 PM 编辑 ]

文世杰

什么来的？

tensaix2j

。。。.很惭愧的说， 我以前的做法都是 O（n^2）的。。
所以想知道有什么好方法。。。更惭愧的是， 还没写过一个完整的游戏。。。所以 想先了解方法， 在去写写看。。。。

tensaix2j

【第二章】， # Route finding

倘若，一个 game 里， 你要 先选择 物件， 然后再 点击 目的地， 你选择的物件就会 自己找 路到 目的地。。。 遇到障碍要绕过。。。 你们会用什么 algorithm 呢？

你们会 如何 配合 collision detection 来知道 障碍的存在， 然后绕过障碍呢？

[ 本帖最后由 tensaix2j 于 14-5-2008 08:51 AM 编辑 ]

geekman

目前最 in 的做法应该是使用 way point 吧。任何一个物件只要一旦和最接近的 way point node 接触，就可以在最快，消耗最少计算资源的情形下找到最接近目的地的 way point node， 然后再通过一般的 collision route finding 去到正确的目的地点（如果 level designer 够聪明，而且不偷懒，甚至可以把 way point 做到尽善尽美，那就根本不必使用一般的 path finding  了）。使用 way point traveling 的时候是不必担心和场景物件的碰撞的，只需担心和会移动，并且在你目前接近的 way point node 附近的物件的碰撞罢了。

可以把 way point 系统想象为马路， node 就是各个路口，way point traveling 就是搭车上路，到了最接近的路口就下车，自己走路到目的地，如果马路能够直接通到家门口，就不必走路了（path finding）。

[ 本帖最后由 geekman 于 14-5-2008 01:22 PM 编辑 ]

tensaix2j

我的障碍是dynamic 的， 我的 way point 也必须dynamically 生产吗？

而且，如何 不碰撞任何障碍物的情况，绕道移动你的物件去那个waypoint

geekman

不必，如果你的way point设定得适当的话（不太疏，也不太密），你可以只检查你的下一个node的附近的物体（或者包括目前的node和前一个node，视乎情况而定），因为你是朝向下一个node前进的，所以2、3个node之后的东西你目前根本不必担心碰撞。这样你就可以省下很多时间。

可否形容以下你的障碍物是如何的dynamic的呢？如果你打算采取vector prediction，就可以避开移动中的障碍物。方法就是观察对方的移动方向和速度，计算出它下一个frame的所在地点，然后避免把你的目的地设定在会和它碰撞的地点，例如以某个角度回转避开它（赛车和空战游戏就多采用这种移动方式）。

Squall_Chua

傳統的path finding algorithm
A* algorithm
不過太浪費resource了
雖然可以直接找出整條path

tensaix2j

就拿回 RTS 的例子，
比如说， 我 选一群 物件， 然后 在选 一个 目的地。。

这群 物件 必须 不collide to each other 的状态， 抵达 那个目的地
因为 你的 目的地是 即时 生成的 ，你要怎么implement 你的 way point 的 algorithm ？

A* algorithm 是 找最短的途径 out of 一堆的可能性的途径。。。 而且，还要given 每个node to node 之间的 cost 。 在加一些 heuristic 。
这个例子的是 不管 是不是最短。。反正不碰撞然后到达就好。
重点是不collide。。