关于寻路算法的一些思考（11）：寻路算法的其他应用

667 查看

本系列：

除了查找一条可沿着移动找到一个单位的路径之外，寻路在其它方面还有很多用途。

探索

如果你的成本函数对已知世界的路径进行惩罚，那路径更有可能会通过处女地。这些路径能很好地侦测到其它单位。

侦查

如果你的成本函数对敌方瞭望塔等单位附近的路径进行惩罚，那你的单位会倾向保持隐蔽。但请注意，为了能良好运行，你需要考虑到敌方单位的移动，定期更新你的路径。

道路建设

从历史上看，道路沿着是经常使用的路径被建造。当路径走的越来越多时，植被被清除，变成泥路，再后来用石头或其它材料覆盖。寻路的一个应用就是找到道路。考虑到人们通行（去城市，湖泊，泉水，矿山等等），会随机得找到这些重要地点之间的路径。在发现上百上千次路径后，确定地图上的哪些空间最常被使用在路径上，然后把这些空间变成道路。跟随探索者喜欢的道路，重复该实验，你会发现更多的道路需要被建设。这种技术可以用于多种类型的道路（高速公路，公路，泥路）：最常用的空间应该变成高速公路，不太常用的空间变成普通公路或者泥路。

地形分析

结合势力图，寻路和视线可以给你有趣的方式来分析地形。

用与道路建设同样的方法，给定一组起点和目标点，我们可以使用寻路来确定哪些区域是最有可能被访问到的，这些区域附近往往具有重要的战略意义。Clash of Civilizations就是使用这种方式来实现它们的地图AI。

通过进一步分析公共路径，我们可以找到伏击点。路径上没有被视线扫到的位置，继续沿着路径再走N步之后才能被看到，部署伏击点在这些位置上意味着当前敌方无法看到你，直到你们的距离小于N时，这样你就能伏击大部队了。

城市建设

城市往往是围绕着自然资源形成的，比如农田和矿产。城市里的居民相互交易需要贸易路线，使用寻路来帮助他们找到自己的贸易路线，并且在路线上标注行进一天的价值。当商队走了一天需要找个地方驻扎时：一个完美的城市位置！沿着一条以上的贸易路线的村庄是用于交易的好地方，最终它会成长为城市。

道路建设和城市建设相结合可以用于生成出逼真的地图，无论是脚本还是随机地图。