[C語言 練習 2]使用Dev C++建立 迷宮

        在上一次吃金幣的練習中,對自己的障礙物(其實想做出迷宮)感到不滿意,雖然有從書上看到遞迴,不過本身也想不到甚麼遞迴的方法.
有一天 找迷宮時看到 此網頁 https://openhome.cc/Gossip/OpenSCAD/RandomMaze.html
        雖然他是用OpenSCAD 而且是用 3D列印印出東西的,不過對我來說有個可以借鑑的東西就覺得很開心了,一開始是玩全看不懂的(不知道那個語言的用法並且對建立迷宮不太清楚怎麼做),所以實際上我幾乎是一路照抄他的寫法,最後卡在拆地圖的地方很久,花了很久的時間(好像快懂又不太懂,持續頓悟中),我才想通整個方法.(不過目前我還只寫得出遞迴版,非遞迴還需要需要思考蠻長一陣子)
P.S. 我才在好奇為毛我的檔名叫.cpp,原來是C++的檔案,所以其實我下方一些東西有沒注意到的錯誤...

C語言中 (我cpp檔案犯的一些錯誤,下方程式為C++支援寫法,不過差別沒太大 .下方連結有放C的程式碼,網頁部分就懶得改了)
我的C語言犯的錯誤...
1.沒有 布林值(bool) 1 0 (也沒有true false)
2.三元運算子 敘述?(是的話,這邊):(不是的話,在這邊)
好像是我等於放太多  , 我的?後面為兩個東西定值,沒把它們用() 包起來

maze[jx][iy]=state[index(jx,iy)].up_right_wall=2

3.index 索引副程式  有被命名過了 需要改名
__________________________________

許多點集合而成的迷宮

x有上牆與右牆

迷宮的建造方法是 每一個點都有上牆與右牆(如左圖),經過許多相同的上牆與右牆可以組成與(如右圖)只剩最左的牆與最底的牆沒放,不過最左的牆與最底的牆是固定不動並且永遠都不會拆的邊界.

__________________________________
P.S.這邊圖的座標為示意用,實際上我在Dev C++上面的座標(0,0)在左上角,向右為x正值,向下為y的正值.

設定 state 結構 與 迷宮牆代表陣列

//全域設定 
int maze[row][col];
struct state{
 int x,y;   //x,y座標點 
 bool visted;        //0沒拜訪過  1拜訪過 
 int up_right_wall;  //0無牆  1右牆 2上牆 3右上牆 
};
struct state state[col*row];

        P.S.其實可以直接以state結構來顯示地圖資訊,maze陣列是用來幫助我了解(x,y)座標,實際上陣列maze可以從整個程式中刪掉

生成基礎地圖參數的  副程式
除了圖上標示(3,4)實際座標值 (row-1,0)為出口,只有上牆外,其餘都是上牆與右牆

void maze_wallmake(){ //製作出(x,y)陣列的每一個點的資訊到state內,並將有牆無牆值放到陣列maze內 
 int iy,jx,i;
 for(iy=0,i=0;iy<col;iy++){
  for(jx=0;jx<row;jx++){
   state[i].x=jx;
   state[i].y=iy;
   state[i].visted=false;
   state[i].up_right_wall=(iy==0&&jx==row-1)?2:3; //0無牆  1右牆 2上牆 3右上牆 
   state[i].visted=0;//false 沒走過 true 走過 
   maze[jx][iy]=state[i].up_right_wall;
   i=i+1;
  }
 }
}

生成基礎地圖,起點(0,0)終點(3,4)

對應左圖初始生成地圖,
各座標的牆面是依據牆面值來設定上牆與右牆
(最左牆與最下牆是在印地圖時加上去的)

__________________________________

列印地圖方法

顯示出地圖的示意圖

此圖各個顏色解說:

        綠色座標是console printf在顯示在螢幕上的座標

        黃色座標是儲存迷宮 上右牆資訊的陣列的 座標  maze[jx][iy]座標

        灰色是最左牆與最下牆(固定不動)

        藍色是每一座標點都會有的點

幾乎可以把地圖看成 黃色[0][0]+u(上牆位置)+r(右牆位置)+藍色框框 當成一個配套

灰色邊界就不多說怎麼印的了,主要說如何印出上牆 右牆 與 藍色

我在列印的時候是把  黃色[0][0]+u(上牆位置)+r(右牆位置)+藍色框框 當成一個區塊在列印,當列印座標在迴圈處理黃色[0][0]時,會先印出u 和藍色 再跳到 綠色[1][2]的位置印出r

會這樣印是腦袋想不到更好的方法  與 剛好學到 如何控制console光標位置

         P.S.不過那篇文章作者,有更好的方法(那篇文章中藏在moudle那裡,我整個了解後才發現到這一行)

就是跑2次j迴圈時,跑兩次判斷 

