【A*算法】如何描述物体的形状，坦克大战BOSS寻路

    比如说，在FC游戏 【坦克大战】 想要加入一个超大的BOSS，如何给这个BOSS寻路呢？

    首先来看一下这个BOSS的特点：它的体型比普通坦克大得多，占据了4个单元格。所以，我们不能把前一期的A*算法的代码直接套在它身上，因为之前的代码默认了物体的形状就是占一个单元格。

    那么该如何调整代码呢？

    很简单，将任何需要寻路的物体都成质点，只有在碰撞检测时才需要用到物体的形状信息。

    所谓碰撞检测就是，检测物体在某个位置时是否会与障碍物发生碰撞。

形状的表示

    首先说明一下地图坐标系，以左上角那个单元格作为原点，向右为x轴正方向，向下为y轴正方向。这个不是固定的，随便取都可以，关键看你的爱好。

    因为上面的BOSS坦克占据了四个单元格，所以，我们就可以用四个坐标来表示它的形状了。这四个坐标是相对坐标，相对于物体的质点，因为物体在寻路时，当前位置是会改变的，但是它的身体的各个点相对于质点的坐标却是不变的。

    质点可以随便取，物体身上的点，不是物体身上的点都可以，我们只是需要一个坐标原点来描述物体的其他点而已。

    比如说，我们取上图中BOSS坦克的左上角单元格作为质点，则可以用 (0, 0), (1, 0), (0, 1), (1, 1)来表示该物体。

碰撞检测

    知道了物体的形状，那么需要使用它的形状信息来修改原来的A*算法代码。

    只需要修改一处就够了，非常简单。

    下面这个函数是检测某个点是否有效点的函数，也就是判断物体是否能移动到该点，能移动的条件是该点在地图内，且该点是可以通行的（值为0）。

     现在只需要利用物体的相对坐标求出物体的所有点的绝对坐标，并判断地图上该点是否有效就行了。也就是，point是质点的坐标，质点坐标加上形状中各个相对坐标就得到了物体上那点现在的绝对坐标。

    只要物体上有一点发生了碰撞，则整个物体就不可以通过该区域。

    代码调整如下：

for (形状中的每个点p)

{

               绝对坐标 p1 = p + 质点坐标point

               if(valid(p1) == false)

                    return false;

}

return true;