欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

 找回密碼
 立即注冊(cè)

QQ登錄

只需一步，快速開(kāi)始

搜索
查看: 4848|回復(fù): 0
打印 上一主題 下一主題
收起左側(cè)

自創(chuàng)的求最短路徑走迷宮算法

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
ID:127229 發(fā)表于 2016-6-19 19:02 | 只看該作者 回帖獎(jiǎng)勵(lì) |倒序?yàn)g覽 |閱讀模式
因?yàn)榍皫滋烊フ搲吹接芯W(wǎng)友問(wèn)迷宮算法的問(wèn)題,所以抽空研究了一下搜索算法.我把很久以前寫(xiě)的
一個(gè)走迷宮的程序貼上去了.這個(gè)程序比較土,不會(huì)判斷隨機(jī)產(chǎn)生的迷宮是否能走通,不是按最短路徑搜索,但是,只要是能連通的迷宮就肯定能走出去.呵呵,很土的一個(gè)方法,自已瞎琢磨了.
以前的程序算法是這樣的:
1.隨機(jī)產(chǎn)生由0x00和0xff結(jié)成的地圖
2.從(0,0)點(diǎn)開(kāi)始進(jìn)入迷宮
3.因?yàn)槌隹谠?MAXX,MAXY),所以搜索方向是 右->下->上->左
4.每走過(guò)一個(gè)方格把此方格對(duì)應(yīng)的值加1
5.在選擇方向時(shí),總是優(yōu)先選擇方格值最小的相鄰方格,這樣,一個(gè)方格走過(guò)的次數(shù)越多就越不會(huì)再次走入, 所以自然而然就會(huì)走到(MAXX,MAXY)了
這種算法導(dǎo)致"小人"會(huì)在迷宮里不停的走來(lái)走去,很多時(shí)候是在重復(fù)走動(dòng),看起來(lái)傻傻的(俺喜歡)

為了解決判斷迷宮是否能走通問(wèn)題,和求最短路徑問(wèn)題,我想了很久.
網(wǎng)上有網(wǎng)友說(shuō)可以用A*算法來(lái)探路比較好,我去找了幾篇資料,沒(méi)看太懂,
自已瞎折騰一通,又搞出一個(gè)新算法,也不知道學(xué)名叫什么,反正結(jié)果看起來(lái)是對(duì)的.呵呵
新的算法是這樣的:
1.隨機(jī)產(chǎn)生由0x00和0xff結(jié)成的地圖
2.建立一個(gè)空的"連通地圖方格列表",然后用遞歸方法去搜索所有與(0,0)相同值的方格,然后把坐格存入"連通地圖方格列表"中 在遞歸時(shí),如果碰到"連通地圖方格列表"中已經(jīng)存在的方格則跳出.這樣,就產(chǎn)生了一個(gè)"連通地圖方格列表",然后只要 判斷迷宮入口坐標(biāo)(0,0)和出口坐標(biāo)(MAXX,MAXY)是否都在列表時(shí)就可以知道是否迷宮能走通了,好簡(jiǎn)單吧:)
3.把迷宮入口坐標(biāo)(0,0)的賦值為1,然后用雙重循環(huán)判斷迷宮中每一方格,如果一個(gè)方格的值>1且小于255的話(huà),則把相鄰 的方格值全部加1,如果某一個(gè)相鄰方格的值比所在方格值+1還要大的話(huà)(因?yàn)檫B通的原因),則把相鄰方格設(shè)成方格值+1 重復(fù)這樣做,直到 出口坐標(biāo)(MAXX,MAXY) 也被賦值為止.
4.現(xiàn)在工作就很簡(jiǎn)單了,從出口坐標(biāo)(MAXX,MAXY)開(kāi)始向上推,逐次遞減直到入口坐標(biāo)(0,0),這樣就得到了一個(gè)由多個(gè)坐標(biāo)組成的路線(xiàn)表,也就是最短路徑了(看起來(lái)是的)
5.因?yàn)槭窃诶系某绦蚧A(chǔ)上改的,也沒(méi)有仔細(xì)弄,把最短路徑經(jīng)過(guò)方格全部設(shè)為0,把其它連通的方格則全部設(shè)為1, 這樣老的程序不做什么修改就OK了.
6.欣賞了幾十遍小人走通迷宮的路線(xiàn),直是簡(jiǎn)潔,呵呵.


在解決迷宮問(wèn)題的同時(shí),俺發(fā)現(xiàn)判斷連通的原理和繪圖時(shí)填充算法其實(shí)是一回事,以后可以自已寫(xiě)填充函數(shù)了:)
迷宮問(wèn)題雖然是小問(wèn)題,但是擴(kuò)展開(kāi)來(lái)又可以解決別的問(wèn)題了,如地圖導(dǎo)航之類(lèi)的.