1迴圈第一次判斷 檢查是黃色[jx[iy]值為上牆或上右牆 是否印上牆 並且 一定印藍色 

2迴圈第二次判斷  檢查是黃色[jx[iy]值為右牆或上右牆 是否印右牆

以座標來講就是 當我在印黃色[0][3]到黃色[3][3]時,
第一次判斷會列印出綠色 [1][8]到綠色[8][8]
第二次判斷會列印出綠色 [1][7]到綠色[8][7]

以下是我列印地圖的副程式    副程式的u,r 是為了讓我更好判斷有沒有誤差

void print_maze(){ //印出maze陣列 
 int iy,jx,i=0;
 for(iy=0;iy<col;iy++){//0無牆  1右牆 2上牆 3右上牆 
  for(jx=0;jx<row;jx++){
   coord(2*jx,2*iy); //確保每次都在[2*jx][2*iy]上開始 
   (jx==0&&iy==col-1)?printf("*"),printf(" "): //入口左牆上一格放牆並且入口左牆空白 
    (jx==0)?printf("*"),printf("\n*"):0;//入口左牆上2格以上的灰色左牆補滿 
   (maze[jx][iy]==3)?coord(1+2*jx,2*iy),printf("u"),printf("*"),coord(2+2*jx,1+2*iy),printf("r"):// 3右上牆 
    (maze[jx][iy]==2)?coord(1+2*jx,2*iy),printf("u"),printf("*")://2上牆
     (maze[jx][iy]==1)?coord(1+2*jx,2*iy),printf(" "),printf("*"),coord(2+2*jx,1+2*iy),printf("r"):
      (maze[jx][iy]==0)?coord(1+2*jx,2*iy),printf(" "),printf("*"):0;
     //0無牆 ,printf("*"):0;的0是無意義的,是因為一定要放個東西進去才放0
  }
 }
 printf("\n");
 for(jx=0;jx<row*2+1;jx++)//列印底下灰牆 
  printf("*");
 printf("\n");
}

__________________________________

(0,0)設定已拜訪,上牆打掉,進入(0,1)

(0,1)設定已拜訪,上牆打掉,進入(0,2)

(1,0)設定已拜訪,上牆打掉,進入(1,1)

(1,1)找不到路後,退回到上一層(也就是暗紅色路線)
找方向, 退到(2,0)時,找到可路線(3,0)

走路概念:
1.從(x,y)開始,先設定(x,y)被拜訪過,
2.再隨機找方向
3.下一個方向的座標點是否可以走(有無超過邊界與有無被拜訪過)
可以: 用下一點的座標值帶進1 (進入遞迴)
不行: 相同的座標值進入2找其他方向 (等到全部座標全部點都無法走時遞迴就會結束)

假設從(0,0)開始隨機走,假設往上走
淺藍.(0,0) 往 (0,1) 走,那障礙為 (0,0) 的上牆 ,(0,0) 上牆會被打掉,往上走後再隨機走,假設往上走
淺藍.(0,1) 往 (0,2) 走,那障礙為 (0,1) 的上牆 ,(0,1) 上牆會被打掉,往上走後再隨機走,假設往右走
淺藍.(0,2) 往 (1,2) 走,那障礙為 (0,2) 的右牆 ,(0,2) 右牆會被打掉,往右走後再隨機走,假設往右走

淺藍.(1,2) 往 (2,2) 走,那障礙為 (1,2) 的右牆 ,(1,2) 右牆會被打掉,往右走後再隨機走,假設往下走

*因為所有點的狀態最多都只有上牆與右牆,往下走會是下方點的上牆被打掉*

淺藍.(2,2) 往 (2,1) 走,那障礙為 (2,1) 的上牆 ,(2,1) 上牆會被打掉,往下走後再隨機走,假設往下走

淺藍.(2,1) 往 (2,0) 走,那障礙為 (2,0) 的上牆 ,(2,0) 上牆會被打掉,往下走後再隨機走,假設往左走
*同上,往左會是左邊點的右牆被打掉*
淺藍.(2,0) 往 (1,0) 走,那障礙為 (1,0) 的右牆 ,(1,0) 右牆會被打掉,往上走後再隨機走,假設往上走
淺藍.(1,0) 往 (1,1) 走,那障礙為 (1,0) 的上牆 ,(1,0) 上牆會被打掉,往上走後再隨機走,假設往上走
暗紅.(1,1) 四個點都試過無法走,因此跳到上一個(點(1,0)嘗試其他方向
暗紅.(1,0) 四個點都試過無法走,因此跳到上一個(點(2,0)嘗試其他方向
暗紅.(2,0) 四個點中試出有一個方向可以走,往右走
淺藍.(2,0) 往 (3,0) 走,那障礙為 (2,0) 的右牆 ,(2,0) 的右牆會被打掉,再隨機走,
之後以此類推,推到所有點都被拜訪過才會跳出遞迴與副程式而停止

走路副程式碼
P.S.
index(jx,iy)是把 (jx,iy)的座標值轉換成state結構的陣列值
next_x是依據當前x座標與方向(dir)回傳出下個座標的x值,next_y同樣.
visted_posible是檢查(jx,iy)座標是否可以被拜訪的函式

void start_go(int jx,int iy){ //開始邊走邊拆迷宮 
 //起點座標與方向 0,col-1,dir[i]
 int dir[4],i;
 rand_dir(dir); //亂數方向產生,一組4個方位,上下左右隨機排湊 
 set_visited(jx,iy); //當站在(jx,iy)座標時,此座標就被標註以路過 
 for(i=0;i<4;i++){ //測4個方向的可走性 
  if(visited_posible(next_x(jx,dir[i]),next_y(iy,dir[i]))){ //查看下一個方向可否被拜訪 
   try_block(jx,iy,dir[i]); //根據當前的(x,y)座標與dir(方向)來破壞牆壁 
   //進入遞迴,下一個座標的start_go,當走不了時會跳出遞迴到上一層遞迴測試方向
   start_go(next_x(jx,dir[i]),next_y(iy,dir[i]));  
  }
 }
}

_______________________________________________
打牆 的副程式
當狀態為右上牆,並要往上走時,打掉上牆只會剩右牆,代表右牆的值為1.
當狀態為右牆,    並要往上走時,上方被打掉過,所以不可能往上走.
當狀態只剩上牆,並要往上走時,牆都沒了,值設為0
其餘狀況皆相同 ,須注意的是
1.向左與向下,需要跳到左邊處理右牆或下方處理上牆
2.因為我這邊列印符號比較方便的座標是 向右與向下為正值,所以向下會是+1,而向左 -1

void go_up(int jx,int iy){ //往上走的牆面設定,0無牆  1右牆 2上牆 3右上牆 
 (state[index(jx,iy)].up_right_wall==3)?maze[jx][iy]=state[index(jx,iy)].up_right_wall=1:maze[jx][iy]=state[index(jx,iy)].up_right_wall=0;
}
void go_down(int jx,int iy){ //往下走的牆面設定,0無牆  1右牆 2上牆 3右上牆 
 (state[index(jx,iy+1)].up_right_wall==3)?maze[jx][iy+1]=state[index(jx,iy+1)].up_right_wall=1:maze[jx][iy+1]=state[index(jx,iy+1)].up_right_wall=0;
}
void go_left(int jx,int iy){ //往左走的牆面設定,0無牆  1右牆 2上牆 3右上牆 
 (state[index(jx-1,iy)].up_right_wall==3)?maze[jx-1][iy]=state[index(jx-1,iy)].up_right_wall=2:maze[jx-1][iy]=state[index(jx-1,iy)].up_right_wall=0;
}
void go_right(int jx,int iy){ //往右走的牆面設定,0無牆  1右牆 2上牆 3右上牆 
 (state[index(jx,iy)].up_right_wall==3)?maze[jx][iy]=state[index(jx,iy)].up_right_wall=2:maze[jx][iy]=state[index(jx,iy)].up_right_wall=0;
}
void try_block(int x,int y,int dir){ //座標與方向,決定向哪個方向走,上0  左1 下2 右3 
 (dir==0)?go_up(x,y):
  (dir==1)?go_left(x,y):
   (dir==2)?go_down(x,y):
    go_right(x,y);
}

_________________________________________________
亂數方向 副程式
一開始我想不太到應該要怎麼用rand()寫出來,
後來想到可以利用陣列配合亂數取值來取得亂數方向,
最後再把取得的亂數跟  當前可選擇的最末項(還未被選過的方向)  交換

void rand_dir(int *a){ //產生亂數方向  上0  左1 下2 右3  
 int i,k=0;
 int b[4]={0,1,2,3}; 
 for(i=0;i<4;i++){
  k=rand()%(4-i);  //避免亂數重覆產生,亂數產生0~(3-i)之間數值
  *(a+i)=b[k];  //a陣列接收的b[k]值會隨著i變大而變小 ,當i=1時,亂數只能產生0~2 
  b[k]=b[4-1-i];  //再把b的當前最末項(受亂數產生0~(3-i)影響)與b[k]交換
 }
}

_________________________________________________
還有部分  比較零碎的副程式沒有放上來,可以直接點下方網址查看
下圖為成功亂數產生的地圖(但是每次一開始時亂數值都一樣都跑一樣的地圖...所以我在main程式 設定個迴圈讓他跑)

第一次產生地圖

第二次產生地圖

以下網址為該練習的 cpp檔 與 exe檔
https://drive.google.com/open?id=1Hxd_AfmrqEofFB2AcN4A_vmj7rqVpsVU