老鼠走迷宮-簡易版

由於前幾個老鼠走迷宮版本可能對有些人來說可能比較難，所以這邊提供幾個最基本的版本~

不要看到下面一大堆程式碼就嚇到了...我只是把它放在一起而已~~

在提供版本之前先來講解一下老鼠怎麼走迷宮
所有的遊戲地圖基本上都是由矩陣所構成，而矩陣中美一個元素可能代表著不同的意思，下圖試一個迷宮的矩陣，我們可以看到裡面有許多的數字:
其中4表示外牆、3表示內牆、1表示起點、2表示終點而0表示可以走的通道!

當然我們一般在玩遊戲時根本不知道原來地圖是長這樣的，因為這些數字對於玩家來說只會眼花撩亂而已，當電腦只要知道這些數字，再將這些數字利用不同的圖片或者符號印出時，就可以得到我們平常玩遊戲時的場景，比如說下面這張圖:

點圖可放大

這張圖片我只是將剛剛第一張圖片不能走的區域弄成黑色，在經由程式印出，這樣就可以畫出遊戲的迷宮了!!這樣大家有沒有比較有概念了?

以下產生的迷宮都是固定迷宮至於如何產生亂數迷宮呢?
請看 資料結構-老鼠走迷宮

接下來我們看一些基本的範例應該可以更有印象，版本由淺入深，盡量每一個都跑過一次~後面的版本請建置專案，將標頭檔與cpp檔放在一起(或者是將標頭檔內容複製到cpp檔程式碼最上端)
以下程式碼請勿直接貼到編譯器中執行，因為會有編碼問題! 請先轉碼!

版本1

#include <stdio.h>
#include <stdlib.h>
#define SIZE 7

typedef struct {
    int x; 
    int y;
} Point;

Point pt(int, int);
int visit(int[][SIZE], Point, Point);
void print(int[][SIZE]);

int main(void) { 
//地圖 2為障礙物 0為可以走的地區，可自行調整地圖 
    int maze[SIZE][SIZE] = {{2, 2, 2, 2, 2, 2, 2}, 
                            {2, 0, 0, 0, 0, 0, 2}, 
                            {2, 0, 2, 0, 2, 0, 2}, 
                            {2, 0, 0, 2, 0, 2, 2}, 
                            {2, 2, 0, 2, 0, 2, 2}, 
                            {2, 0, 0, 0, 0, 0, 2}, 
                            {2, 2, 2, 2, 2, 2, 2}}; 

    if(!visit(maze, pt(1, 1), pt(5, 5))) {
        printf("\n沒有找到出口！\n"); 
    }
    print(maze);
    
    return 0; 
}

Point pt(int x, int y) {
    Point p = {x, y};
    return p;
}
/*開始拜訪迷宮*/ 
int visit(int maze[][SIZE], Point start, Point end) {
    if(!maze[start.x][start.y]) {
         maze[start.x][start.y] = 1;
         if(!maze[end.x][end.y] && 
            !(visit(maze, pt(start.x, start.y + 1), end) || 
              visit(maze, pt(start.x + 1, start.y), end) ||
              visit(maze, pt(start.x, start.y - 1), end) || 
              visit(maze, pt(start.x - 1, start.y), end))) {
                 maze[start.x][start.y] = 0;
         }
    }
    return maze[end.x][end.y];
    
}
/*印出地圖*/ 
void print(int maze[][SIZE]) {
    int i, j;
    for(i = 0; i < SIZE; i++) { 
        for(j = 0; j < SIZE; j++) switch(maze[i][j]) {
            case 0 : printf("  "); break;
            case 1 : printf("◇"); break;
            case 2 : printf("█"); 
        }
        printf("\n"); 
    }     
}

版本2(貌似有點問題?! 請先用其它版本)

//用此類別來紀錄走訪過的路，含有堆疊的特性 
#ifndef RECORD_H
#define RECORD_H
class RECORD_ROAD
{
      private:
              int row,col;
      public:
             void pop(int* r,int* c){*r = row; *c = col;}
             void push(int r,int c){row = r;col = c;}
};
#endif

/*題目：老鼠走迷宮陣列版本 ,以該迷宮一定有路徑可以達到終點為前提
1.使用物件陣列來儲存走訪的路徑，記憶體使用上有些許浪費 
2.走訪的方法，則是使用巢狀if else結構來完成 
*/
#include <cstdlib>
#include <iostream>
#include "record.h"//RECORD_ROAD類別與實做的宣告 
#include <windows.h>//COORD結構的宣告 
using namespace std;


const int row_size = 14;//迷宮圖列 
const int col_size = 17;//迷宮圖行 
int top = 0;

