【警告】 本文章并非面向零基础的人，而是面对黄金段位的LOL大神。本文同样适合出门在外没有导航，就找不到家的孩子。
在英雄联盟之中，当你和你的队友都苦苦修炼到十八级的时候，仍然与敌方阵营不分胜负，就在你刚买好装备已经神装的时候，你看见信息框中一条队友的消息：“大龙集合”，这个时候你鼠标移到大龙处，轻点右键，然后你就像一个吃瓜群众一样盯着你的英雄，看他走进野区小路，因为你买了日炎斗篷，路过三狼的时候三狼还追着你咬了几口，你的英雄也没有去理会，三狼可算是出了一口气，牛逼坏了！然后你还顺路采了几个蘑菇，因烫到了蓝buff被蓝buff追杀。就连河道里的河蟹都想咬你一口为你在三级的时候杀了它的爷爷而报仇。然而你还是在临死前来到大龙面前，你还没动大龙一根汗毛，就被大龙一个甩尾干趴下了，这时候你旁边的妹纸还很疑惑，你得显示器怎么突然坏掉了，变成黑白的了。
那么问题来了，为什么野区套路那么深，而你的英雄不选择走大路沿河道到大龙呢？因为你每确定一个目标，你的英雄就会沿着最短的路线前往。那么你的英雄是怎么找到最近的路线呢？如果你觉的很简单，你自己也能找到，你有你的英雄找的快吗？当你确定目标的时候你的英雄可不是东张西望让后才开始走，更不会走一半发现不对劲有自己回去重头再来。你也许开始对这个问题感兴趣了，那些游戏中的英雄人物是怎么做到的？如果你不玩游戏，那么你肯定用过导航软件，你应该会好奇它是怎么做到的。你能读到这篇文章，那么你一定会写代码，你能用代码去实现这个功能吗？其实我一直都很好奇这个是怎么做到的，我最多也就会写一些增删改查的常规操作。直到我接到了一个实现A-star算法的作业，才弄明白。
A-star算法我们假设某个人要从A点到达B点，而一堵墙把这两个点隔开了，如下图所示，绿色 部分代表起点A，红色部分代表终点B，蓝色方块部分代表之间的墙。
你首先会注意到我们把这一块搜索区域分成了一个一个的方格，如此这般，使搜索 区域简单化，正是寻找路径的第一步。这种方法将我们的搜索区域简化成了一个普 通的二维数组。数组中的每一个元素表示对应的一个方格，该方格的状态被标记为 可通过的和不可通过的。通过找出从A点到B点所经过的方格，就能得到AB之间的 路径。当路径找出来以后，这个人就可以从一个格子中央移动到另一个格子中央， 直到抵达目的地。 这些格子的中点叫做节点。当你在其他地方看到有关寻找路径的东西时，你会经常发现人们在讨论节点。为什么不直接把它们称作方格呢？因为你不一定要把你的搜 索区域分隔成方块，矩形、六边形或者其他任何形状都可以。况且节点还有可能位 于这些形状内的任何一处呢？在中间、靠着边，或者什么的。我们就用这种设定， 因为毕竟这是最简单的情况。
当我们把搜索区域简化成一些很容易操作的节点后，下一步就要构造一个搜索来寻 找最短路径。在A*算法中，我们从A点开始，依次检查它的相邻节点，然后照此继 续并向外扩展直到找到目的地。 我们通过以下方法来开始搜索：
1. 从A点开始，将A点加入一个专门存放待检验的方格的“开放列表”中。这个开放列表 有点像一张购物清单。当前这个列表中只有一个元素，但一会儿将会有更多。列表 中包含的方格可能会是你要途经的方格，也可能不是。总之，这是一个包含待检验 方格的列表。
2.检查起点A相邻的所有可达的或者可通过的方格，不用管墙啊，水啊，或者其他什 么无效地形，把它们也都加到开放列表中。对于每一个相邻方格，将点A保存为它 们的“父方格”。当我们要回溯路径的时候，父方格是一个很重要的元素。稍后我们 将详细解释它。
3.从开放列表中去掉方格A，并把A加入到一个“封闭列表”中。封闭列表存放的是你现 在不用再去考虑的方格。