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

Squall_Chua

我覺得他說的way point algorithm指的應該是
他在design那個map時就設好way point
換句話說就是要預設好所有可能的path
如果是醬的話
我覺得會造成更多的工作
如果以一個很大的map來看
可能還不如用A*都還比較能夠減輕負擔

tensaix2j

昨天拿starcraft 来研究。他们做的很微妙
他的 物件 重不会 overlap 的 而且，
就拿那张图， 中间那个被困的家伙， 一旦我把困住他的人拿开，
他自己还会知道 如何 绕道 去我刚点的 地方。。。

geekman

对，我说的 way point 就是在设计版图时就将所有可能的路线plot出来，当初研究Counter Strike 的 bot 时就有接触到。当然，要很好地运用way point， level designer的头脑就得很清醒。地形十分复杂的地方当然不可能傻到把每一个角落都plot出来。你可以只plot出重要地点的路线，然后到了该地点再用其他algo来抵达到真正的目的地，这也是为何我之前就提出搭车到地点再走路的比喻。做游戏的人就是得头脑灵活，善于在适当的地方使用适当的技巧，那才是一流的game designer。其实way point工作多只是在设计版图时多一层功夫，在实际游戏运行时可省下的时间和运算资源绝对是值得在开头时所花费的那一份功夫的。

至于那个一组物件一同移动但是不会相撞，可以使用Formation的概念，例如规划一个grid，然后每个unit都乖乖的呆在自己的格子里，当整组移动时，那个看不见的grid也一起移动，这样就可以让部队不互相重叠的移动。然后呢，再次的强调：使用了Formation grid， 就并不表示你不能配搭其他algo，比如如果你要让部队移动时表现得比较生动，就可以把grid的限制放宽，让unit可以和其他unit稍微发生碰撞，不过他们会做出互相推撞的动作后又再回到自己的范围，然后在停止时再回到自己既定的位置，这样就会让部队显得更活灵活现，就好像Age of Empire 2那样。

再不然就是用push-pull方式，有用过Sun 的ONE IDE for Java 的应该会看过一个java applet， 里面有一组格子，以类似tree的link连接起来，当你拖动其中一个时，其他的格子也会被拖着走，或者被推开，总之每个格子之间都会维持一定的（可伸缩的）距离，这也是一个可用的方法 - 也就是每当你的部队移动一步，就得进行一次push-pull运算。

tensaix2j

grid 的问题就是， 一个物件move from grid to grid 的时候，
就难免会有overlap 的状况。。

例子
一个 物件A 从 ２，５ 移着去 ２，８
另一个物件B 在 ２，７。。。你移动A时，就会穿过B

除非 你每一步都 check， 不过还是有overlap 的可能性
因为 当你move A，check ２，７时， B可能才刚刚要踏入B，但还没完全踏入， 所以系统看２，７是空的，就把A 给带到２，７，这时B
也踏入 ２，７， 那么就可能 overlap 了

sson

原帖由 geekman 于 14-5-2008 01:16 PM 发表
目前最 in 的做法应该是使用 way point 吧。任何一个物件只要一旦和最接近的 way point node 接触，就可以在最快，消耗最少计算资源的情形下找到最接近目的地的 way point node， 然后再通过一般的 collision route  ...

不解何以说路标发是最 in ？
可否说明？

原帖由 tensaix2j 于 14-5-2008 10:04 PM 发表
就拿回 RTS 的例子，
比如说， 我 选一群 物件， 然后 在选 一个 目的地。。

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

路标方法的好处就是在创建地图是（无论是动态 dynamic 还是预先设计）都可以在游戏开始前建立路标。

在你的情况，小章鱼不清楚他们是怎么实现的，
不过小章鱼的做法是在选中的物件中选一个当队长，做一次 A*，其它跟队长走。

原帖由 tensaix2j 于 15-5-2008 12:04 PM 发表
grid 的问题就是， 一个物件move from grid to grid 的时候，
就难免会有overlap 的状况。。

