A*寻路

啊～。

今天不知道怎么了……居然想到看《圣剑英雄传2》的源代码（自制RPG梦想死灰复燃中）。毕竟C的源代码不是那么好读的啊……（完全看不懂……）于是打开了和源程序一起打包的《源程序导读》……

（说是给不懂的人看的，但是不懂的人看了肯定还是看不懂，请跳过吧。）

NOTE：下面的部分是额外的部分，写给不懂的人看的，高手就不用继续了。

好了，来说说A*寻路和Alpha混合，相信大家都读过了圣二的README吧，这两个可是里面有提的哦，快看看是怎么做的先。（还先？！现在了才拿出来说！–：）

先说A*算法。

A*算法是用来在游戏中寻路的，它能计算出两点之间最短的距离，而且很快。是怎么会事情呢？A*算法在找两个顶点的最短距离的时候不是象深度优先搜索那样要遍历每一个子节点，而是寻找一个最优的点，然后直接从这个点开始新的搜索。那么是怎么去找这个最优点呢？让一个叫评估函数的来算出这个点的可能最好值，然后加上这个点的深度（当然不一定是深度了，凡是可以表示从开始点到这个点所花的代价的值都可以的）就是这个点的价值了，根据这个价值把所以的子节点排序，找个最小的就是最优点了。但是可能这个时候的最优并不一定是全局的最优，所以用了一个表（open）来保存子节点，一个表（close）来保持访问过的节点。那么整个算法看起来就像是这样的：

先用一个变量保存离目的点最近的点，称为最近点。

1. 将第一个节点（根）放到open表中
2. 从open表从取一个最优点，如果为空就跳出循环到7
3. 把取出来的点放到close表中，并按照他到他的父节点的方式拉好指针，比较这个点和最近点，更新最近点。
4. 探索取出来的点的子节点
5. 按照价值的顺序从前向后插入到open表里面（这个里面有些点可以明显的丢弃）
6. 比较取出来的点是不是目标点，如果不是就跳到2，否则到7
7. 从最近点按照拉好的指针在close表里面找到路径

怎么样？看不懂吧？其实他说的话已经很清楚啦～就是……跳掉了一些词汇（跳掉了怎么还算是清楚啊！）……所以……一般人看不懂，是很正常滴~那么这个A*到底是什么呢？

A*（读作A-star也就是A-星，不叫A-asterisk）就是……就是……啊啊，首先来介绍一下什么是启发式搜索！

A*严格来说不一定能被称作算法，因为算法是有明确的步骤来达到目的的，而A*不一定有结果。这样的东西……我们就叫他启发式搜索了^_^。

启发式搜索也可以这样说（复述中）：如果从初始状态，做一件事，世界会朝什么方向发展？做另一件事呢？做这一件事之后再做另一件事呢？不停重复下去到什么时候世界会变得和目标一样呢？如果和目标一样了，我们搜索就成功了。（复述失败……技能经验值+0,残念……）

（重试中）：从初始状态，每一种行动的可能，可以看作是一棵树上的分支，每一个分支下面还有另外的分支，而我们的目的就是要找到最后到达目的地的分支。（这个……可以吗？好像很接近实际算法……）

这个有点像是在讨论博弈或者AI问题……没错，A*可以说是人工智能的一种。

说到博弈……在碰到不确定事件的时候，经常的做法就是猜测可能的行动来决定对策。但是你不可能将所有可能的行动都想出来判断对策；会累死的（无论是人还是计算机）。遇到这种情况，研究人工智能的人一般会选择最有可能的可能来进行推测和判断。（我一般选择最没有可能的可能来作出决定的，呵。）

A*在判断行走路线的时候也是一样；在判断“下一步如何走”的时候会优先判断最有可能的走法。然后是下一步的下一步，再是下一步的下一步的下一步……直到达到目标。

我将A*中每一个状态(如果在RPG中就是人物的位置)看作是一个“树”上的“节点”（这个节点就像真实树枝上的分叉点），看看从这个状态可能达到的状态有哪些叫做“展开”这个节点。展开一个节点之后会在这个节点下产生从上个状态移动可以达到的状态。展开一个节点之后就寻找最有可能更容易到达终点的节点然后再看看从它可以到哪里。

不太好懂吗？结合实际地说一遍吧。

在一开始只有一个节点(根节点)，就是角色开始的位置。

然后“展开”这个开始位置的节点。现在我们有角色周围的位置作为节点。

这之后再展开离目标最近的节点。（相当于向目标迈出了一步）这下又多了许多新节点。

如果节点离目标如此的远，以至于先前没有展开的节点比现在的节点离目标近了（走太远了！）那么就先展开先前没有展开的节点（试一条别的路）。

重复尝试，直到到达目的地或者所有的节点都已经打开过了。

哎！说明文写作失败了啊！看来只好试着照抄别人的东西了……我怎么这么容易灰心呢？其实已经差不多了……我刚才这个东西基本都是照抄（虽然我敢说没有侵犯版权）这个是Justin Heyes-Jones的A*算法教程(A* algorithm Tutorial)的（连不上Geocities,大概是因为有邪教内容？为了防止Msn Spaces被Ban所以链接地址改过了,我是用Google快照看的）。

不怎么想翻译了……但是把一部分这篇文章中的概念说一下：

首先，什么是open表，什么是close表？

Open表储存的就是还没有展开的节点。Close表储存的是已经展开的节点。（和人家说的没区别……）
Open表中的节点是将来要打开的。Close表的节点是没必要再打开的。

然后，权重。这个权重不只是到终点的距离；而是到终点的大约距离加上到当前节点所已经花费的。

最后，打开新节点的时候，不是打开刚才打开的节点的子节点中权最少的，而是打开所有未打开子节点(Open表)中权最少的。

写了好多……耽误我玩魔力……郁闷而快乐着……

父母打算带我去连云港。不要不要不要啊。

不过想到布库尔（Falcom出品游戏《双星物语》男主角的预设名字（中文版改名字只能改成数字），汗一个）的父母（主角当然要做得可怜一点啦……所以这姐弟俩就成孤儿了）……

卡库尔（这个名字真的和布库尔没关系）我还是很幸福的阿～

什么？去连云港？我不要我不要我不要～～～～～～～～！

p.s:在好长时间过后金点时空终于更新了（没注意到…）