设为首页收藏本站
开启辅助访问 切换到宽版

 找回密码
 立即注册

QQ登录

只需一步，快速开始

热门： 51单片机 | 24小时必答区 | 单片机教程 | 单片机DIY制作 | STM32 | Cortex M3 | 模数电子 | 电子DIY制作 | 音响/功放 | 拆机乐园 | Arduino | 嵌入式OS | 程序设计

搜索
»论坛 › 电子技术分类讨论区 › 程序设计/上位机 › 自创的求最短路径走迷宫算法
返回列表 发新帖
查看: 4820|回复: 0
打印 上一主题 下一主题
收起左侧

自创的求最短路径走迷宫算法

[复制链接]
跳转到指定楼层
楼主
ID:127229 发表于 2016-6-19 19:02 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
因为前几天去论坛看到有网友问迷宫算法的问题,所以抽空研究了一下搜索算法.我把很久以前写的
一个走迷宫的程序贴上去了.这个程序比较土,不会判断随机产生的迷宫是否能走通,不是按最短路径搜索,但是,只要是能连通的迷宫就肯定能走出去.呵呵,很土的一个方法,自已瞎琢磨了.
以前的程序算法是这样的:
1.随机产生由0x00和0xff结成的地图
2.从(0,0)点开始进入迷宫
3.因为出口在(MAXX,MAXY),所以搜索方向是 右->下->上->左
4.每走过一个方格把此方格对应的值加1
5.在选择方向时,总是优先选择方格值最小的相邻方格,这样,一个方格走过的次数越多就越不会再次走入, 所以自然而然就会走到(MAXX,MAXY)了
这种算法导致"小人"会在迷宫里不停的走来走去,很多时候是在重复走动,看起来傻傻的(俺喜欢)

为了解决判断迷宫是否能走通问题,和求最短路径问题,我想了很久.
网上有网友说可以用A*算法来探路比较好,我去找了几篇资料,没看太懂,
自已瞎折腾一通,又搞出一个新算法,也不知道学名叫什么,反正结果看起来是对的.呵呵
新的算法是这样的:
1.随机产生由0x00和0xff结成的地图
2.建立一个空的"连通地图方格列表",然后用递归方法去搜索所有与(0,0)相同值的方格,然后把坐格存入"连通地图方格列表"中 在递归时,如果碰到"连通地图方格列表"中已经存在的方格则跳出.这样,就产生了一个"连通地图方格列表",然后只要 判断迷宫入口坐标(0,0)和出口坐标(MAXX,MAXY)是否都在列表时就可以知道是否迷宫能走通了,好简单吧:)
3.把迷宫入口坐标(0,0)的赋值为1,然后用双重循环判断迷宫中每一方格,如果一个方格的值>1且小于255的话,则把相邻 的方格值全部加1,如果某一个相邻方格的值比所在方格值+1还要大的话(因为连通的原因),则把相邻方格设成方格值+1 重复这样做,直到 出口坐标(MAXX,MAXY) 也被赋值为止.
4.现在工作就很简单了,从出口坐标(MAXX,MAXY)开始向上推,逐次递减直到入口坐标(0,0),这样就得到了一个由多个坐标组成的路线表,也就是最短路径了(看起来是的)
5.因为是在老的程序基础上改的,也没有仔细弄,把最短路径经过方格全部设为0,把其它连通的方格则全部设为1, 这样老的程序不做什么修改就OK了.
6.欣赏了几十遍小人走通迷宫的路线,直是简洁,呵呵.


在解决迷宫问题的同时,俺发现判断连通的原理和绘图时填充算法其实是一回事,以后可以自已写填充函数了:)
迷宫问题虽然是小问题,但是扩展开来又可以解决别的问题了,如地图导航之类的.