例子
一个 物件A 从 ２，５ 移着去 ２，８
另一个物件B 在 ２，７。。。你移动A时，就会穿过B

除非 你每一步都  ...

实际上一个游戏很难这样把所有的技术分开来，以为每一个都息息相关。
在设计游戏后，经过分析，决定要使用什么类型的数据结构很重要。

这种情况下，一般如果两者的速度一样，基本上不会感觉他们 overlap ，以为一个出一个进，大体上都占据一半罢。
另外的做法就是在移动的时候注册 2 个 Tile（这里实际上技术叫 Tile ，不是 grid)

所以之前小章鱼有说可以用游戏的设计（关卡、规则）去限制。

小章鱼喜欢的做法是在移动的时候使用 grid 来取舍周围的动态物件，然后做碰撞（反正本来就要做的，物理模拟什么的）
这样就可以有比较真实的运动效果。


不过一般市面上比较“高级”的游戏，AI 都采用混合式的演算，
不觉得 A* 加上路标可以更灵活吗？
除了 A* 还有很多 path finding 的方式。
更有用猜的方式（走迷宫），小章鱼在做 pacman/tank 类的游戏经常用。

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

tensaix2j

原帖由 sson 于 15-5-2008 12:42 PM 发表
这种情况下，一般如果两者的速度一样，基本上不会感觉他们 overlap ，以为一个出一个进，大体上都占据一半罢。
另外的做法就是在移动的时候注册 2 个 Tile（这里实际上技术叫 Tile ，不是 grid)

不是，现在的情形是 一个根本不动。，另一个则穿越它来到达戈壁的格。。

            A       B

             ----- B ------> A

除非每跑一格就在计算 intermediate target x and intermediate target y,
。。而不是直接带到 final target x and final target y
因为 move时是increment x跟y 来到 target x，y

sson

不移动的时候就占用一个 Tile ，当成障碍物来处理就可以啊。
活用游戏里的数据。

这里使用了Tiles, tile 基本上就是地图的每个格子（2D游戏为例）

可以先去了解了解各种数据结构的用法。

tensaix2j

那如果你的物件只跑到半个tile的话呢？
因为不是 full tile 的游戏，就是你的物件不是一格格tile increment的。。而是x y (更小的pixel tile)

因为通常RTS虽然有tile
但movement 却是以更小格来increment的。。

问题是你什么时候才写你的 tile（x，y）as occupied

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

tensaix2j

如果 movement 是以tile 格的进度，那当然没问题。。

但 movement是以 ２ pixels 的进度 （例子）。。

尤其是两个 物件 正要进入一格时，（因为此时此格是空） 突然发现

彼此的 存在  ，那 那格 归谁 occupied？

sson

不要忘记了你的物理运算，凡是有移动，就有最起码的物理模拟。
所以小章鱼说了，一定要管理好游戏数据，然后善用它们。
而且两个物件进入同一格的情况，真的存在吗？下面有简单的伪代码

for each(object in Objects){
    object.move()；
}

也就是说真正进入的是第一个，第二个移动时第一个已经在上面了。当然如果你用多线程可能就不一样了，不过控制得好，基本原理没差。
而移动，目前想必没有游戏是移动一个 tile 的吧，就是移动一个 tile 的也会做个过渡移动。
如何移动就看你的物理模拟了。



另外，推荐一个入门游戏， Pacman
其中用到了 tile ， 也用到了 grid ，
敌人又有 4 个，各个又有不同的特性，对初步 AI 研究很不错。
做好了，可以对数据结构和管理有很大的帮助，也可以理解到 AI 和游戏数据间的关系。

2D 中 grid 是一种简单好用的数据结构，用来取舍物件和方便，其有建立、更新快的优点，缺点就是耗记忆。
tile, quadtree, scene graph 等有不同的作用


[ 本帖最后由 sson 于 15-5-2008 03:29 PM 编辑 ]

