Monthly Archives: December 2009

原文见http://www.gamedev.net/reference/articles/article2003.asp 中文翻译见http://data.gameres.com/message.asp?TopicID=25439http://blog.vckbase.com/panic/archive/2005/03/20/3778.html 相关笔记A* 算法的C#实现(笔记)http://aloneplayer.spaces.live.com/blog/cns!C3CB6D654135F83D!2538.entry 1. 引入问题 在游戏中，地图是由很多小格子构成的。这些小格子有的代表可以穿过的平地，有的代表不可穿过的障碍物。 现在有这样一个地图，绿色的起点A和红色的终点B，两点之间的褐色方块是不可以通过的障碍物。 如何以最短或者最聪明的路线从A移动到B呢？ 2. 开始搜索 A*算法的实质是从起点开始，检查相邻方格的，向外扩展直到找到目标。 操作步骤如下： 1.从起点（2，3）开始，并且把它作为待处理点存入一个“open list”。Open list包含可能构成最终路径的格子。随着搜索的进行，不断有新的格子被加入，也会有格子在考察后被移除。简而言之，open list是一个包含待考察的格子的容器。 2．寻找起点周围所有可通过的格子，忽略不可通过的格子（墙，水等障碍物）。把可通过的格子加入Open list。同时要记录这些新的待考察格的父格子（parent square）为起点格子。父节点的概念对与路径描述十分重要。 3. 从Open List中删除起点格子（2，3），把它加入到一个“closed list”，表示它不再参与计算，closed list保存所有不需要再次检查的格子。【具体实现时没必要构造closed list，把这个格子标记为Closed就足够了】 此时,如图所示，起点格子（2，3）首先被加入Open List。相邻的8个格子都是可以通过的，因此这8个格子都被加入Open List，用淡蓝色边框表示。 这8个格子的父格子都指向格子（2，3）。 对A格的考察完毕，把它从Open List中移除，加入到Closed list当中，在图中用红色边线表示。 此时要开始考察Open List中包含的8个格子，但是，哪个方格是我们要选择的呢？答案是F值最低的那个节点。 3. 路径评分 选择路径中经过哪个方格的关键是下面这个等式： F = … Continue reading →