思考：移动中的碰撞侦测

CNBLOGS.COM的steeven已经开始讨论一些关于游戏的细节问题了：算法：移动中的碰撞侦测 ，我在这里也就他的问题讨论一下。

其实这个就是典型的图形问题（我不知道是不是该叫图形问题，哈哈，英文叫做graph problem）

对于在一个特定的GRAPH里寻找minimum spanning tree，可以使用kruskal's algorithm和prim's algorithm，寻找一个特定点到的最短路径比较著名的就是dijkstra's algorithm了（就是前一段去跟上帝讨论问题去了的那个家伙的算法），在这个算法的基础上有不少版本的延伸，我曾经在GOOGLE上查到过一篇一个中国的女工程师写的关于dijkstra的讨论，刚才查了一下又找不到了：（寻找一个GRAPH里的所有点的最短路径一般使用floyd或者warshall，floyd很有效，但是也是一种greedy algorithm，地图大了要计算的东西多了效率就不高了。

我觉得要找路径肯定不能是撞啦，那就是瞎子摸墙走，不能算是AI，我想比较普遍的做法应该是在制定范围内（就是以要移动的物体－坦克和鼠标点的另外一个地方画一个长方形）在这个范围内寻找最短路径，因为在地图制作的时候肯定有标尺，所以各个点之间的距离就是已知的了，那么只要算出来这个路径然后让坦克沿着路径走就可以了。

以前打CC的时候都会有编组的的机制，我想这个编组对算法的主要好处就是可以大大简化电脑的运算量，把整个一队作为一个单独的对象来考虑，然后一组都按照一个路线走，在这里就又涉及到network flow（这个应该叫做网络流量吧？）的问题，就是解决瓶颈。如果一大堆的坦克呼呼呼的前进，结果在途中要过桥，大家都往上挤就谁也别过桥了。我想主要就是两个办法，走，或者不走！走，就是在遇到桥的时候一部分走桥，然后另外一部分扩大搜索面积看看附近能不能绕道走，如果不能的话，那就只能不走！不走，就是等到网络中有了空闲流量的时候才通过。

写完上面的话我又仔细看了一下steeven的问题才发现我根本答非所问，他主要考虑的是如何避开大面积的物体，而我想到路径上去了。

因为在实际运动中主要会有两种障碍物，一种是建筑物，他们是死的，不会动。一种是其他的可移动物体。对于死的东西可以每次计算都考虑到路径的运算里，可是可移动的东西就没准什么时候会出现在路径中了，这时候我想就不需要把它考虑到路径的运算中。坦克都应该有一个侦测器来侦测是否可以移动到下一个位置，我想如果前方突然出现了一个障碍物，那么坦克可以1）等一下再走，因为在已知路径内出现的障碍物，肯定是可移动的物体，因为算出来的路径肯定是可以走的，如果不能走，那么就说明有飞来横祸了，呵呵，稍微等一下，等其障碍物移动开了就可以了。2）马上再重新计算新的路径。

我想在实际的运算中，肯定是几个算法几个方法一起上的，单独的解决办法都不能很灵活的移动。

我以上的方法都是基于一种方案就是把整个地图和所有物体都量化，形成一个巨大的网格，这样每个网格之间的距离就都是1。如果一点有一个障碍物，那么这点的两个对顶点的距离就是无限大。这样就能比较好的控制路径的运算了。不过我不知道在实际的运算中这样是否好用，因为地图太大了的话就什么情况都会出现了，譬如说如果让一个坦克从地图的左下角走到右上角呢？

所以最后的办法还是应该由几层的算法：dynamic programming->divide and conquer->greedy algorithm。这样才能比较灵活的实现吧。

我对AI没有什么研究，这个问题应该找兔子同学来看看，哪天把他找来：）