基于A_算法的游戏地图最短路径搜索

A*算法,GIS

算法与语言

基于 A*算法的游戏地图最短路径搜索 崔振兴，顾治华 (武汉理工大学计算机科学与技术学院，北武汉 430063)湖 摘要：介绍了常用的搜索算法思想,重点剖析了采用启发式 A*算法实现大地图与复杂地形的最短路径搜索，在对估价函数特性进行分析的基础上,讨论了它的几个一般构造原则,并简要介绍一些常用的启发函数。关键词：短路径；最 Dijkstra算法； Best-First-Search;算法； A*启发函数中图分类号： TP312文献标识码： A文章编号： 1672-7800(2007)09-0145-03

0

前言 搜索分为无提示信息搜索 (也称盲目

h*(n)为节点 n到终点的实际距离，而使从得找到的路径为最短路径或最优路径。在保证 h(n)<=h*(n)的前提下，(n)的值越大， h则启发信息也越大，可以减少搜索过程中扩展的节点数，加快搜索速度。 1.2算法 (1)把起始节点 S放到 OPEN有序表中。 (2)果 OPEN表为空，失败退出，如则无解。 (3)从 OPEN表中选择一个 f值最小的节点 n。 (4) n从 OPEN表中移出，把放入 CLOSED表中。 (5)果 n是目标节点，成功退出，如则求得一个解；则跳到否 (6)。步 (6)扩展节点 n,生成其全部后继节点。对于 n的每个后继节点 m,计算 f (m)。①如果 m不在 OPEN表和 CLOSED表中，把它加入 OPEN表中，给 m加一指向其父节点 n的指针，便找到目标节点以时记住解答路径；如果 m已在 OPEN表②中，比较刚计算的(m)值和该节点 m则 f新在表中的 (m)值，果 (m)值较小， f旧如 f新表示找到了一条更好的路径，则以此新 f (m)取代表中该节点的(m)值，节值 f旧将点 m的父指针指向当前的 n节点，不是而指向它的历史父节点；③如果 m在 CLOSED表中，跳过该节点，回则返 (6)续扩展其继

它节点。 (3)到步骤跳 (2)继续循环，到找，直到解或无解退出。 1.3数据结构 (1)索树结构搜根节点为开始节点，节点为空，父在到达目标节点后，从目标节点回溯到根节点，遍历的节点就是最短路径。所 typedef struct tree_node *TREE; struct tree_node{ TREE parent;该节点的父指针// int height;//该节点在搜索树中的高度 int tile; n(x,y)的位置标号// (y*地图高度+ x)} (2) OPEN表， CLOSED表 OPEN表和 CLOSED表分别是用于保存未处理和已处理的节点的链表 typedef struct node_link *LINK; struct node_link{ TREE node

;节点内容// int f;估价函数// LINK next;下一个节点//} LINK open,close; (3)价函数 (x,=g(x,)+ h x,估 f y) y ( y)其中 f是当前节点 (x,的估价函数。 y)

搜索)有提示信息和 (启发式)搜索[1]。最短路径搜索，就是根据游戏地图中的地形和障碍，寻找一条从起点到终点的最近、最直接的路径的算法。许多著名的游戏均采用了该技术，如帝国时代和圣剑英雄传等。在大多数计算机教材中，径搜索路算法大多建立在数学中图的基础上，即图是由边(edges)连接的一系列点 (vertices)的集合。而在瓦片 (tiled)戏地图中，游我们可以把地图中的每个瓦片 (tile)看作点，并且邻接瓦片间由边(edge)连接。本文中，我们假设使用的都是这种二维栅格 (grid) title游戏地图。的 1968年，们提出了 A*算法，算法人该结合了像 BFS (Best-First-Seareh)的启发式方法和 Dijkstra算法的形式化方法。 BFS像算法这样的启发式算法通常给你一种估计的方式来解决问题而不能保证你得到最优解。 A*算法却能够保证找到最短路径。

1 A*算法 1.1思想 A*算法把 OPEN表中的节点按估价函数 f (n)=g (n)+h (n)的值从小到大进行排序，所有的搜索节点 n, h (n)<=h*(n),对使

,山东临沂人，硕士，究方向为算法设计与分析、算机网络技术；治华研计顾 (1963 )男，,湖北武汉人，硕士，汉理工大武作者简介：振兴崔 (1983 )男，学计算机科学与技术学院副教授，研究方向为软件工程、数据库应用技术。

软件导刊 2007 月号 9

145

第1页下一页