a_game_road_find.rar_mapx_动态寻路_寻路算法_游戏寻_移动节点距离

A*寻径算法 下面我来说说我理解的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任保留-1 */ for( i = 0; i < 4; ++i ) { if( (p->direct & d_signal) >> i == 0x01 ) dis =(int)distance(pX + move[0], pY + move[1], quit_x, quit_y); } /* 获得最短距离的方向 */ for(i = 0; i < 4; ++i) { if(dis != -1 && dis < minDis) { minId = i; minDis = dis; } } /* 若没有可用的方向，则通知寻径函数折回 */ 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[1]][pX + move[0]] != PATH_BLOCK && maze[pY + move[1]][pX + move[0]] != PATH_FOOTPRINT) { /* 若尝试的下一个位置不是障碍物或自己走过的足迹，则视为可用方向，获得该方向的信号量 */ pnode->direct |= d_signal; } } 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; /* 压缩坐标 */ 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[1]][eX + move[0]] != PATH_BLOCK) /* 若无障碍物则获得该方向的信号量 */ p->direct |= d_signal; } 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 /* 脚印 */ ＃i nclude "AStar.cpp" #endif /* main.cpp */ /* 设计者： yuki */ ＃i nclude <stdio.h> ＃i nclude <stdlib.h> ＃i nclude <string.h> ＃i nclude <conio.h> ＃i nclude <math.h> ＃i nclude <assert.h> ＃i nclude "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[j]]); printf("\n"); } getch(); return 0; }