其實這個議題對於每次遇到要寫類似迷宮程式的時候都是一個頭痛需要思考的問題。
在此我就提供其中一個方法,也許方法很多我的不代表就是最佳但是一個參考方向。

當你要寫迷宮程式的時候也許你會有以下的作法:
1.亂數隨意產生牆壁的作法,長度不要過長的方式來達到,但有會走不到終點的情況,因為有死路產生。
2.乾脆將地圖寫死,多做幾個在程式中亂數選擇之一,還算可以的作法好處是不會有死路產生但變化不多。
3.取一的作法加入更多的限制條件,但是還是會有死路產生的狀況無法解決。
條件:在下點的情況下需檢查周圍狀況之類.....
我這提供的作法其實很簡單,就是把路先長出來然後填牆......說來簡單就幾句話而已,難道我當大家是白癡喔!!
大家都知道阿....問題就在作法上的處理了。
我以31x31的地圖大小來做說明,記住地圖一定要是積數絕不要用偶數,如果使用我的方法的話。
範例使用C語言設計,請不要問我其他語言請自行修改設計。

1.清空地圖
 for(i=0;i<31;i++)
 for(j=0;j<31;j++)
 mz[i][j]=0;

2.建圍牆
 for(i=0;i<31;i++)
 {
 mz[0][i] = 1;
 mz[30][i] = 1;
 mz[i][0] = 1;
 mz[i][30]=1;
 }

3.取偶數點,這就是訣竅點了......
為什麼要取偶數點呢?經過前面兩個動作之後如果我們只取偶數點的話圖形會如下所示:

橘色就是我們亂數取點決定牆起點的位置
 xx = (random(14)+1)*2;
 yy = (random(14)+1)*2;

4.決定牆延展的方向和限制牆的長度。
5.將牆依據檢查路線實際填上就完成。
6.列印迷宮。

經過以上的過程我們就可以完成一個不死迷宮,我必須強調不是永不死是機率上降低許多。
因為也許有人會說你可能會連續挑到同一直線或者橫線的點而且又相同的一個方向,沒錯這個機率是存在的但
他可能跟中樂透是一樣的,機率不高而且你可以在實際希望劃上的線(牆壁)不要這麼密集又可以將變成死迷宮的機率降低更多。
原始程式碼: 
/*
   程式:產生迷宮地圖
   作者: Pirate
   開發環境: Dev-C++ 4.9.8.0
*/
#include <iostream>
#include <math.h>
#include <stdlib.h>

int random(int n) {return rand() % n; }
void randomize() { srand(time(NULL)); }

using namespace std;

int main(void)
{
   int mz[30][30];
   int i,j;
   //initial
   for(i=0;i<30;i++)
      for(j=0;j<30;j++)
             mz[i][j]=0;
   //make border
   for(i=0;i<30;i++)
   {
       mz[0][i] = 1;
       mz[29][i] = 1;
       mz[i][0] = 1;
       mz[i][29]=1;
   }
   int xx,yy;       //random position
   int x_tmp,y_tmp; //backup position
   int dir;         //directory way
   int count;
   randomize();
   for(i=0;i<100;i++)
   {
       //取偶數點
       xx = (random(14)+1)*2;
       yy = (random(14)+1)*2;
       x_tmp = xx;
       y_tmp = yy;
       if(mz[xx][yy] == 0){
       do{
               count = 0;
               xx = x_tmp;
               yy = y_tmp;
               dir = random(4);
               cout << "dir:" << dir << endl;
            do{
               count = count + 1;
               switch (dir)
               {
                  case 0: xx = xx-1;
                          break;
                  case 1: xx = xx+1;
                          break;
                  case 2: yy = yy+1;
                          break;
                  case 3: yy = yy-1;
                          break;
               }
            }while(mz[xx][yy]!=1); // 確認是否已經碰到牆壁
            cout << "count:" << count << endl;
       }while(count > 10); //長度不能超過陣列-邊緣的長度否則會產生死路
       xx = x_tmp;
       yy = y_tmp;
       do{
               mz[xx][yy] = 1;
               switch (dir)
               {
                  case 0: xx = xx-1;
                          break;
                  case 1: xx = xx+1;
                          break;
                  case 2: yy = yy+1;
                          break;
                  case 3: yy = yy-1;
                          break;
               }
       }while(mz[xx][yy] != 1);
       }//if end      
       }
       //列印迷宮
       for(i=0;i<30;i++){
          for(j=0;j<30;j++){
              if(mz[i][j]==1)
                 cout << "■";
              else
                 cout << "□";
          }
          cout << endl;        
   }
   cin.get();
}

