[编程经验] A星寻路技巧：不同大小角色的寻路

本帖最后由 sleep2death 于 2010-3-4 21:05 编辑

大家都玩过红警，星际争霸。当我们在使用Astar寻路的时候，有没有考虑过这些游戏是如何处理不同大小的作战单位的吗？较大的坦克，和较小的人类士兵他们的寻径路线是肯定不一样的，比如某些较窄的桥只能由体积较小的单位通过。

他们采用了一种叫做Brushfire（请用google，百度是搜不到的)的算法,将Grid上的每个网格赋予了一个clearence的值，就像扫雷一样：

这个值也就是该网格在这个方块区域内没有任何的障碍物。

那么下面的解决步骤就很简单了：
小物体的：

大物体的：

坦克的实际寻径路线如下图（只有值大于等于2的才能通过）:

下面是伪代码：
方法名: getPath
参数: start, goal, size

1. push start onto open list.
   
2. for each node on the open list
   
3.   if current node is the goal,
   
4.     return path.
   
5.   else,
   
6.     for each neighbour of the newly opened node
   
7.       if neighbour is on the closed list, skip it
   
8.       else,
   
9.         if neighbour is already on the open list, update weights
   
10.         else,
    
11.           if clearance(neighbour, capability) > size,
    
12.             push neighbour on the open list
    
13.           else, skip neighbour
    
14.   push current node on closed list
    
15.   if openlist is null, return failure

复制代码

我用AdvancED_ActionScript_Animation中A*寻路里的源码做了一些修改，大家可以看看。没做优化，仅仅是做个简单实现。