C++_迷宮演算法面試考題_上下左右移動演算法_AI判別是否可以走出迷宮_先往右再往下(若通順)之後往左再往上(若不通順)

初始位置
最左上角 (0,0)



可以走出的迷宮地圖資料設置

此時的  Realdata 和  AIdata 資料一致



程式碼版本分割區:
https://github.com/dryjoker/MazeProject_C-Exercise



maze_version1_可以上下左右移動改變_C/C++多檔案操作

00 01 02
10 11 12
20 21 22

假若今日我們以  11  此位置 來進行移動

往上  變  01
往下  變  21
往左  變  10
往右  變  12

將中心位置(目前我們所在位置用  i,j 表示之)

algorithm for maze movement(up/down/right/left)
按下   w 往上 -->(i-1,j)
按下   s 往下  -->(i+1,j)
按下   a 往左  -->(i,j-1)
按下   d 往右  --> (i,j+1)


我們是接收每一次   user  keyin的一個字元來進行
移動(預設所在位置會標示為1)
當按下移動後 1 就前進一格

有四個按鍵輸入    w/s/a/d

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

switch (ch) { case 'w': //i-1必須大於等於0 if (ipos - 1 >= 0 && Realdata[ipos - 1][jpos]<2) { //變數數值交換 0換1 1換0 int tmp = Realdata[ipos][jpos]; Realdata[ipos][jpos] = Realdata[ipos - 1][jpos]; Realdata[ipos - 1][jpos] = tmp; ipos -= 1; } break; case 's': if (ipos + 1 <= N - 1 && Realdata[ipos + 1][jpos]<2)//2d-array 最大下標為9 { //變數數值交換 0換1 1換0 int tmp = Realdata[ipos][jpos]; Realdata[ipos][jpos] = Realdata[ipos + 1][jpos]; Realdata[ipos + 1][jpos] = tmp; ipos += 1; } break; case 'a': //j-1必須大於等於0 if (jpos - 1 >= 0 && Realdata[ipos][jpos-1]<2) { //變數數值交換 0換1 1換0 int tmp = Realdata[ipos][jpos]; Realdata[ipos][jpos] = Realdata[ipos][jpos-1]; Realdata[ipos][jpos-1] = tmp; jpos -= 1; } break; case 'd': //j+1必須小於等於9 if (jpos + 1 <= N-1 && Realdata[ipos][jpos + 1]<2) { //變數數值交換 0換1 1換0 int tmp = Realdata[ipos][jpos]; Realdata[ipos][jpos] = Realdata[ipos][jpos + 1]; Realdata[ipos][jpos + 1] = tmp; jpos += 1; } break; default: break; }

maze_version2_加迷宮阻擋物 和 AI 判斷


利用AI來判斷地圖是否可以被走出去


設置一個flag 代表可否走出此迷宮之狀態切換判斷

更改成一個不能走出之迷宮

2 設定之數值  代表 阻礙物


撰寫AI判定函數

輸出判定結果


這張地圖大小寬高為10

這裡為了日後改變及表示方便用 N 表示

0~N-1

當位置到   (N-1 , N-1)    代表可走出迷宮!!!!!

使用

Recursive

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include "ai.h" int AIout(int AIdata[N][N], int i, int j) { AIdata[i][j] = 3;//避免走回頭路(死循環) if (i == N-1 && j == N-1) { canout = 1;//可走出迷宮 printf("\n恭喜走出迷宮\n"); } else { //先右再往下之後往左再往上 if (j+1 <=9 && AIdata[i][j+1]<2) { AIout(AIdata, i, j + 1); } if (i + 1 <= 9 && AIdata[i+1][j] < 2) { AIout(AIdata, i+1, j); } if (j - 1 >= 0 && AIdata[i][j-1] < 2) { AIout(AIdata, i, j - 1); } if (i - 1 >= 0 && AIdata[i-1][j] < 2) { AIout(AIdata, i-1, j); } } return canout;//代表是否成功 }

當給予的地圖有一堵牆無法走出時

AI 的  判斷

不可走出之地圖

可走出之地圖


挖個洞讓他走

這時若要看最短路徑路線走法

我們只需要多加判斷 && canout!=1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include "ai.h" int AIout(int AIdata[N][N], int i, int j) { AIdata[i][j] = 3;//避免走回頭路(死循環) if (i == N-1 && j == N-1) { canout = 1;//可走出迷宮 printf("\n恭喜走出迷宮\n"); } else { //先右再往下之後往左再往上 if (j+1 <=9 && AIdata[i][j+1]<2 && canout!=1) { AIout(AIdata, i, j + 1); } if (i + 1 <= 9 && AIdata[i+1][j] < 2 && canout != 1) { AIout(AIdata, i+1, j); } if (j - 1 >= 0 && AIdata[i][j-1] < 2 && canout != 1) { AIout(AIdata, i, j - 1); } if (i - 1 >= 0 && AIdata[i-1][j] < 2 && canout != 1) { AIout(AIdata, i-1, j); } } return canout;//代表是否成功 }

不過這是最為理想單純的走迷宮模式
先往右再往下(若通順)之後往左再往上(若不通順)

在此這張map 也只有  配置一個空格可走出

假若今日  map 複雜化為其他屬性就有可能需要額外進行其他操作