當然另外一個議題就是怎麼走一個迷宮......
可能常遇到的會是要求找最短路徑，不然就是找有幾條路可以出去....等等
這都是另外需要研究討論的議題，不在這個產生迷宮的話題中。

另外範例.....這個範例必須使用TC++來編譯，而且他還使用到繪圖模式....我想大部分的人應該都無法順利編譯執行，但看看他的迷宮怎麼製作產生才是重點。

#include<stdio.h>
#include<graphics.h>
#include<conio.h>
#include<stdlib.h>
#include<dos.h>
#define lenx 20
#define leny 16
#define len 20
#define up 1
#define left 2
#define right 4
#define down 8

int step[4][2]={{0,-1},{-1,0},{1,0},{0,1}};
int bx,by;
class maze
{
private:
 int map[lenx+1][leny+1];
public:
 maze(void);
 int get(int x,int y) {return (map[x][y]);};
 void set(int x,int y,int dir) {if (x>=0 && x<=lenx && y>=0 && y<=leny)  map[x][y] |= dir;};
 void link(int x,int y);
 void create(void);
 ~maze(void) {};
};

maze::maze(void)
{
int i,j;
for (i=0;i<=lenx;i++)
 for (j=0;j<=leny;j++)
  map[i][j]=0;
for (i=0;i<=lenx;i++)
{
 set(i,0,left);
 set(i,0,right);
 set(i,leny,left);
 set(i,leny,right);
}
for (j=0;j<=leny;j++)
{
 set(0,j,up);
 set(0,j,down);
 set(lenx,j,up);
 set(lenx,j,down);
}
}

void maze::link(int x,int y)
{
int i,dir;
do
{
 dir=random(4);
 i=0;
 do
 {
  if (get(x,y) & 1<<((dir+i)%4))
   i++;
  else if (get(x+step[(dir+i)%4][0],y+step[(dir+i)%4][1]))
   i++;
  else
  {
   set(x,y,1<<((dir+i)%4));
   x+=step[(dir+i)%4][0];
   y+=step[(dir+i)%4][1];
   if (x<0 || x>lenx || y<0 || y>leny)
    i=100;
   else
   {
    switch (1<<((dir+i)%4))
    {
     case up:
      set(x,y,down);
      line (bx+x*len,by+y*len,bx+x*len,by+(y+1)*len);
      break;
     case left:
      set(x,y,right);
      line (bx+x*len,by+y*len,bx+(x+1)*len,by+y*len);
      break;
     case right:
      set(x,y,left);
      line (bx+(x-1)*len,by+y*len,bx+x*len,by+y*len);
      break;
     case down:
      set(x,y,up);
      line (bx+x*len,by+(y-1)*len,bx+x*len,by+y*len);
      break;
    }  //switch
    delay(10);
    dir=random(4);
    i=0;
   }  //else
  }  //else
 }while (i<4);
}while (i<4);
}

void maze::create(void)
{
int u,r,d,l,i;
u=0;  r=lenx;  d=leny;  l=0;
line(bx,by,bx+lenx*len,by);
line(bx,by+len,bx,by+leny*len);
line(bx+lenx*len,by,bx+lenx*len,by+(leny-1)*len);
line(bx,by+leny*len,bx+lenx*len,by+leny*len);
while (u<d && l<r)
{
 for (i=l;i<=r;i++)
  link(i,u);
 u++;
 for (i=u;i<=d;i++)
  link(r,i);
 r--;
 for (i=r;i>=l;i--)
  link(i,d);
 d--;
 for (i=d;i>=u;i--)
  link(l,i);
 l++;
}
}

void main(void)
{
int driver,mode;
driver=VGA;
mode=VGAHI;
initgraph(&driver,&mode,"..\\bgi");
bx=getmaxx()/2-lenx/2*len;
by=getmaxy()/2-leny/2*len;
randomize();
maze m1;
m1.create();
getch();
closegraph();
}
arrow
arrow
    全站熱搜

    NBPBlog 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