A*, A Star A星算法详解( 五 ) _a星算法

题外话
离题一下，见谅，值得一提的是，当你在网上或者相关论坛看到关于A*的不同的探讨，你有时会看到一些被当作A*算法的代码而实际上他们不是。要使用A* ，你必须包含上面讨论的所有元素－－特定的开启和关闭列表，用F,G和H作路径评价。有很多其他的寻路算法，但他们并不是A* ， A*被认为是他们当中最好的。Bryan Stout在这篇文章后面的参考文档中论述了一部分，包括他们的一些优点和缺点。有时候特定的场合其他算法会更好，但你必须很明确你在作什么。好了，够多的了。回到文章。
实现的注解
现在你已经明白了基本原理，写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用了我用C++和Blitz Basic写的程序，但对其他语言写的代码同样有效。
1.其他单位(避免碰撞)：如果你恰好看了我的例子代码，你会发现它完全忽略了其他单位。我的寻路者事实上可以相互穿越。取决于具体的游戏，这也许可以，也许不行。如果你打算考虑其他单位，希望他们能互相绕过，我建议你只考虑静止或那些在计算路径时临近当前单位的单位，把它们当前的位置标志为可通过的。对于临近的运动着的单位，你可以通过惩罚它们各自路径上的节点，来鼓励这些寻路者找到不同的路径(更多的描述见#2).
如果你选择了把其他正在移动并且远离当前寻路单位的那些单位考虑在内，你将需要实现一种方法及时预测在何时何地碰撞可能会发生，以便恰当的避免。否则你极有可能得到一条怪异的路径，单位突然转弯试图避免和一个已经不存在的单位发生碰撞。
当然，你也需要写一些碰撞检测的代码，因为无论计算的时候路径有多完美，它也会因时间而改变。当碰撞发生时，一个单位必须寻找一条新路径，或者，如果另一个单位正在移动并且不是正面碰撞，在继续沿当前路径移动之前，等待那个单位离开。
这些提示大概可以让你开始了。如果你想了解更多，这里有些你可能会觉得有用的链接：
* 自治角色的指导行为：Craig 在指导能力上的工作和寻路有些不同，但是它可以和寻路整合从而形成更完整的移动和碰撞检测系统。
* 电脑游戏中的长短距指导：指导和寻路方面著作的一个有趣的考察。这是一个pdf文件。
* 协同单位移动：一个两部分系列文章的第一篇，内容是关于编队和基于分组的移动，作者是帝国时代(Age of )的设计者Dave .
* 实现协同移动：Dave 文章系列的第二篇。
2. 不同的地形损耗：在这个教程和我附带的程序中，地形只能是二者之－可通过的和不可通过的。但是你可能会需要一些可通过的地形，但是移动耗费更高－沼泽，小山，地牢的楼梯，等等。这些都是可通过但是比平坦的开阔地移动耗费更高的地形。类似的，道路应该比自然地形移动耗费更低。
这个问题很容易解决，只要在计算任何地形的G值的时候增加地形损耗就可以了。简单的给它增加一些额外的损耗就可以了。由于A*算法已经按照寻找最低耗费的路径来设计，所以很容易处理这种情况。在我提供的这个简单的例子里，地形只有可通过和不可通过两种， A*会找到最短，最直接的路径。但是在地形耗费不同的场合，耗费最低的路径也许会包含很长的移动距离－就像沿着路绕过沼泽而不是直接穿过它。