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

四种算法是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                         }
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。