tensaix2j

原帖由 sson 于 15-5-2008 03:24 PM 发表
而且两个物件进入同一格的情况，真的存在吗？下面有简单的伪代码

for each(object in Obj ...

其实也是看你什么时候决定把该tile assign to 那个物件，
。。到底是只要一碰到tile，还是完全进入tile 后。。。

tensaix2j

你的pacman 里， 敌人跟敌人是允许overlap 的吗？

sson

原帖由 tensaix2j 于 15-5-2008 04:17 PM 发表
其实也是看你什么时候决定把该tile assign to 那个物件，
。。到底是只要一碰到tile，还是完全进入tile 后。。。

一般就是碰到就算，因为我们知道下一步它就会进入（程式是你编的嘛）
一般容易的解决就是做个简单的演算让第二个走进邻近的 tile 咯。

Pacman 可以做可以 overlap 的，也可以做不 overlap 的。
不过主要是去理解 AI 是怎么运行的， 数据结构对 AI 的重要性等……
顺便一提，
Pacman 中 4 只鬼的的不同是
1. 到处乱走
2. 会去找玩家
3. 避开玩家
4. 看到玩家就追上去

tensaix2j

有一点不同就是， 一碰到就算的话， 很有可能一个 物件同时霸占四个 tile ，  

或是说， 你 只要一个pixel 碰到， 你就assign 那个tile 给他，但 它原本的 tile 就要release 。。。也就是说， 他现在有 ９９％的pixel 不在它belong 的tile里。。 它身在的新tile 只有 1 ％ 的pixel在新tile里头（例子）。。。

那么另一个物件，及有可能跑去它刚release的tile， 但 有 ９９％的pixel还在里头。。。也就是说，很有可能会 overlap 到另一个刚进入 它刚离开的tile 的物件。。


－---话题二-------------------------------

好象瞒有趣的。。

可以说说你用过哪些 AI呢？
ANT， Hill climbing, simulated annealing。。？
还是一些比较 heuristic 类的。。

sson

同样的道理，它刚里开，所以其他的也不会马上占据它刚离开的位子，
也是慢慢的走过去，所以视觉上也不会 overlap 。
而允许它占据多少个 tile 是由你的游戏规则来决定。
小章鱼过往的都是一个。

对不起，小章鱼是井底蛙，你说的小章鱼一个都不懂。
小章鱼做的 AI 都是简单的，不像那些“高级”游戏宣传的 AI 有人性、会学习什么的。
唯一做过会“学习”的，应该是走迷宫吧，探索过的不再去（如果这个也算“学习”的话 ）

tensaix2j

例子，

假设我的tile map 如下
[ 1  ]  [ 2  ]  [ 3 ]
[ 4  ] [  5 ]  [  6 ]
现在
A 在 ４ 要去 ６
B 在 ５ 要去 ２
[   ]   [   ]  [  ]
[ A  ] [  B ]  [   ]

B 的头顶move１pixel 碰到了２，所以 B是被当作２的霸主,５现在变空，但
B 的身体大部分还留在 ５ ， A 正好要经过 ５，从４ 到 ６。

可是对 A 来说， ５ 是空的。。 那么它就不闪了， 但在此某时就碰到了 B 的躯体。。。
-----------------------------------------


还不错呀.
那请问小鱼还做过哪些游戏呢？

sson

呵呵，看来你是想多了些许
这情况下，咱们可以看看游戏画面的设计，
如果游戏是正倾斜或全倾斜的话，就不存在这问题了，因为有前后遮挡关系。
A 一定会遮罩了 B ，所以视觉上碰到了 B 的躯体是合理的。

可是如果游戏是鸟瞰图方式的话，也有方法创造合理的视觉效果。
譬如 A 或 B 的速度恒一致或比 B 慢，那么 A 永远比 B 慢起步，所以身体重叠也就不明显了，
视游戏的设计，或许可以忽略这问题。
如无法达到要求，也可以让 B 占据 2 个 tile，那么 A 移动时绝会等待 5 闲置后才开始移动，或绕过。
不过小章鱼比较喜欢占一个 tile ，然后在移动时做个取舍，取舍后再对取舍结果做个碰撞，
（不过现在不酱做了，反正数据有了，结构也有了，直接取舍就好，何必多个 tile 的限制）
酱 A 就会移动直到轻碰 B 就停下等待 B 通过，看起来就像让路一样。
当然 A 也可以避开 B 些许而行。

不要认为取舍在游戏中会很耗操作时间，比较起来远比做简单的碰撞快多了。
当然前提是已经管理好数据，和应用合理的数据结构。


嗯，记得以前似乎有提过，小章鱼多是做 puzzle 类的游戏，动作类还蛮少的。
属于动作类的游戏，因该多是像 Pacman 或 Tank 的吧。


你在计划什么游戏呢？可方便分享？
之前未完成的游戏又有哪些？不如开个帖大家讨论讨论，合力完成。

tensaix2j

另一个问题， A 如何知道饶道
假设用回同个tile map例子
  [1  ] [2  ] [ 3 ]
  [A  ] [B  ] [ 6 ]
  [7  ] [8  ] [9  ]
A detect 到，５ 有东西， 那他是怎么知道现在该往 ７ 还是１走。
如果每到一个tile都给它一次计算 path finding 会不会很慢。。

而且，如果A 是从 ４ 去 ３ 的话，
你看到他的movement 会不会怪怪的。。因为他在４ 的时候
他被安排往 ２ 走在被安排往 ３走。。。instead of 一条直接的斜线(４ 到３)

------------------------------------------------

我一直围绕RTS 的问题，就大概可以猜到我想尝试写RTS。。
之前未完成的 有很多各种各样的。。很多都是一时兴起写的。
做到半途。。然后就不了了之。。。

例如这个 射击游戏。。 http://chinese3.cari.com.my/myfo ... 4783&extra=page%3D1
这个网络百万富翁。。
http://www.facebook.com/apps/application.php?id=7785129182
这个论坛宠物
http://bluecapstudio.popsg.com/t ... omic/create_pet.php
还有这个 ajax小玩意
http://www.po psg.com/myfav/public/main
(把空格拿掉)

还有很多 flash 的casino游戏
还有一些用 gamemaker ，vb写的小 puzzles，.....。

还有很多我不记得了。

小鱼是freelance？
还是在游戏公司？
还是业余的？

[ 本帖最后由 tensaix2j 于 16-5-2008 11:53 AM 编辑 ]

sson

嗯，其实当你点击 A ，然后选目的地时，一定会做一次 path finding 吧？
不然你怎么知道 A 要走 4 --> 2 --> 3
而这 path finding 的结果 4 --> 2 --> 3 就成为了 A 的 way points
A 就顺着走，有物体阻挡（之前提到的）就避开，然后再走回未达到的 way point
至于如何避开，就看你的决定了（不过不要忘了设定限制，不然越走越远哦），小章鱼比较懒，一般用猜（就是随便选一个啦 ）
所以 path finding 只做一次罢。

而运动方向的问题，一般 tile base 的游戏就用 2 种， 8 方位和 4 方位
4 方位看起来比较生硬，不过很合适 TBS 游戏
8 方位就比较灵活， RTS 常用



另外工作问题，小章鱼都是
还有哦鱼儿和章鱼是两码事

tensaix2j

可是， 若障碍不存在的话，
你是否会看到那个物件 先往diagonal 路线跑在往horizontal 或 vertical 路线跑。。。。
-------------------------------

anyway 我刚完成了试验的第一步。。。 还没想怎么去 optimize 它。。。
有兴趣研究的可以下载来看看。。。我有package 一起它的interpretor

下载


那小章鱼的游戏是手机游戏吗？

[ 本帖最后由 tensaix2j 于 17-5-2008 03:35 PM 编辑 ]