void draw_map(bool map[row_size][col_size]);//畫出迷宮圖 
void gotoxy(int x,int y);//設置列印座標 
void print_path(RECORD_ROAD* record_road);//列印出路徑 

     
int main(int argc, char *argv[])
{
//將迷宮的外層圍一層牆壁 
bool map[row_size][col_size] = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
                                {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
                                {1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
                                {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
                                {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
                                {1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
                                {1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},
                                {1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1},
                                {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1},
                                {1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
                                {1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
                                {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
   int row = 1,col = 1;//起點(1,1) 
   RECORD_ROAD record_road[100];//利用物件陣列來紀錄走過的座標 
  
   
   draw_map(map);//畫出迷宮圖案  
   record_road[top].push(row,col);//push (1,1)
   map[row][col] = 1;//凡走過，則將該圖上的位置標示為 1  
   
   //當座標還沒有到達終點之前，繼續走訪 
   while((row != row_size-2)||(col != col_size-2))
   {
              if(map[row-1][col] == 0 )//正上方 
              {
                   row--;             
              }
              else if(map[row-1][col+1]==0 )//右上方 
              {
                   row--;   col++; 
              }
              else if(map[row][col+1]==0 )//右方 
              {
                   col++;
              }
              else if(map[row+1][col+1]==0 )//右下方 
              {
                   row++;    col++;                  
              }
              else if(map[row+1][col]==0)//下方 
              {
                   row++;                  
              }
              else if(map[row+1][col-1]==0 )//左下方 
              {
                   row++;    col--;
              }
              else if(map[row][col-1]==0 )//左方 
              {
                   col--;
              }
              else if(map[row-1][col-1]==0 )//左上方 
              {
                   row--;    col--;
              }
              else//當目前的座標位置沒有路可以前進時 
              {   
                  top--;
                  //返回前一步的座標   
                  
                  record_road[top].pop(&row,&col);
                  //pop前一步的座標 
                  
                  continue;
                  //重新判斷是否有方向可以走訪       
              }  
               //如果有路可以走的話，則前進並且紀錄目前的座標 
               
               top++;
               //前進 
               
               record_road[top].push(row,col);
               //將目前的座標紀錄下來 
               
               map[row][col] = 1;
               //凡走過，則將該圖上的位置標示為 1 
   }
    print_path(record_road);
    //將物件陣列的位址pass給function
                  
    system("PAUSE");
    return EXIT_SUCCESS;
}

void draw_map(bool map[row_size][col_size])
{   
    int row,col;
    for(row=0; row<row_size; row++)
    {
               for(col=0; col<col_size; col++)
               {          
                    if(row==0||row==13)cout<<"-";
               else if(col==0||col==16)cout<<"|";
               else
                   cout<< (map[row][col]== 1? "x":"o");
               }
               cout<<endl;
    }  
}
void gotoxy(int x,int y)//設置列印座標 
{
    COORD c;
    c.X = x;
    c.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c);
    //設置終端機滑鼠指標位置 
} 

void print_path( RECORD_ROAD* record_road)
{
     int row,col;
     //列印出可以走到終點的路徑 
   for(int i=0; i<=top; i++)
   {       
           record_road.pop(&row,&col);//將走訪過路徑pop出來 
           
           gotoxy(col,row);//col行，代表是x座標；row列，代表是y座標 
           
           cout<<static_cast<char>(1);
           _sleep(200);//is included in stdlib.h參數為毫秒 200->0.2秒 
   }        
}

版本3

//用此類別來紀錄走訪過的路，含有堆疊的特性 
#ifndef RECORD_H
#define RECORD_H
class RECORD_ROAD
{
      private:
              int row,col;
      public:
             void pop(int* r,int* c){*r = row; *c = col;}
             void push(int r,int c){row = r;col = c;}
             RECORD_ROAD* forward,*next;//雙向鏈結 
};
#endif

/*題目：老鼠走迷宮鏈結串列版,以該迷宮一定有路徑可以達到終點為前提
1.使用雙向鏈結串列來儲存走訪的路徑，可達到節省記憶體的效果
2.走訪的方法，則是使用巢狀if else結構來完成 
*/
#include <cstdlib>
#include <iostream>
#include "record.h"//RECORD_ROAD類別與實做的宣告 
#include <windows.h>//COORD結構的宣告 
using namespace std;


const int row_size = 14;//迷宮圖列 
const int col_size = 17;//迷宮圖行 

void draw_map(bool map[row_size][col_size]);//畫出迷宮圖 
void gotoxy(int x,int y);//設置列印座標 
void print_path(RECORD_ROAD* first_point);//列印出路徑 


     
int main(int argc, char *argv[])
{
//將迷宮的外層圍一層牆壁 
bool map[row_size][col_size] = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
                                {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
                                {1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
                                {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
                                {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
                                {1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
                                {1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},
                                {1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1},
                                {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1},
                                {1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
                                {1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
                                {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
   int row = 1,col = 1;//起點(1,1) 
   RECORD_ROAD *first_point,*this_point;
   
   draw_map(map);//畫出迷宮圖案  
   this_point = first_point = new RECORD_ROAD;//建立第一個節點 
   this_point->push(row,col);//push (1,1)
   map[row][col] = 1;//凡走過，則將該圖上的位置標示為 1  
   
   //當座標還沒有到達終點之前，繼續走訪 
   while((row != row_size-2)||(col != col_size-2))
   {
              if(map[row-1][col] == 0 )//正上方 
              {
                   row--;             
              }
              else if(map[row-1][col+1]==0 )//右上方 
              {
                   row--;   col++; 
              }
              else if(map[row][col+1]==0 )//右方 
              {
                   col++;
              }
              else if(map[row+1][col+1]==0 )//右下方 
              {
                   row++;    col++;                  
              }
              else if(map[row+1][col]==0)//下方 
              {
                   row++;                  
              }
              else if(map[row+1][col-1]==0 )//左下方 
              {
                   row++;    col--;
              }
              else if(map[row][col-1]==0 )//左方 
              {
                   col--;
              }
              else if(map[row-1][col-1]==0 )//左上方 
              {
                   row--;    col--;
              }
              else//當目前的座標位置沒有路可以前進時 
              {   
                  this_point = this_point->forward;
                  //退回前一步 
                  
                  delete(this_point->next);
                  //釋放原位置記憶體 
                  
                  this_point->pop(&row,&col);
                  //pop出前一個位置的座標 
                  
                  continue;
                  //重新判斷是否有方向可以走訪       
              }  
           //如果有路可以走的話，則前進並且紀錄目前的座標 
           
               this_point->next = new RECORD_ROAD;
           //動態配置一個新的節點並且指定給this_point->next這個指標 
           
               this_point->next->forward = this_point;
            //將現在的位置指定給下一個節點中的forward指標   
               
               this_point = this_point->next;
               //位置往前移一格
                
               this_point->push(row,col);
               //將目前座標紀錄下來
                
               map[row][col] = 1;
               //凡走過，則將該圖上的位置標示為 1 
   }
    print_path(first_point); 
    //將首節點位址pass給function 
                       
    system("PAUSE");
    return EXIT_SUCCESS;
}

void draw_map(bool map[row_size][col_size])
{   
    int row,col;
    for(row=0; row<row_size; row++)
    {
               for(col=0; col<col_size; col++)
               {          
                    if(row==0||row==13)cout<<"-";
               else if(col==0||col==16)cout<<"|";
               else
                   cout<< (map[row][col]== 1? "x":"o");
               }
               cout<<endl;
    }  
}
void gotoxy(int x,int y)//設置列印座標 
{
    COORD c;
    c.X = x;
    c.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c);
    //設置終端機滑鼠指標位置 
} 

void print_path(RECORD_ROAD* first_point)//列印出路徑 
{
     int row,col;
     RECORD_ROAD* this_point;
     //列印出可以走到終點的路徑 
     
      this_point=first_point; 
     //從第一個節點開始 
     
      while(this_point!=NULL)
      {  //當節點不存在時候就跳出  
    
           this_point->pop(&row,&col);//將走訪過路徑pop出來 
           
           gotoxy(col,row);//col行，代表是x座標；row列，代表是y座標 
           
           cout<<static_cast<char>(1);
           _sleep(300);//is included in stdlib.h參數為毫秒 300->0.3秒 
           
           this_point = this_point->next;
           //靠著next來移動節點
      }  
}

版本4

//用此類別來紀錄走訪過的路，含有堆疊的特性 
#ifndef RECORD_H
#define RECORD_H
class RECORD_ROAD
{
      private:
              int row,col;
      public:
             void pop(int* r,int* c){*r = row; *c = col;}
             void push(int r,int c){row = r;col = c;}
             RECORD_ROAD* forward,*next;//雙向鏈結 
};
#endif

#ifndef DIRECTION_H
#define DIRECTION_H
//利用列舉型態名稱來作為陣列的索引值，將索引值帶入則可以得到方向值 
enum DIR{top, r_top, right, r_down, down, l_down, left, l_top};
short r_value[8] = {-1,-1,0,1,1, 1, 0,-1};
short c_value[8] = { 0, 1,1,1,0,-1,-1,-1};
#endif

/*題目：老鼠走迷宮鏈結串列版，以該迷宮一定有路徑可以達到終點為前提 
1.使用雙向鏈結串列來儲存走訪的路徑，可達到節省記憶體的效果
2.使用enum來建立方向表，利用方向表來走訪(請見direction.h) 
*/
#include <cstdlib>
#include <iostream>
#include "record.h"//RECORD_ROAD類別與實做的宣告 
#include "direction.h"
#include <windows.h>//COORD結構的宣告 
using namespace std;


const int row_size = 14;//迷宮圖列 
const int col_size = 17;//迷宮圖行 

void draw_map(bool map[row_size][col_size]);//畫出迷宮圖 
void gotoxy(int x,int y);//設置列印座標 
void print_path(RECORD_ROAD* first_point);//列印出路徑 


     
int main(int argc, char *argv[])
{
//將迷宮的外層圍一層牆壁 
bool map[row_size][col_size] = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
                                {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
                                {1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
                                {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
                                {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
                                {1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
                                {1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},
                                {1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1},
                                {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1},
                                {1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
                                {1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
                                {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
   bool go_ahead;
   int row = 1,col = 1;//起點(1,1) 
   RECORD_ROAD *first_point,*this_point;
   
   
   draw_map(map);//畫出迷宮圖案  
   this_point = first_point = new RECORD_ROAD;//建立第一個節點 
   this_point->push(row,col);//push (1,1)
   map[row][col] = 1;//凡走過，則將該圖上的位置標示為 1  
   
   //當座標還沒有到達終點之前，繼續走訪 
   while((row != row_size-2)||(col != col_size-2))
   {
         go_ahead = false;
         
        // 判斷八個方向中是否有可以前進的路，由top開始，順時鐘找尋 
         for(int dir = top; dir<=l_top; dir++)
         {
                 //有路可以前進的時候 
              if(map[row+r_value[dir]][col+c_value[dir]] == 0 ) 
              {
                   row += r_value[dir];
                   col += c_value[dir];
                   go_ahead = true;
                   //標記可以前進，以便辨認要執行pop或是push
                    
                   break;//找到可以前進的路，就跳出迴圈 
              }
         }
         //如果go_ahead沒有被標記為true代表目前的位置沒有路可以前進
         //所以要執行pop動作 
         if(! go_ahead) 
         {
              this_point = this_point->forward;
              //退回前一步 
                  
              delete(this_point->next);
              //釋放原位置記憶體 
                  
              this_point->pop(&row,&col);
              //pop出前一個位置的座標 
                  
              continue;
              //重新判斷是否有方向可以走訪 
         }      
         //反之，代表有路可以走，則前進，執行push的動作 
         else
         {
             this_point->next = new RECORD_ROAD;
             //動態配置一個新的節點並且指定給this_point->next這個指標 
           
             this_point->next->forward = this_point;
             //將現在的位置指定給下一個節點中的forward指標   
               
             this_point = this_point->next;
             //位置往前移一格
                
             this_point->push(row,col);
             //將目前座標紀錄下來
                
             map[row][col] = 1;
             //凡走過，則將該圖上的位置標示為 1
           } 
   }
    print_path(first_point); 
    //將首節點位址pass給function 
                       
    system("PAUSE");
    return EXIT_SUCCESS;
}

void draw_map(bool map[row_size][col_size])
{   
    int row,col;
    for(row=0; row<row_size; row++)
    {
               for(col=0; col<col_size; col++)
               {          
                    if(row==0||row==13)cout<<"-";
               else if(col==0||col==16)cout<<"|";
               else
                   cout<< (map[row][col]== 1? "x":"o");
               }
               cout<<endl;
    }  
}
void gotoxy(int x,int y)//設置列印座標 
{
    COORD c;
    c.X = x;
    c.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c);
    //設置終端機滑鼠指標位置 
} 

void print_path(RECORD_ROAD* first_point)//列印出路徑 
{
     int row,col;
     RECORD_ROAD* this_point;
     //列印出可以走到終點的路徑 
     
      this_point=first_point; 
     //從第一個節點開始 
     
      while(this_point!=NULL)
      {  //當節點不存在時候就跳出  
    
           this_point->pop(&row,&col);//將走訪過路徑pop出來 
           
           gotoxy(col,row);//col行，代表是x座標；row列，代表是y座標 
           
           cout<<static_cast<char>(1);
           _sleep(300);//is included in stdlib.h參數為毫秒 300->0.3秒 
           
           this_point = this_point->next;
           //靠著next來移動節點
      }  
}

相關文章:
資料結構-老鼠走迷宮

老鼠走迷宮-easyx版本