这个程序及源代码的下载地址在：
  1. /*
  2.     这是一个研究最短迷宫寻路算法程序
  3.    
  4.     mail:szluosj@21cn.com
  5. */

  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <conio.h>
  10. #include <dos.h>
  11. #include <iostream.h>

  13. const int XSIZE = 60;
  14. const int YSIZE = 45;
  15. const int DIE  = 255;
  16. unsigned long count=0;
  17. unsigned char Map[YSIZE][XSIZE];

  19. int g_SameAreaList[YSIZE*XSIZE][2]; //相同区域的列表
  20. int g_iSameAreaCount = 0;

  22. int g_ShortPathList[YSIZE*XSIZE][2]; //最段的路径点列表
  23. int g_iShortPathCount = 0;

  25. int dir[4][2]=
  26. {
  27.     1 , 0,
  28.     0 , 1,
  29.     0 , -1,
  30.     -1, 0
  31. };


  34. int xx=0,yy=0;
  35. int oldxx=xx,oldyy=yy;

  37. //枚举一条线段上的所有点
  38. int LineDDA(int x1,int y1,int x2,int y2,void *p_pData)
  39. {
  40.     int i,p,n,x,y,tn,j;
  41.     int iIndex = 0;
  42.     int *pData = (int *)p_pData;
  43.    
  44.     if( y1==y2 ) //是一横线
  45.     {
  46.         if(x1>x2)
  47.         {
  48.             x=x2; x2=x1; x1=x;
  49.         }
  50.         
  51.         for (j=x1;j<=x2;j++)
  52.         {
  53.             pData[iIndex] = j;
  54.             pData[iIndex+1] = y1;
  55.             iIndex+=2;
  56.         }
  57.         return iIndex;
  58.     }
  59.    
  60.     if( x1==x2 ) //是一竖线
  61.     {
  62.         if(y1>y2)
  63.         {
  64.             y=y2; y2=y1; y1=y;
  65.         }
  66.         
  67.         for (j=y1;j<=y2;j++)
  68.         {
  69.             pData[iIndex] = x1;
  70.             pData[iIndex+1] = j;
  71.             iIndex+=2;
  72.         }
  73.         return iIndex;
  74.     }
  75.    
  76.     if( abs(y2-y1) <= abs(x2-x1) )
  77.     {
  78.         if( (y2<y1&&x2<x1) || (y1<=y2&&x1>x2) )
  79.         {
  80.             x=x2; y=y2; x2=x1; y2=y1; x1=x; y1=y;
  81.         }
  82.         
  83.         if( y2>=y1 && x2>=x1 )
  84.         {
  85.             x=x2-x1;
  86.             y=y2-y1;
  87.             p=2*y;
  88.             n=2*x-2*y;
  89.             tn=x;
  90.             
  91.             while(x1<=x2)
  92.             {
  93.                 if(tn>=0)
  94.                     tn-=p;
  95.                 else
  96.                 {
  97.                     tn+=n;
  98.                     y1++;
  99.                 }
  100.                
  101.                 pData[iIndex] = x1;
  102.                 pData[iIndex+1] = y1;
  103.                 iIndex+=2;
  104.                
  105.                 x1++;
  106.             }
  107.         }
  108.         else
  109.         {
  110.             x=x2-x1;
  111.             y=y2-y1;
  112.             p=-2*y;
  113.             n=2*x+2*y;
  114.             tn=x;
  115.             while(x1<=x2)
  116.             {
  117.                 if(tn>=0)
  118.                     tn-=p;
  119.                 else
  120.                 {
  121.                     tn+=n;
  122.                     y1--;
  123.                 }
  124.                 pData[iIndex] = x1;
  125.                 pData[iIndex+1] = y1;
  126.                 iIndex+=2;
  127.                
  128.                 //        putpixel(x1,y1);
  129.                 x1++;
  130.             }
  131.         }
  132.     }
  133.     else
  134.     {
  135.         x=x1; x1=y2; y2=x; y=y1; y1=x2; x2=y;
  136.         if( (y2<y1&&x2<x1) || (y1<=y2&&x1>x2) )
  137.         {
  138.             x=x2; y=y2; x2=x1; y2=y1; x1=x; y1=y;
  139.         }
  140.         
  141.         if( y2>=y1 && x2>=x1 )
  142.         {
  143.             x=x2-x1; y=y2-y1;
  144.             p=2*y; n=2*x-2*y; tn=x;
  145.             while(x1<=x2)
  146.             {
  147.                 if(tn>=0)
  148.                     tn-=p;
  149.                 else
  150.                 {
  151.                     tn+=n;
  152.                     y1++;
  153.                 }
  154.                 //      putpixel(y1,x1);
  155.                 pData[iIndex] = y1;
  156.                 pData[iIndex+1] = x1;
  157.                 iIndex+=2;
  158.                
  159.                 x1++;
  160.             }
  161.         }
  162.         else
  163.         {
  164.             x=x2-x1; y=y2-y1;
  165.             p=-2*y; n=2*x+2*y; tn=x;
  166.             
  167.             while(x1<=x2)
  168.             {
  169.                 if(tn>=0)
  170.                     tn-=p;
  171.                 else
  172.                 {
  173.                     tn+=n;
  174.                     y1--;
  175.                 }
  176.                 //        putpixel(y1,x1);
  177.                 pData[iIndex] = y1;
  178.                 pData[iIndex+1] = x1;
  179.                 iIndex+=2;
  180.                
  181.                 x1++;
  182.             }
  183.         }
  184.     }
  185.     return iIndex;
  186. }

  188. void ShowXY()
  189. {
  190.     textattr(0x0f);
  191.     gotoxy(70,1);
  192.     cprintf("X=%u",xx);
  193.     gotoxy(70,2);
  194.     cprintf("Y=%u",yy);
  195.     gotoxy(65,4);
  196.     cprintf("Total= %lu",count);
  197. }

  199. void ClearMap()
  200. {
  201.     for (int y=0;y<YSIZE;y++)
  202.     {
  203.         for (int x=0;x<XSIZE;x++)
  204.         {
  205.             Map[y][x]=0;
  206.         }
  207.     }
  208. }

  210. void MakeMap()
  211. {
  212.     int y,x;
  213.     int iData;
  214.    
  215.     ClearMap();
  216.     randomize();
  217.     for (y=0;y<YSIZE;y++)
  218.     {
  219.         for (x=0;x<XSIZE;x++)
  220.         {
  221.             iData = random(1000);
  222.             if ( (iData>0) && (iData<300) )
  223.                 Map[y][x]=DIE;
  224.         }
  225.     }
  226.     for (y=0;y<5;y++)
  227.     {
  228.         for (x=0;x<5;x++)
  229.         {
  230.             Map[y][x]=0;
  231.             Map[YSIZE-y-1][XSIZE-x-1]=0;
  232.         }
  233.     }
  234. }

  236. void DrawBox(int x1,int y1,int x2,int y2)
  237. {
  238.     textattr(0x7);
  239.     for (int i=0;i<x2-x1;i++)
  240.     {
  241.         gotoxy(i+x1,y1);
  242.         cprintf("?);
  243.             gotoxy(i+x1,y2);
  244.         cprintf("?);
  245.     }
  246.     for (i=0;i<y2-y1;i++)
  247.     {
  248.         gotoxy(x1,y1+i);
  249.         cprintf("?);
  250.             gotoxy(x2,y1+i);
  251.         cprintf("?);
  252.     }
  253.    
  254. }

  256. void ShowMan()
  257. {
  258.     gotoxy(oldxx+2+1,oldyy+2+1);
  259.     textattr(14);
  260.     cprintf(".");
  261.    
  262.     gotoxy(xx+2+1,yy+2+1);
  263.     textattr(13);
  264.     cprintf("");
  265. }

  267. void ShowMap()
  268. {
  269.     int X=2,Y=2;
  270.     DrawBox(X,Y,X+XSIZE+1,Y+YSIZE+1);
  271.     gotoxy(X+XSIZE+1,Y+YSIZE);
  272.     cprintf(" ");
  273.     gotoxy(X+1,Y);
  274.     cprintf(" ");
  275.    
  276.     for (int y=0;y<YSIZE;y++)
  277.     {
  278.         for (int x=0;x<XSIZE;x++)
  279.         {
  280.             gotoxy(x+X+1,y+Y+1);
  281.             switch(Map[y][x])
  282.             {
  283.             case DIE:
  284.                 textattr(4);
  285.                 cprintf("?);
  286.                     break;
  287.             case 254:
  288.                 textattr(0x2);
  289.                 cprintf("?);
  290.             case 0:
  291.             case 1:
  292.                 textattr(0x0f);
  293.                 cprintf(" ");
  294.                 break;
  295.             default:
  296.                 textattr(0x0E);
  297.                 cprintf(".");
  298.             }
  299.             
  300.         }
  301.     }
  302. }

  304. int isOver()
  305. { //判断是否死路, 判断是不是所有走过的路周围都没有路了,如果是这样就是死路了
  306.     int y,x;
  307.     //看看是不是还有气
  308.     for (y=0;y<YSIZE;y++)
  309.     {
  310.         for (x=0;x<XSIZE;x++)
  311.         {
  312.             if (Map[y][x]==0)
  313.                 continue;
  314.             
  315.             if (Map[y][x]==DIE)
  316.                 continue;
  317.             
  318.             if (y>1)
  319.                 if (Map[y-1][x]==0)
  320.                     return 0;
  321.                
  322.             if (y<YSIZE-1)
  323.                 if (Map[y+1][x]==0)
  324.                     return 0;
  325.                     
  326.             if (x>1)
  327.                 if (Map[y][x-1]==0)
  328.                     return 0;
  329.                         
  330.             if (x<XSIZE-1)
  331.                 if (Map[y][x+1]==0)
  332.                     return 0;
  333.         }
  334.     }
  335.    
  336.     return 1;
  337. }

  339. int GoToThere()
  340. {
  341.     int tx,ty;
  342.     unsigned char dd[4];
  343.     int i,j,d;
  344.     unsigned char min,data;
  345.    
  346.     for (d=0;d<4;d++)
  347.     {
  348.         tx = xx + dir[d][0];
  349.         ty = yy + dir[d][1];
  350.         if ((tx>=XSIZE)||(tx<0))
  351.         {
  352.             dd[d]=DIE;
  353.             continue;
  354.         }
  355.         if ((ty>=YSIZE)||(ty<0))
  356.         {
  357.             dd[d]=DIE;
  358.             continue;
  359.         }
  360.         dd[d]=Map[ty][tx];
  361.     }
  362.    
  363.     data=dd[0];
  364.     min=0;
  365.    
  366.     for (i=0;i<4;i++)
  367.     {
  368.         if (data>dd[i])
  369.         {
  370.             data=dd[i];
  371.             min = i;
  372.         }
  373.     }
  374.    
  375.     return min;
  376. }

  378. int Go()
  379. {
  380.     int i,d;
  381.     count++;
  382.     d = GoToThere();
  383.     oldxx=xx;
  384.     oldyy=yy;
  385.     xx = xx + dir[d][0];
  386.     yy = yy + dir[d][1];
  387.     Map[oldyy][oldxx]++;
  388.    
  389.     if (Map[oldyy][oldxx]==1)
  390.         Map[oldyy][oldxx] = 2;
  391.    
  392.     return 0;
  393. }

  395. int Success()
  396. {
  397.     if ((xx>=XSIZE-1) && (yy>=YSIZE-1))
  398.     {
  399.         //    do
  400.         //    {
  401.         gotoxy(70,5);
  402.         textattr(0xee);
  403.         cprintf("SUCCESS!"); //SUCCESS!
  404.         gotoxy(70,6);
  405.         textattr(0xee);
  406.         cprintf("Esc to Exit");
  407.         //    } while(getch()!=27);
  408.         return 0;
  409.     }
  410.     return -1;
  411. }

  413. int isExistPosInSameAreaList(int p_iX,int p_iY)
  414. {
  415.     for (int i=0;i<g_iSameAreaCount;i++)
  416.     {
  417.         if ( (g_SameAreaList[i][0] == p_iX) && (g_SameAreaList[i][1] == p_iY) )
  418.             return 1;
  419.     }
  420.    
  421.     return 0;
  422. }

  424. int AddOnePosToSameAreaList(int p_iX,int p_iY)
  425. {
  426.     if (isExistPosInSameAreaList(p_iX,p_iY))
  427.         return 0;
  428.    
  429.     g_SameAreaList[g_iSameAreaCount][0] = p_iX;
  430.     g_SameAreaList[g_iSameAreaCount][1] = p_iY;
  431.     g_iSameAreaCount++;
  432.    
  433.     return g_iSameAreaCount;
  434. }

  436. int GetSameArea(int p_iX,int p_iY)
  437. {
  438.     int iNewX,iNewY;
  439.     int iHasSame = 0;
  440.     for (int d=0;d<4;d++)
  441.     {
  442.         iNewX = p_iX + dir[d][0];
  443.         iNewY = p_iY + dir[d][1];
  444.         
  445.         if ( (iNewX>=0) && (iNewX<XSIZE) && (iNewY>=0) && (iNewY<YSIZE) )
  446.         { //新的位置有效
  447.             if (Map[iNewY][iNewX]==Map[p_iY][p_iX])
  448.             {
  449.                 iHasSame = 1;
  450.                 if (AddOnePosToSameAreaList(iNewX,iNewY)!=0) //追加成功一个新的节点
  451.                     if (GetSameArea(iNewX,iNewY)==0)//再查询下一个节点
  452.                         return 0;
  453.             }
  454.         }
  455.     }
  456.    
  457.     return iHasSame;
  458. }

  460. int GetSameAreaList(int x,int y)
  461. { //从map中得到一片相连的区域,存放到 listSameArea
  462.     g_iSameAreaCount = 0;
  463.     return GetSameArea(x,y);
  464. }

  466. int GetShortStepCount(int x1,int y1,int x2,int y2,int p_iStep)
  467. {
  468.     int iNewX,iNewY;
  469. //   int iStepCount = 0;
  470.     int iTemp;
  471.    
  472.    
  473.    
  474.     for (int d=0;d<4;d++)
  475.     {
  476.         iNewX = x1 + dir[d][0];
  477.         iNewY = y1 + dir[d][1];
  478.         
  479.         if ( (iNewX>=0) && (iNewX<XSIZE) && (iNewY>=0) && (iNewY<YSIZE) ) { //新的位置有效
  480.             if (Map[iNewY][iNewX]==Map[x1][y1]) {
  481.                 if ((iNewX==x2) && (iNewY==y2))
  482.                     return p_iStep;
  483.                
  484.                 iTemp = GetShortStepCount(iNewX,iNewY,XSIZE-1,YSIZE-1,p_iStep);
  485.                 if (iTemp==9999)
  486.                     Map[iNewX][iNewY] = 100;
  487.                
  488.                 p_iStep+=iTemp;
  489.             }
  490.         }
  491.     }
  492.    
  493.     Map[y1][x1] = 100;
  494.     return 9999;
  495. }

  497. int GetShortPathList()
  498. {
  499.     int iNewX,iNewY;
  500.     int iIndex;
  501.     int i,d,x,y;
  502.    
  503.    
  504.     Map[0][0] = 1;
  505.    
  506.     while (Map[YSIZE-1][XSIZE-1]==0) {
  507.         for (y=0;y<YSIZE;y++)
  508.         {
  509.             for (x=0;x<XSIZE;x++)
  510.             {
  511.                 if (Map[y][x]==DIE)
  512.                     continue;
  513.                
  514.                 if (Map[y][x]==0)
  515.                     continue;
  516.                
  517.                 for (d=0;d<4;d++)
  518.                 {
  519.                     iNewX = x + dir[d][0];
  520.                     iNewY = y + dir[d][1];
  521.                     if ( (iNewX>=0) && (iNewX<XSIZE) && (iNewY>=0) && (iNewY<YSIZE) ) { //新的位置有效
  522.                         if (Map[iNewY][iNewX]==DIE)
  523.                             continue;
  524.                         
  525.                         if (Map[iNewY][iNewX]==0)
  526.                             Map[iNewY][iNewX] = Map[y][x] + 1;
  527.                         else if (Map[iNewY][iNewX]>(Map[y][x] + 1))
  528.                             Map[iNewY][iNewX] = Map[y][x] + 1;
  529.                     }
  530.                 }
  531.             }
  532.         }
  533.     }
  534.    
  535.     iIndex = 0;
  536.    
  537.     iIndex = 0;
  538.     x = XSIZE-1;
  539.     y = YSIZE-1;
  540.     g_ShortPathList[iIndex][0] = x;
  541.     g_ShortPathList[iIndex][1] = y;
  542.     iIndex++;
  543.     while(1) {
  544.         if ( (x==0) && (y==0) )
  545.             break;
  546.         
  547.         for (d=0;d<4;d++)
  548.         {
  549.             iNewX = x + dir[d][0];
  550.             iNewY = y + dir[d][1];
  551.             if ( (iNewX>=0) && (iNewX<XSIZE) && (iNewY>=0) && (iNewY<YSIZE) ) { //新的位置有效
  552.                 if (Map[iNewY][iNewX]==(Map[y][x]-1)) {
  553.                     g_ShortPathList[iIndex][0] = iNewX;
  554.                     g_ShortPathList[iIndex][1] = iNewY;
  555.                     iIndex++;
  556.                     x = iNewX;
  557.                     y = iNewY;
  558.                     break;
  559.                 }
  560.             }
  561.         }
  562.     }
  563.    
  564.     g_iShortPathCount = iIndex;
  565.     return g_iShortPathCount;
  566. }

  568. void ShowSameArea()
  569. {
  570.     for (int i=0;i<g_iSameAreaCount;i++)
  571.     {
  572.         Map[g_SameAreaList[i][1]][g_SameAreaList[i][0]] = 10;
  573.     }
  574.    
  575.     ShowMap();
  576. }

  578. int GetPathCount(int p_iX,int p_iY)
  579. {//得到一个节点的通路个数
  580.     int iNewX,iNewY;
  581.     int iPathCount = 0;
  582.     for (int d=0;d<4;d++)
  583.     {
  584.         iNewX = p_iX + dir[d][0];
  585.         iNewY = p_iY + dir[d][1];
  586.         
  587.         if ( (iNewX>=0) && (iNewX<XSIZE) && (iNewY>=0) && (iNewY<YSIZE) ) { //新的位置有效
  588.             if (Map[iNewY][iNewX]==1)
  589.                 iPathCount++;
  590.             else if (Map[iNewY][iNewX]==0)
  591.                 iPathCount++;
  592.         }
  593.     }
  594.     return iPathCount;
  595. }

  597. int DropAllLeaf()
  598. {
  599.     int iCount;
  600.    
  601.     //删除单一叶子结点
  602.     do {
  603.         iCount = 0;
  604.         
  605.         for (int i=0;i<g_iSameAreaCount;i++)
  606.         {
  607.             if (GetPathCount(g_SameAreaList[i][0],g_SameAreaList[i][1])<=1)
  608.             {
  609.                 Map[g_SameAreaList[i][1]][g_SameAreaList[i][0]] = 254;
  610.                 g_SameAreaList[i][0] = 0;
  611.                 g_SameAreaList[i][1] = 0;
  612.                 iCount++;
  613.             }
  614.         }
  615.     } while(iCount>0);
  616.    
  617.     return iCount;
  618.     //删除两个分支的结点
  619. }

  621. int DropDoubleLeaf()
  622. {
  623.     int SameAreaList[YSIZE*XSIZE][2]; //相同区域的列表
  624. //    int iSameAreaCount = 0;

  626.     for (int i=0;i<g_iSameAreaCount;i++)
  627.     {
  628.         memcpy((char *)SameAreaList,g_SameAreaList,YSIZE*XSIZE*2*sizeof(int));
  629. //        iSameAreaCount = g_iSameAreaCount;

  631.         if (GetPathCount(g_SameAreaList[i][0],g_SameAreaList[i][1])==2)
  632.         { //有两条分支
  633.             Map[g_SameAreaList[i][1]][g_SameAreaList[i][0]] = 254;
  634.             g_SameAreaList[i][0] = 0;
  635.             g_SameAreaList[i][1] = 0;
  636.             //     iCount++;
  637.         }
  638.     }

  640.     return 0;
  641. }

  643. void init()
  644. {
  645.     xx=0,yy=0;
  646.     oldxx=xx,oldyy=yy;
  647.     count = 0;
  648.    
  649.    
  650.     //    highvideo(void);
  651.     //    lowvideo(void);
  652.     //    normvideo(void);
  653.     clrscr();
  654.     clrscr();
  655.     _setcursortype(_NOCURSOR);
  656. }

  658. void end()
  659. {
  660.     //    highvideo(void);
  661.     //    lowvideo(void);
  662.     //    normvideo(void);
  663.    
  664.     textattr(0x07);
  665.     clrscr();
  666.     _setcursortype(_NORMALCURSOR);
  667. }

  669. void main()
  670. {
  671.     int i;
  672.     //    highvideo();
  673.     textmode(64);
  674.    
  675.     end();
  676.     init();
  677.    
  678. lab_begin:
  679.    
  680.    
  681.     end();
  682.     init();
  683.     MakeMap();
  684.    
  685.     GetSameAreaList(1,1);
  686.    
  687.     if (!isExistPosInSameAreaList(XSIZE-1,YSIZE-1)) {
  688.         gotoxy(70,5);
  689.         textattr(0xee);
  690.         cprintf("disconnect!");
  691.         gotoxy(70,6);
  692.         textattr(0xee);
  693.         cprintf("Esc to Exit");
  694.         sound(500);
  695.         delay(100);
  696.         sound(250);
  697.         delay(100);
  698.         sound(500);
  699.         delay(100);
  700.         nosound();
  701.         
  702.         ShowSameArea();
  703.         //            ShowMap();
  704.         //            getch();
  705.         delay(1000);
  706.         
  707.         goto lab_begin;
  708.     }
  709.    
  710.     //    ShowSameArea();
  711.    
  712.     for (i=0;i<g_iSameAreaCount;i++)
  713.         Map[g_SameAreaList[i][1]][g_SameAreaList[i][0]] = 0;
  714.         /*
  715.         g_iShortPathCount = LineDDA(0,0,XSIZE-1,YSIZE-1,g_ShortPathList); // 最段的路径点列表
  716.         printf("\n%d\n",g_iShortPathCount);
  717.     */
  718.    
  719.     g_iShortPathCount = 0 ;
  720.     GetShortPathList();
  721.    
  722.     for (i=0;i<g_iSameAreaCount;i++)
  723.         Map[g_SameAreaList[i][1]][g_SameAreaList[i][0]] = 1;
  724.    
  725.     for (i=0;i<g_iShortPathCount;i++) {
  726.         if (Map[g_ShortPathList[i][1]][g_ShortPathList[i][0]]!=DIE)
  727.             Map[g_ShortPathList[i][1]][g_ShortPathList[i][0]] = 0;
  728.     }
  729.    
  730.     /*
  731.     g_iShortPathCount = 0 ;
  732.     //  GetShortPathList();
  733.     g_iShortPathCount = LineDDA(0,0,XSIZE-1,YSIZE-1,g_ShortPathList); // 最段的路径点列表
  734.     for (i=0;i<g_iShortPathCount;i++) {
  735.     if (Map[g_ShortPathList[i][1]][g_ShortPathList[i][0]]!=DIE)
  736.     Map[g_ShortPathList[i][1]][g_ShortPathList[i][0]] = 0;
  737.     }
  738.     */
  739.     //    delay(2000);
  740.     ShowMap();
  741.    
  742.     do
  743.     {
  744.         Go();
  745.         
  746.         //ShowMap();
  747.         ShowMan();
  748.         ShowXY();
  749.         
  750.         if (Success()==0)
  751.         {
  752.             delay(1000);
  753.             end();
  754.             goto lab_begin;
  755.             //      return;
  756.         }
  757.         
  758.         delay(50);
  759.         
  760.     }while(!kbhit());
  761.     if (getch()!=27)
  762.         goto lab_begin;
  763.    
  764.     _setcursortype(_NORMALCURSOR);
  765.     clrscr();
  766.     //    normvideo();
  767.     textmode(-1);
  768. }


  771. /*
  772. 20:05 2005-9-9
  773. 今天是周末,没很多事,抽空研究了一下搜索算法.因为前几天去论坛看到有网友请教迷宫算法的问题,我把很久以前写的
  774. 一个走迷宫的程序贴上去了.这个程序比较土,不会判断随机产生的迷宫是否能走通,不是按最短路径搜索,但是,只要是
  775. 能连通的迷宫就肯定能走出去.呵呵,我的算法没学好,很多时候就搞自已瞎琢磨了.

  777.   以前的程序算法是这样的:
  778.   
  779. 1.随机产生由0x00和0xff结成的地图
  780. 2.从(0,0)点开始进入迷宫
  781. 3.因为出口在(MAXX,MAXY),所以搜索方向是  右->下->上->左
  782. 4.每走过一个方格把此方格对应的值加1
  783. 5.在选择方向时,总是优先选择方格值最小的相邻方格,这样,一个方格走过的次数越多就越不会再次走入,
  784. 所以自然而然就会走到(MAXX,MAXY)了

  786. 这种算法导致"小人"会在迷宫里不停的走来走去,很多时候是在重复走动,看起来傻傻的(俺喜欢)


  789. 为了解决判断迷宫是否能走通问题,和求最短路径问题,我想了很久.
  790. 嫌型阉悼梢杂肁*算法来探路比较好,我去找了几篇资料,没看太懂,
  791. 自已瞎折腾一通,又搞出一个新算法,也不知道学名叫什么,反正结果看起来是对的.呵呵

  793. 新的算法是这样的:

  795. 1.随机产生由0x00和0xff结成的地图

  797. 2.建立一个空的"连通地图方格列表",然后用递归方法去搜索所有与(0,0)相同值的方格,然后把坐格存入"连通地图方格列表"中
  798. 在递归时,如果碰到"连通地图方格列表"中已经存在的方格则跳出.这样,就产生了一个"连通地图方格列表",然后只要
  799. 判断迷宫入口坐标(0,0)和出口坐标(MAXX,MAXY)是否都在列表时就可以知道是否迷宫能走通了,好简单吧:)

  801. 3.把迷宫入口坐标(0,0)的赋值为1,然后用双重循环判断迷宫中每一方格,如果一个方格的值>1且小于255的话,则把相邻
  802. 的方格值全部加1,如果某一个相邻方格的值比所在方格值+1还要大的话(因为连通的原因),则把相邻方格设成方格值+1
  803. 重复这样做,直到  出口坐标(MAXX,MAXY) 也被赋值为止.

  805. 4.现在工作就很简单了,从出口坐标(MAXX,MAXY)开始向上推,逐次递减直到入口坐标(0,0),这样就得到了一个由多个
  806. 坐标组成的路线表,也就是最短路径了(看起来是的)

  808. 5.因为是在老的程序基础上改的,也没有仔细弄,把最短路径经过方格全部设为0,把其它连通的方格则全部设为1,
  809. 这样老的程序不做什么修改就OK了.

  811. 6.欣赏了几十遍小人走通迷宫的路线,直是简洁,呵呵.

  813.   嗯,程序虽然表面上功能是实现了,但不知道这样处理是不是会有漏洞.
  814.   
  815.     算法书上的公式都看不懂,郁闷.
  816. */
复制代码




luosj_mg.rar

52.33 KB, 下载次数: 8, 下载积分: 黑币 -5

评分

参与人数 1黑币 +8 收起 理由
芦苇劫 + 8

查看全部评分

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏2 分享淘帖 顶顶 踩踩
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表