[游戏开发]四种寻路算法并比较 - 开发资源区 - 中国移动开发者社区论坛 OMS开发,A...

[其他] [游戏开发]四种寻路算法并比较

四种算法是DFS,BFS,Heuristic DFS, Heuristic BFS (A*) 用了两张障碍表，一张是典型的迷宫： char Block[SY][SX]= {{1,1,1,1,1,1,1,1,1,1,1 }, {1,0,1,0,1,0,0,0,0,0,1 }, {1,0,1,0,0,0,1,0,1,1,1 }, {1,0,0,0,1,0,1,0,0,0,1 }, {1,0,1,1,0,0,1,0,0,1,1 }, {1,0,1,0,1,1,0,1,0,0,1 }, {1,0,0,0,0,0,0,0,1,0,1 }, {1,0,1,0,1,0,1,0,1,0,1 }, {1,0,0,1,0,0,1,0,1,0,1 }, {1,1,1,1,1,1,1,1,1,1,1 }}; 第二张是删掉一些障碍后的: char Block[SY][SX]= {{1,1,1,1,1,1,1,1,1,1,1 }, {1,0,1,0,1,0,0,0,0,0,1 }, {1,0,1,0,0,0,1,0,1,1,1 }, {1,0,0,0,0,0,1,0,0,0,1 }, {1,0,0,1,0,0,1,0,0,1,1 }, {1,0,1,0,0,1,0,1,0,0,1 }, {1,0,0,0,0,0,0,0,1,0,1 }, {1,0,1,0,0,0,1,0,1,0,1 }, {1,0,0,1,0,0,1,0,0,0,1 }, {1,1,1,1,1,1,1,1,1,1,1 }}; 结果： 尝试节点数 合法节点数 步数 深度优先 416/133 110/43 19/25 广度优先 190/188 48/49 19/15 深度+启发 283/39 82/22 19/19 广度+启发 189/185 48/49 19/15 所以可以看出深度+启发是最好的，效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。 view source print? 001 #include <iostream.h>  002 #include <memory.h>  003 #include <stdlib.h>  004    005 #define SX 11 //宽  006 #define SY 10 //长  007    008 int dx[4]={0,0,-1,1}; //四种移动方向对x和y坐标的影响  009 int dy[4]={-1,1,0,0};  010    011 /*char Block[SY][SX]= //障碍表  012 {{ 1,1,1,1,1,1,1,1,1,1,1 },  013 { 1,0,1,0,1,0,0,0,0,0,1 },  014 { 1,0,1,0,0,0,1,0,1,1,1 },  015 { 1,0,0,0,0,0,1,0,0,0,1 },  016 { 1,0,0,1,0,0,1,0,0,1,1 },  017 { 1,0,1,0,0,1,0,1,0,0,1 },  018 { 1,0,0,0,0,0,0,0,1,0,1 },  019 { 1,0,1,0,0,0,1,0,1,0,1 },  020 { 1,0,0,1,0,0,1,0,0,0,1 },  021 { 1,1,1,1,1,1,1,1,1,1,1 }};*/  022    023 char Block[SY][SX]= //障碍表  024 {{ 1,1,1,1,1,1,1,1,1,1,1 },  025 { 1,0,1,0,1,0,0,0,0,0,1 },  026 { 1,0,1,0,0,0,1,0,1,1,1 },  027 { 1,0,0,0,1,0,1,0,0,0,1 },  028 { 1,0,1,1,0,0,1,0,0,1,1 },  029 { 1,0,1,0,1,1,0,1,0,0,1 },  030 { 1,0,0,0,0,0,0,0,1,0,1 },  031 { 1,0,1,0,1,0,1,0,1,0,1 },  032 { 1,0,0,1,0,0,1,0,1,0,1 },  033 { 1,1,1,1,1,1,1,1,1,1,1 }};  034    035 int MaxAct=4; //移动方向总数  036 char Table[SY][SX]; //已到过标记  037 int Level=-1; //第几步  038 int LevelComplete=0; //这一步的搜索是否完成  039 int AllComplete=0; //全部搜索是否完成  040 char Act[1000]; //每一步的移动方向，搜索1000步，够了吧？  041 int x=1,y=1; //现在的x和y坐标  042 int TargetX=9,TargetY=8; //目标x和y坐标  043 int sum1=0,sum2=0;  044    045 void Test( );  046 void Back( );  047 int ActOK( );  048 int GetNextAct( );  049    050 void main( )  051 {  052 memset(Act,0,sizeof(Act)); //清零  053 memset(Table,0,sizeof(Table));  054 Table[y][x]=1; //做已到过标记  055 while (!AllComplete) //是否全部搜索完  056 {  057 Level++;LevelComplete=0; //搜索下一步  058 while (!LevelComplete)  059 {  060 Act[Level]=GetNextAct( ); //改变移动方向  061 if (Act[Level]<=MaxAct)  062 sum1++;  063 if (ActOK( )) //移动方向是否合理  064 {  065 sum2++;  066 Test( ); //测试是否已到目标  067 LevelComplete=1; //该步搜索完成  068 }  069 else  070 {  071 if (Act[Level]>MaxAct) //已搜索完所有方向  072      Back( ); //回上一步  073 if (Level<0) //全部搜索完仍无结果  074     LevelComplete=AllComplete=1; //退出  075 }  076 }  077 }  078 }  079    080 void Test( )  081 {  082 if ((x==TargetX)&&(y==TargetY)) //已到目标  083 {  084 for (int i=0;i<=Level;i++)  085 cout<<(int)Act[i]; //输出结果  086 cout<<endl;  087 cout<<Level+1<<" "<<sum1<<" "<<sum2<<endl;  088 LevelComplete=AllComplete=1; //完成搜索  089 }  090 }  091    092 int ActOK( )  093 {  094 int tx=x+dx[Act[Level]-1]; //将到点的x坐标  095 int ty=y+dy[Act[Level]-1]; //将到点的y坐标  096 if (Act[Level]>MaxAct) //方向错误？  097 return 0;  098 if ((tx>=SX)||(tx<0)) //x坐标出界？  099 return 0;  100 if ((ty>=SY)||(ty<0)) //y坐标出界？  101 return 0;  102 if (Table[ty][tx]==1) //已到过？  103 return 0;  104 if (Block[ty][tx]==1) //有障碍？  105 return 0;  106 x=tx;  107 y=ty; //移动  108 Table[y][x]=1; //做已到过标记  109 return 1;  110 }  111    112 void Back( )  113 {  114 x-=dx[Act[Level-1]-1];  115 y-=dy[Act[Level-1]-1]; //退回原来的点  116 Table[y][x]=0; //清除已到过标记  117 Act[Level]=0; //清除方向  118 Level--; //回上一层  119 }  120    121 int GetNextAct( ) //找到下一个移动方向。这一段程序有些乱，  122 //仔细看!  123 {  124 int dis[4];  125 int order[4];  126 int t=32767;  127 int tt=2;  128 for (int i=0;i<4;i++)  129 dis[i]=abs(x+dx[i]-TargetX)+abs(y+dy[i]-TargetY);  130 for (i=0;i<4;i++)  131 if (dis[i]<t)  132 {  133 order[0]=i+1;  134 t=dis[i];  135 }  136 if (Act[Level]==0)  137 return order[0];  138 order[1]=-1;  139 for (i=0;i<4;i++)  140 if ((dis[i]==t)&&(i!=(order[0]-1)))  141 {  142 order[1]=i+1;  143 break;  144 }  145 if (order[1]!=-1)  146 {  147 for (i=0;i<4;i++)  148 if (dis[i]!=t)  149 {  150 order[tt]=i+1;  151 tt++;  152 }  153 }  154 else  155 {  156 for (i=0;i<4;i++)  157 if (dis[i]!=t)  158 {  159 order[tt-1]=i+1;  160 tt++;  161 }  162 }  163    164 if (Act[Level]==order[0])  165 return order[1];  166 if (Act[Level]==order[1])  167 return order[2];  168 if (Act[Level]==order[2])  169 return order[3];  170 if (Act[Level]==order[3])  171 return 5;  172 }