A*算法

一、引子

今天想跟大家聊的，是我们经常用到，但是却让大家觉得十分神秘的那个算法：A* 。

image.png

想必大家都玩儿过对战类的游戏，老王读书那会儿，中午吃完饭就会跟几个好哥们儿一起来两局红警。后来升级了，玩儿星际（是不是暴露年龄了，哈哈~~）。

玩儿的时候，就会发现这里面的兵（为了方便描述，把坦克、飞艇、矿车、龙骑等统称为兵），你只要指定好地点，他们就会自己朝目的地进发，最终去向你指定的地点。不过红警的实现似乎要差一点，经常走绕路，然后在路上就莫名其妙被人干了……

于是，老王就对这个找路算法做了些研究，去查了查资料。所有的资料都一致显示，这些寻路算法，基本上使用的都是一个叫做A*的算法。不过当时看了算法，没有去实践，所以也没有太深入的思考，只是知道他是一种启发式的搜索算法，能够比较快的找到相对优的路径。说来也巧，后来因为百度的A-Star算法比赛进入百度实习，才了解了很多互联网相关的技术。

二、原文

A*，那个传说中的算法