一个简单的 A 星算法的实现

发布时间:2016-12-9 21:28:00 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"一个简单的 A 星算法的实现",主要涉及到一个简单的 A 星算法的实现方面的内容,对于一个简单的 A 星算法的实现感兴趣的同学可以参考一下。

在写自己的 2D RPG 作品的时候,经常都在想,要不要加上自动寻路功能呢 ??寻路算法的学习难度已经是家喻户晓了,刚开始学习编程的时候,我总是尽力回避那些高深复杂的算法和原理,但是,一想到以后如果要用到这些算法,而自己又不懂的话,那就糟了,所以,还是硬着头皮学习 A 星算法,虽然没有抱多大的期待,不过在按下 F5 之后看到那正确的运行结果,真心被狠狠地治愈了一顿 ... 好吧,废话少说,我们就直接看代码吧 。 开始寻路之前,我们需要准备好算法所需要的所有数据 : 1 #include <list> 2 using namespace std; 3 4 // 5 // 路径节点结构体 6 // 7 struct TILE 8 { 9 TILE( ){ x = y = f = g = h = 0; father = NULL; } 10 TILE( int x, int y ){ this->x = x; this->y = y; father = NULL; } 11 12 int x, y; 13 int f, g, h; 14 15 TILE * father; 16 }; 17 18 const int BLOCK_SIZE = 48; 19 20 // 21 // 地图大小 22 // 23 const int MAP_WIDTH = 20; 24 const int MAP_HEIGHT = 15; 25 26 // 27 // 地图碰撞数据 28 // 29 // 0 可通行 30 // 1 不可通行 31 // 32 33 int map[ MAP_HEIGHT ][ MAP_WIDTH ] = 34 { 35 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 37 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 38 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 39 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 40 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 41 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 42 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 43 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 44 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 45 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 46 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 47 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 48 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 50 }; 51 52 // 53 // 起始点与终点 54 // 55 POINT start = { 4, 8 }; 56 POINT end = { 13, 6 }; 57 58 // 59 // 开放列表与封闭列表 60 // 61 list< TILE * > open_list; 62 list< TILE * > close_list; 63 64 // 65 // 寻路成功后用于保存路径 66 // 67 TILE * path = NULL; 然后,准备好所需要的辅助函数 : 1 // 2 // 添加新节点到 open list 3 // 4 void AddNodeToOpenList( TILE * father, int x, int y ) 5 { 6 TILE * node = new TILE( x, y ); 7 8 node->father = father; 9 10 if( father ) 11 { 12 node->g = father->g + 1; 13 node->h = abs( x - end.x ) + abs( y - end.y ); 14 node->f = node->g + node->h; 15 } 16 else 17 { 18 node->g = 0; 19 node->h = 0; 20 node->f = 0; 21 } 22 23 open_list.push_back( node ); 24 } 25 26 // 27 // 判断节点是否已经存在 open list 里面 28 // 29 bool NodeInOpenList( int x, int y ) 30 { 31 list< TILE* >::iterator iter = open_list.begin( ); 32 while( iter != open_list.end( ) ) 33 { 34 if( x == ( * iter )->x && y == ( * iter )->y ) 35 return true; 36 iter ++; 37 } 38 39 return false; 40 } 41 42 // 43 // 添加特定节点的邻近节点到 open list 44 // 45 void AddAdjNodeToOpenList( TILE * father ) 46 { 47 int x = father->x; 48 int y = father->y; 49 50 // 生成四个邻近节点的 tile 索引 51 52 POINT adj[ 4 ] = 53 { 54 { x, y - 1 }, 55 { x, y + 1 }, 56 { x - 1, y }, 57 { x + 1, y } 58 }; 59 60 for( int i = 0; i < 4; i ++ ) 61 { 62 // 节点必须在地图范围内 63 64 if( adj[ i ].x >= 0 && adj[ i ].x < MAP_WIDTH && 65 adj[ i ].y >= 0 && adj[ i ].y < MAP_HEIGHT ) 66 { 67 // 节点必须可以通行 68 69 if( 0 == map[ adj[ i ].y ][ adj[ i ].x ] ) 70 { 71 // 节点不存在 open list 里面 72 73 if( ! NodeInOpenList( adj[ i ].x, adj[ i ].y ) ) 74 { 75 // 满足上面三个条件的话,就把它添加到 open list 里面 76 77 AddNodeToOpenList( father, adj[ i ].x, adj[ i ].y ); 78 } 79 } 80 } 81 } 82 } 83 84 // 85 // 从 open list 中寻找最小 F 评价的节点 86 // 87 TILE * FindBestFNode( void ) 88 { 89 int min_f = 99999999; 90 TILE * min_node = NULL; 91 list< TILE* >::iterator iter = open_list.begin( ); 92 93 while( iter != open_list.end( ) ) 94 { 95 if( ( * iter )->f < min_f ) 96 { 97 min_f = ( * iter )->f; 98 min_node = * iter; 99 } 100 101 iter ++; 102 } 103 104 return min_node; 105 } 106 107 // 108 // 从 open list 里面寻找 G 评价优于 node 的邻近节点 109 // 110 TILE * FindAdjBestGNode( TILE * node ) 111 { 112 int min_g = node->g; 113 TILE * min_node = NULL; 114 list< TILE* >::iterator iter = open_list.begin( ); 115 116 int x = node->x; 117 int y = node->y; 118 119 POINT adj[ 4 ] = 120 { 121 { x, y - 1 }, 122 { x, y + 1 }, 123 { x - 1, y }, 124 { x + 1, y } 125 }; 126 127 for( int i = 0; i < 4; i ++ ) 128 { 129 while( iter != open_list.end( ) ) 130 { 131 TILE * temp = * iter; 132 133 if( temp->x == adj[ i ].x && temp->y == adj[ i ].y ) 134 { 135 if( temp->g <= min_g ) 136 { 137 min_g = temp->g; 138 min_node = temp; 139 break; 140 } 141 } 142 143 iter ++; 144 } 145 } 146 147 return min_node; 148 } 最后,就是我们的核心寻路函数 : 1 // 2 // 开始寻路, 仅进行四方向寻路 3 // 4 TILE * FindPath( int sx, int sy, int ex, int ey ) 5 { 6 TILE * start_node = NULL; 7 TILE * best_f_node = NULL; 8 TILE * best_g_node = NULL; 9 10 // 清空 open list 和 close list 11 12 open_list.clear( ); 13 close_list.clear( ); 14 15 // 添加起始节点到 open list 16 17 AddNodeToOpenList( NULL, start.x, start.y ); 18 19 // 得到起始节点 20 21 start_node = * open_list.begin( ); 22 23 // 添加起始节点的邻近节点到 open list 24 25 AddAdjNodeToOpenList( start_node ); 26 27 // 开始寻路 28 29 while( 0 != open_list.size( ) ) 30 { 31 // 找到拥有最优 F 评价的节点 32 33 best_f_node = FindBestFNode( ); 34 35 // 如果是目标节点, 则完成寻路 36 // 此时 best_f_node 代表目标节点 37 38 if( best_f_node->x == end.x && best_f_node->y == end.y ) 39 return best_f_node; 40 41 // 将最优 F 评价的节点放入到 close list 里面 42 // 并且将其从 open list 里面移除 43 44 close_list.push_back( best_f_node ); 45 open_list.remove( best_f_node ); 46 47 // 我们看看 best_f_node 的邻近节点中 48 // 是否存在比 best_f_node 拥有更优 G 评价的节点 49 50 best_g_node = FindAdjBestGNode( best_f_node ); 51 if( best_g_node ) best_f_node = best_g_node; 52 53 // 将 best_f_node 节点的邻近节点添加到 open list 里面 54 55 AddAdjNodeToOpenList( best_f_node ); 56 } 57 58 return NULL; 59 } 最最最后,我们来看看运行效果哈 ~~ 如果大家对这个算法的实用性有疑惑的话,我们就来个复杂点的 : 再来个更复杂的 : 我没有仔细看路径是不是最优的,不过它的确帮我找到回家的路了,就像一篇外文里面说到的 :“一只有远见的猫 。”(笑) ------------------------------------------------- 最后有点疑惑就是,路是找到了,不过效率非常非常低,好比后两张图,需要大概五秒钟的时间,才能得出结果,尽管是第一张那么简单的,也要几毫秒这么久 。 所以希望各位前辈们指点一下,这个算法,应该怎么优化呢 ??

上一篇:centos6.4 install nodejs +express
下一篇:Visual Studio 各版本下载

相关文章

相关评论