贴个小东西，也许是许多游戏开发爱好者都想要获得算法。
下面我来说说我理解的A*算法的原理：
A*算法是一个求最短路径的函数，为许多即时战略游戏所用刀（或许人家大型的即时战略游戏笔者算法更好，不管它）。它由两个函数组成，一个是评估函数，也就是确定人物移动的下一个位置必须离目标位置最近，评估函数评估的结果越精确，则寻径的速度越快；另一个就是寻径函数，也就根据评估的结果做出响应，然后从新位置继续评估下一个位置，若无路可走（四周都是障碍什么的），那么折回一个路径节点，尝试其他方向，这个算法有个缺点，随着游戏中人物增多，相应的处理节点就增多了，会影响处理速度，而且占用大量的内存。
有兴趣的朋友可以改成动态的寻径，就是当入口和出口位置都在变化的时候进行寻径，这个代码也只有200多行。
我的算法还不能算是最优的，因为评估函数只不过是简单的测试两点距离（这会带来误差），选择离出口最短的且非障碍物的方向，进行下一个路径节点的移动。
这里说一句，我希望大家将我的代码用于学习目的，不希望看见是为了交作业而拷贝过去，我会很伤心的。
/* AStar.cpp */
/* 设计者： yuki */
typedef unsigned char byte_t;
typedef unsigned int uint_t;
/* 路径节点 */
typedef struct footprint {
/* 存放在数组中的位置 */
uint_t pos;
/* 存放方向信号量 */
byte_t direct;
struct footprint *next;
struct footprint *prev;
} path_t;
/*
方向信号量查询表
0x01(0000 0001) : 上
0x02(0000 0010) : 下
0x04(0000 0100) : 左
0x08(0000 1000) : 右
*/
static byte_t d_signal[4] = {0x01, 0x02, 0x04, 0x08};
/*
方向信号量使用表
如果指定方向已经走过，那么使用“与”运算去处该方向
0x0E(0000 1110) : 上
0x0D(0000 1101) : 下
0x0B(0000 1011) : 左
0x07(0000 0111) : 右
*/
static byte_t d_spend[4] = {0x0E, 0x0D, 0x0B, 0x07};
/* 指定方向移动偏量 */
static int move[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
/* 打印迷宫用的符号 */
static byte_t symbolic[3] = {'#',0x20,'*'};
/* 求两点间的距离 */
inline uint_t
distance( uint_t pos1X, uint_t pos1Y, uint_t pos2X, uint_t pos2Y ) {
uint_t ret = 0;
/* 距离公式 */
ret = (uint_t)sqrt((pow((double)((int)pos1X - (int)pos2X),2) + pow((double)((int)pos1Y - (int)pos2Y),2)));
return ret;
}
/* 压缩坐标 */
inline uint_t
create_pos( uint_t pX, uint_t pY ) {
uint_t ret = 0;
/* 将pX赋给ret，这样pX坐标在ret的低八位 */
ret = pX;
/* 将pX坐标移到高八位去，这样低位就能存放pY */
ret <<= 8;
/* 将pY存放放到ret的低八位，并保持高八位的数据不变 */
ret |= pY;
return ret;
}
/*
== 估计函数 ===========================================
-p : 当前移动到的节点指针
-quit_x
-quit_y : quit_x 和 quit_y表示迷宫出口坐标
-maze : 迷宫矩阵
=======================================================
*/
inline path_t *
evaluate( path_t *p, uint_t quit_x, uint_t quit_y, byte_t maze[MAZE_HEIGHT][MAZE_WIDTH] ) {
uint_t pX, pY;
/* 用于接收四个方向离开出口的距离，以便选择最近的方向移动 */
int dis[4];
int minDis = 32767;
int minId = -1;
path_t *pnode = (path_t *)0;
register int i;
/* 计算当前节点的坐标 */
pX = p->pos >> 8;
pY = p->pos & 0x00FF;
memset(dis, (int)-1, sizeof(int)*4);
/* 计算每个方向离开出口的距离，一次存放到dis数组，若没有i方向，则dis[i]任保留-1 */
for( i = 0; i < 4; ++i ) {
if( (p->direct & d_signal[i]) >> i == 0x01 )
dis[i] =(int)distance(pX + move[i][0], pY + move[i][1], quit_x, quit_y);
}
/* 获得最短距离的方向 */
for(i = 0; i < 4; ++i) {
if(dis[i] != -1 && dis[i] < minDis) {
minId = i;
minDis = dis[i];
}
}
/* 若没有可用的方向，则通知寻径函数折回 */
if(minId == -1)
return (path_t *)0;
/* 用去最近距离方向的信号量 */
p->direct &= d_spend[minId];
/* 在移动到新位置之前，在旧位置处留下足迹 */
maze[pY][pX] = (byte_t)PATH_FOOTPRINT;
/* 构建新的路径节点 */
pnode = (path_t *)malloc(sizeof(path_t));
assert(pnode);
/* 计算下一个位置的坐标 */
pX += move[minId][0];
pY += move[minId][1];
pnode->pos = create_pos(pX, pY);
pnode->prev = p;
pnode->next = (path_t *)0;
pnode->direct = 0;
/* 在新位置处，计算下一个位置可用的移动方向 */
for(i = 0; i < 4; ++i) {
if(maze[pY + move[i][1]][pX + move[i][0]] != PATH_BLOCK && maze[pY + move[i][1]][pX + move[i][0]] != PATH_FOOTPRINT) {
/* 若尝试的下一个位置不是障碍物或自己走过的足迹，则视为可用方向，获得该方向的信号量 */
pnode->direct |= d_signal[i];
}
}
return pnode;
}
/*
== A*算法寻径函数 ===========================================
-eX
-eY :入口坐标
-qX
-qY :出口坐标
-maze :迷宫矩阵
=============================================================
*/
inline path_t *
AStar(uint_t eX, uint_t eY, uint_t qX, uint_t qY, byte_t maze[MAZE_HEIGHT][MAZE_WIDTH]) {
register int i;
if(maze[qY][qX] == PATH_BLOCK)
return (path_t *)0;
/* 压缩坐标 */
uint_t quit_pos = create_pos(qX, qY);
/* 构建入口路径节点，视为路径链的头 */
path_t *head = (path_t *)malloc(sizeof(path_t));
path_t *p = (path_t *)0;
path_t *back = (path_t *)0;
assert(head);
p = head;
p->direct = 0;
p->pos = create_pos(eX,eY);
p->next = (path_t *)0;
p->prev = (path_t *)0;
/* 创建入口处的可用方向 */
for(i = 0; i < 4; ++i) {
if(maze[eY + move[i][1]][eX + move[i][0]] != PATH_BLOCK)
/* 若无障碍物则获得该方向的信号量 */
p->direct |= d_signal[i];
}
do {
/* 获得下个路径的节点指针 */
back = evaluate(p, qX, qY, maze);
if(back) {
p->next = back;
p = p->next;
}
/* 无路可走则折回 */
if(p->direct == 0 && p != head && p->pos != quit_pos) {
back = p->prev;
back->next = (path_t *)0;
/* 清楚脚印 */
maze[p->pos & 0x00FF][p->pos >> 8] = (byte_t)PATH_WALKON;
free(p);
p = back;
}
/* 若走不出迷宫，即折回到入口，且入口处的可用方向全部尝试过 */
if(p == head && p->direct == 0) {
free(head);
return (path_t *)0;
}
} while( p->pos != quit_pos );
/* 在出口处留下脚印，便于打印 */
maze[p->pos & 0x00FF][p->pos >> 8] = (byte_t)PATH_FOOTPRINT;
return head;
}
/* AStar.h */
/* 设计者： yuki */
#ifndef __ASTAR_H
#define __ASTAR_H
#define MAZE_WIDTH 10 /* 迷宫宽度 */
#define MAZE_HEIGHT 10 /* 迷宫高度 */
#define PATH_BLOCK 0 /* 障碍物 */
#define PATH_WALKON 1 /* 可行走 */
#define PATH_FOOTPRINT 2 /* 脚印 */
#include "AStar.cpp"
#endif
/* main.cpp */
/* 设计者： yuki */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>
#include <assert.h>
#include "AStar.h"
static byte_t maze[MAZE_HEIGHT][MAZE_WIDTH] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
0, 1, 1, 1, 1, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 1, 1, 0, 1, 0,
0, 1, 1, 1, 0, 1, 1, 0, 1, 0,
0, 1, 0, 1, 1, 1, 0, 1, 1, 0,
0, 1, 0, 0, 0, 1, 0, 0, 1, 0,
0, 0, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
int main() {
register int i,j;
path_t *pHead = AStar((uint_t)1,(uint_t)1,(uint_t)2,(uint_t)8,maze);
path_t *p = pHead;
path_t *bak;
if(p) {
bak = p->next;
printf("(%u,%u)",p->pos >> 8, p->pos & 0x00FF);
free(p);
p = bak;
while(p) {
bak = p->next;
printf("->(%u,%u)",p->pos >> 8, p->pos & 0x00FF);
free(p);
p = bak;
}
printf("\n");
}
else
printf("No path to get out of the maze\n");
pHead = p = bak = (path_t *)0;
/* 打印迷宫 */
for(i = 0; i < MAZE_HEIGHT; ++i) {
for(j = 0; j < MAZE_WIDTH; ++j)
printf("%c",symbolic[maze[i][j]]);
printf("\n");
}
getch();
return 0;
}
[此贴子已经被作者于2006-8-5 9:25:33编辑过]
----------------解决方案--------------------------------------------------------
修正一个非致命错误。
错误描述：
当出口（也就是移动的目的地）设置在障碍物上，由于无法抵达而导致该算法全图遍历路径，最后折返到出发点得出“无路可走的结论”。若地图很大，且地形复杂，则严重影响效率。
错误解决：
在搜索路径前首先测试目的地的是否可通行。
代码(已在首贴中更改）：
我在AStar()函数开头部分添加了一个测试语句
if(maze[qY][qX] == PATH_BLOCK)
return (path_t *)0;
----------------解决方案--------------------------------------------------------
帮顶！
----------------解决方案--------------------------------------------------------
问题1：最短路的话为什么不直接用Dijkstra？
问题2：你这个算法的A函数是什么
----------------解决方案--------------------------------------------------------
问题1：最短路的话为什么不直接用Dijkstra？
Dijkstra是典型的最短路径求解算法，主要特点是以起始点的中心向外扩展，直到扩展到终点为止，该算法能够求出最优解，但当地图很大，展开的节点相应的增多，影响效率；而A*算法是基于Dijkstra算法的改进，它们的主要区别在于有无估计函数，A*算法是一种启发式的探索，虽然它往往由于估计函数的误差不能得到最优的解，但是它是公认的最有效的寻径算法。A*算法在每移动一个节点后都对下一个节点进行评估，也就是展开那个节点最接近目标（走哪个节点），所以一般不用展开大量的节点，也就是说有些路径就不尝试了。
问题2：你这个算法的A函数是什么
AStar()函数主要是根据evaluate()评估的结果生成路径。
1) 首先生成入口的路径节点
2) 循环进行估计知道获得的路径节点是出口就退出，反之
a) 若获得的节点是空节点(可能因为无法获得下一个位置则折回）
b) 若折回到头节点，且所有的方向都尝试，则无解
这个函数返回获得路径链的首地址，若误解则返回(path_t *)0
----------------解决方案--------------------------------------------------------
回楼上：
A*算法是一定能够找到最有解的，除非A函数不符合条件，但是如果不符合条件的话就不叫A*算法了.
我指的A函数就是启发函数.
能不能评估一下你的算法的复杂度
----------------解决方案--------------------------------------------------------
不是这样的，我在网上看了点资料还有修改代码做过些实验，A*算法并不一定能够找到最优解，解得质量取决于评估函数的精确性，在游戏中一般评估函数都找的不是非常精确，原因是精确的评估需要大量的、复杂的计算，这样会影响效率，其实我们只要找到一个有效解就可以了。
抱歉，我不懂如何正确评估一个算法的复杂度，一般我都是理解原理后直接写代码，这种数学工作我不在行。
----------------解决方案--------------------------------------------------------
这只是一个概念的问题。。。
我在一些书本上看到的是A*算法的A函数必须满足一些特性，这些特性保证找到的第一个解答也是最优解答。如果A函数不满足该条件的话就不能够算A*算法。
当然我说了这只是概念性的问题而已.所以我想也不需要讨论了。
其实我更敢兴趣的是你怎么设计这个估价函数.也就是评估结果是怎么产生的.
----------------解决方案--------------------------------------------------------
这里我示意的写一下评估函数实现过程
函数原形：
inline path_t *
evaluate( path_t *p, uint_t quit_x, uint_t quit_y, byte_t maze[MAZE_HEIGHT][MAZE_WIDTH] );
指针p是指当前所处位置的路径节点，quit_x和quit_y都是出口坐标，maze是迷宫矩阵
实现步骤：
1）将p节点的坐标解压成pX和pY
2) p->direct低四位存放着可用的方向信号量，比如
p->direct : 0000 0101 那么我们可以认定下一个节点有两个方向可以展开“下方”和“右方”
（在这之前定义了一个4个元素的dis数组，全部元素出初始为-1用于区别可用方向和非可用方向。）
3）回到上面p->direct那个例子，循环分别尝试着两个方向，并计算着两个方向离开出口的距离长，被填入dis[1]和dis[3]。由于其他方向不可用那么dis[0]和dis[2]仍保持-1。
4）接下来用到前面定义的两个变量minId和midDis分别是记录dis中最小值索引，和最小距离，通过循环得到着两个东西。
5）对于得到的最小minId若非初始化时的-1，说明有可用最近节点存在，则根据minId值展开这个方向的节点，并用去就节点上这个方向的信号量，比如“下方”是最近节点，也就是说p->direct变为 0000 0001被用去了信号量，即使折回时也只有一个信号量可用了。
6）构建新位置的路径节点，并在迷宫的旧位置处，也就是pX和pY处留下脚印，脚印被视作已走过的方向，新节点无法使用这个方向，这样就不会重复走同样的路了。
7）若没有问题则返回新路径节点，若minId为-1则返回(path_t *)0
以上就是实现步骤啦，如果真要我哦用数学归纳法，高阶无穷小这类方法来归纳算法时间复杂度和空间复杂度真难倒我了，高数我下学期准备复习了，现在忘得差不多，实在没办法做，抱歉。
----------------解决方案--------------------------------------------------------