這個(gè)程序及源代碼的下載地址在：
  1. /*
  2.     這是一個(gè)研究最短迷宮尋路算法程序
  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]; //相同區(qū)域的列表
  20. int g_iSameAreaCount = 0;

  22. int g_ShortPathList[YSIZE*XSIZE][2]; //最段的路徑點(diǎn)列表
  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. //枚舉一條線(xiàn)段上的所有點(diǎn)
  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 ) //是一橫線(xiàn)
  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 ) //是一豎線(xiàn)
  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. { //判斷是否死路, 判斷是不是所有走過(guò)的路周?chē)紱](méi)有路了,如果是這樣就是死路了
  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) //追加成功一個(gè)新的節(jié)點(diǎn)
  451.                     if (GetSameArea(iNewX,iNewY)==0)//再查詢(xún)下一個(gè)節(jié)點(diǎn)
  452.                         return 0;
  453.             }
  454.         }
  455.     }
  456.    
  457.     return iHasSame;
  458. }

  460. int GetSameAreaList(int x,int y)
  461. { //從map中得到一片相連的區(qū)域,存放到 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. {//得到一個(gè)節(jié)點(diǎn)的通路個(gè)數(shù)
  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.     //刪除單一葉子結(jié)點(diǎn)
  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.     //刪除兩個(gè)分支的結(jié)點(diǎn)
  619. }

  621. int DropDoubleLeaf()
  622. {
  623.     int SameAreaList[YSIZE*XSIZE][2]; //相同區(qū)域的列表
  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); // 最段的路徑點(diǎn)列表
  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); // 最段的路徑點(diǎn)列表
  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. 今天是周末,沒(méi)很多事,抽空研究了一下搜索算法.因?yàn)榍皫滋烊フ搲吹接芯W(wǎng)友請(qǐng)教迷宮算法的問(wèn)題,我把很久以前寫(xiě)的
  774. 一個(gè)走迷宮的程序貼上去了.這個(gè)程序比較土,不會(huì)判斷隨機(jī)產(chǎn)生的迷宮是否能走通,不是按最短路徑搜索,但是,只要是
  775. 能連通的迷宮就肯定能走出去.呵呵,我的算法沒(méi)學(xué)好,很多時(shí)候就搞自已瞎琢磨了.

  777.   以前的程序算法是這樣的:
  778.   
  779. 1.隨機(jī)產(chǎn)生由0x00和0xff結(jié)成的地圖
  780. 2.從(0,0)點(diǎn)開(kāi)始進(jìn)入迷宮
  781. 3.因?yàn)槌隹谠?MAXX,MAXY),所以搜索方向是  右->下->上->左
  782. 4.每走過(guò)一個(gè)方格把此方格對(duì)應(yīng)的值加1
  783. 5.在選擇方向時(shí),總是優(yōu)先選擇方格值最小的相鄰方格,這樣,一個(gè)方格走過(guò)的次數(shù)越多就越不會(huì)再次走入,
  784. 所以自然而然就會(huì)走到(MAXX,MAXY)了

  786. 這種算法導(dǎo)致"小人"會(huì)在迷宮里不停的走來(lái)走去,很多時(shí)候是在重復(fù)走動(dòng),看起來(lái)傻傻的(俺喜歡)


  789. 為了解決判斷迷宮是否能走通問(wèn)題,和求最短路徑問(wèn)題,我想了很久.
  790. 嫌型閹悼梢雜肁*算法來(lái)探路比較好,我去找了幾篇資料,沒(méi)看太懂,
  791. 自已瞎折騰一通,又搞出一個(gè)新算法,也不知道學(xué)名叫什么,反正結(jié)果看起來(lái)是對(duì)的.呵呵

  793. 新的算法是這樣的:

  795. 1.隨機(jī)產(chǎn)生由0x00和0xff結(jié)成的地圖

  797. 2.建立一個(gè)空的"連通地圖方格列表",然后用遞歸方法去搜索所有與(0,0)相同值的方格,然后把坐格存入"連通地圖方格列表"中
  798. 在遞歸時(shí),如果碰到"連通地圖方格列表"中已經(jīng)存在的方格則跳出.這樣,就產(chǎn)生了一個(gè)"連通地圖方格列表",然后只要
  799. 判斷迷宮入口坐標(biāo)(0,0)和出口坐標(biāo)(MAXX,MAXY)是否都在列表時(shí)就可以知道是否迷宮能走通了,好簡(jiǎn)單吧:)

  801. 3.把迷宮入口坐標(biāo)(0,0)的賦值為1,然后用雙重循環(huán)判斷迷宮中每一方格,如果一個(gè)方格的值>1且小于255的話(huà),則把相鄰
  802. 的方格值全部加1,如果某一個(gè)相鄰方格的值比所在方格值+1還要大的話(huà)(因?yàn)檫B通的原因),則把相鄰方格設(shè)成方格值+1
  803. 重復(fù)這樣做,直到  出口坐標(biāo)(MAXX,MAXY) 也被賦值為止.

  805. 4.現(xiàn)在工作就很簡(jiǎn)單了,從出口坐標(biāo)(MAXX,MAXY)開(kāi)始向上推,逐次遞減直到入口坐標(biāo)(0,0),這樣就得到了一個(gè)由多個(gè)
  806. 坐標(biāo)組成的路線(xiàn)表,也就是最短路徑了(看起來(lái)是的)

  808. 5.因?yàn)槭窃诶系某绦蚧A(chǔ)上改的,也沒(méi)有仔細(xì)弄,把最短路徑經(jīng)過(guò)方格全部設(shè)為0,把其它連通的方格則全部設(shè)為1,
  809. 這樣老的程序不做什么修改就OK了.

  811. 6.欣賞了幾十遍小人走通迷宮的路線(xiàn),直是簡(jiǎn)潔,呵呵.

  813.   嗯,程序雖然表面上功能是實(shí)現(xiàn)了,但不知道這樣處理是不是會(huì)有漏洞.
  814.   
  815.     算法書(shū)上的公式都看不懂,郁悶.
  816. */
復(fù)制代碼




luosj_mg.rar

52.33 KB, 下載次數(shù): 8, 下載積分: 黑幣 -5

評(píng)分

參與人數(shù) 1黑幣 +8 收起 理由
蘆葦劫 + 8

查看全部評(píng)分

分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏2 分享淘帖 頂頂 踩踩
回復(fù)

使用道具 舉報(bào)

本版積分規(guī)則

小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表