Java實現的迷宮遊戲

Posted on by

完整項目地址：

https://github.com/richenyunqi/Maze-game

軟件總體框架

該軟件主要分為如下三個模塊：

  1. 參數設置模塊
  2. 按鈕功能模塊按鈕功能模塊
  3. 迷宮主界面模塊迷宮主界面模塊

軟件各模塊介紹

參數設置模塊

1.迷宮大小相關參數：

  • ROWS（即迷宮行數，默認設置為奇數，最小值為11，最大值為99，默認值為11）；
  • COLS（即迷宮列數，默認設置為奇數，最小值為11，最大值為99，默認值為11）；
  • Lattice’s width（即組成迷宮的格子的寬度，迷宮格子默認設置為正方形，指定瞭迷宮格子的寬度相當於指定瞭迷宮格子的大小，默認設置為自然數，最小值為5，最大值為30，默認值為15）。

這些參數設置的顯示圖下圖所示：

2.迷宮創建算法相關參數 本遊戲中創建一個迷宮的算法有三種：

  • Depth First Search Algorithm（深度優先搜索算法）
  • Randomized Prim’s Algorithm（隨機普利姆算法）
  • Recursive Division Algorithm（遞歸分割算法）。 用戶需在同時也隻能在這三種迷宮創建算法中任意選擇一種，默認選擇的迷宮創建算法為Depth First Search Algorithm（深度優先搜索算法）。迷宮創建算法相關參數的顯示圖如下圖所示：

3.迷宮尋路算法相關參數 本遊戲中走出一個迷宮的迷宮尋路算法有兩種：

  • Depth First Search Algorithm（深度優先搜索算法）
  • Breadth First Search Algorithm（廣度優先搜索算法）。 用戶需在同時也隻能在這兩種迷宮創建算法中任意選擇一種，默認選擇的迷宮創建算法為Depth First Search Algorithm（深度優先搜索算法）。迷宮尋路算法相關參數的顯示圖如下圖所示：

4.整個參數設置模塊的顯示圖如下圖所示：

按鈕功能模塊

本遊戲中，按進行遊戲的主體不同共設計兩個遊戲狀態：

  • 用戶進行遊戲的狀態
  • 計算機進行遊戲的狀態

本遊戲軟件剛剛運行時刻，按鈕功能模塊的顯示圖如下圖所示：

該模塊涉及到的遊戲功能按鈕及相關的適用狀態有以下六種：

  1. Restart按鈕：即重新開始遊戲按鈕，在用戶進行遊戲的狀態和計算機進行遊戲的狀態兩種狀態下均可使用。點擊該按鈕，當前所有正在進行的遊戲行為都立刻被終止，程序使用參數設置模塊的相關參數——用戶選中的迷宮創建算法按照用戶選擇的迷宮行列數創建一個新的迷宮，並以用戶選擇的格子寬度顯示在遊戲界面上。
  2. Pause/Continue按鈕：即暫停/繼續按鈕，隻能在用戶進行遊戲的狀態下才能使用。在用戶進行遊戲的狀態下，點擊Pause按鈕，當前迷宮遊戲被暫停，遊戲計時器、遊戲計步器被停止，按鈕上的Pause文字被立刻替換成Continue文字；當用戶點擊Continue按鈕時，被暫停的迷宮遊戲可以繼續進行，遊戲計時器、遊戲計步器也在被停止的地方再次開始，按鈕上的Continue文字被立刻替換成Pause文字。
  3. Prompt按鈕：即提示按鈕，隻能在用戶進行遊戲的狀態下才能使用。在用戶進行遊戲的狀態下，Prompt按鈕的主要提示功能是在迷宮主界面上會顯示出一條綠色的由用戶當前的遊戲位置到迷宮出口處的路徑，進而對用戶走出迷宮的路徑進行提示。在用戶點擊Prompt按鈕時，會跳出一個對話框要求用戶指定提示路徑的顯示時間，用戶可選擇的顯示時間有：1s、3s、5s、10s、forever。
  4. Play do按鈕：即指定遊戲轉換為用戶進行遊戲狀態的按鈕，隻能在計算機進行遊戲的狀態下才能使用。在用戶進行遊戲的狀態下，點擊Play do按鈕，當前計算機進行的遊戲行為被立刻終止，遊戲狀態切換到用戶進行遊戲的狀態，將進行遊戲的控制權由計算機轉交給用戶。
  5. Computer do按鈕：即指定遊戲轉換為計算機進行遊戲狀態的按鈕，隻能在用戶進行遊戲的狀態下才能使用。在用戶進行遊戲的狀態下，點擊Computer do按鈕，會跳出一個對話框要求用戶指定計算機進行遊戲時每走一步的所用速度，用戶可選擇的速度有：lower seed 、low speed、 medium speed、 high speed、 higher speed。用戶選擇後，當前用戶進行的遊戲行為被立刻終止，遊戲狀態切換到計算機進行遊戲的狀態，將進行遊戲的控制權由用戶轉交給計算機。在計算機取得遊戲控制權後，程序將使用參數設置模塊中用戶選中的迷宮尋路算法計算出從遊戲入口到遊戲出口的路徑，並按用戶進行遊戲的形式按用戶選擇的進行遊戲時每走一步的所用時間將從入口到出口的行走路徑演示一遍。
  6. 聲音設置按鈕：即指定是否開啟背景音樂的按鈕，在用戶進行遊戲的狀態和計算機進行遊戲的狀態兩種狀態下均可使用。

迷宮主界面模塊

本遊戲軟件剛剛運行時刻，迷宮主界面模塊的顯示圖如下圖所示：

整個迷宮使用大量的方格（正方形）進行顯示，其中，可行走的路徑用白色方格顯示，不可行走的路徑即障礙物用黑色方格表示，出口用紅色方格表示，用戶用於行走的標識用綠色小球（圓形）表示。用戶通過鍵盤上上下左右的方向鍵操縱小球在迷宮主界面上運動。

參數設計模塊中的ROWS（即迷宮行數）、COLS（即迷宮列數）在迷宮主界面的表示分別指的是迷宮主界面中每行、每列方格的數量，參數設計模塊中的Lattice’s width（即組成迷宮的格子的寬度）在迷宮主界面的表示是迷宮主界面中每個方格的寬。此外，在迷宮主界面模塊的正上方，存在統計用戶進行遊戲的當前時刻的所用時間和所走步數的計時器和計步器。

迷宮整體界面

軟件設計方案

軟件相關原理說明

要設計一款迷宮的遊戲軟件，其中最主要也是必須要解決的兩大主要問題就是如何去生成一個隨機的迷宮以及如何在一個隨機生成的迷宮中找到從迷宮入口到迷宮出口的路徑。在圖論中，這兩個問題的表示就是：

  1. 如何隨機生成一個無權連通圖
  2. 如何在一個找到一個無權連通圖中任意兩點間的路徑

關於這兩個問題的解決，目前存在許多算法，本款軟件采取並實現瞭目前應用最為廣泛的三大隨機無權連通圖生成算法：

  • Depth First Search Algorithm（深度優先搜索算法）
  • Randomized Prim’s Algorithm（隨機普利姆算法）
  • Recursive Division Algorithm（遞歸分割算法）

以及兩大無權連通圖遍歷算法：

  • Depth First Search Algorithm（深度優先搜索算法）
  • Breadth First Search Algorithm（廣度優先搜索算法）

迷宮生成算法

在對迷宮生成算法進行具體闡述之前，有兩個概念首先要明確定義一下：迷宮單元和墻。迷宮單元可以映射到無權連通圖中的點，而墻壁則可以映射到無權連通圖中兩點之間的邊。如果墻壁是打通的，則記為無權連通圖中的墻壁兩側的點間有邊；如果墻壁是沒有打通的，則記為無權連通圖中的墻壁兩側的點間沒有邊。要生成一個隨機的迷宮，就需要做到迷宮中任意兩個迷宮單元之間都有一條路徑。

我們用二維數組表示一個迷宮，每個迷宮單元表示為一個二維數組元素，由於生成算法的限制，迷宮的行數和列數均需設置為奇數，在瞭解瞭相關算法原理後，就能明白其中原因。在下列迷宮生成算法執行之前，假設位於奇數行奇數列的點為迷宮單元，位於偶數行或者偶數列的點為墻壁，且所有的點均初始化為未訪問狀態、不可通過狀態。

Depth First Search Algorithm（深度優先搜索算法）

算法描述

將起點作為當前迷宮單元並標記為已訪問

當還存在未標記的迷宮單元，進行循環

如果當前迷宮單元有未被訪問過的的相鄰的迷宮單元

隨機選擇一個未訪問的相鄰迷宮單元
將當前迷宮單元入棧
移除當前迷宮單元與相鄰迷宮單元的墻
標記相鄰迷宮單元並用它作為當前迷宮單元

如果當前迷宮單元不存在未訪問的相鄰迷宮單元，並且棧不空

棧頂的迷宮單元出棧

令其成為當前迷宮單元

生成的迷宮特點

一般來說，Depth First Search Algorithm生成的迷宮極度扭曲，有著一條明顯的主路。生成的51行51列迷宮如下圖所示：

Randomized Prim’s Algorithm（隨機普利姆算法）

算法描述

讓迷宮全是墻.

隨機選一個單元格作為迷宮的通路，然後把它的鄰墻放入列表

當列表裡還有墻時

從列表裡隨機選一個墻，如果這面墻分隔的兩個單元格隻有一個單元格被訪問過

那就從列表裡移除這面墻，即把墻打通，讓未訪問的單元格成為迷宮的通路
把這個格子的墻加入列表

如果墻兩面的單元格都已經被訪問過，那就從列表裡移除這面墻

生成的迷宮特點

相對於深度優先的算法，Randomized Prim’s Algorithm不是優先選擇最近選中的單元格，而是隨機的從所有的列表中的單元格進行選擇，新加入的單元格和舊加入的單元格同樣概率會被選擇，新加入的單元格沒有優先權。因此其分支更多，生成的迷宮更復雜，岔路更多，難度更大，也更自然。生成的51行51列迷宮如下圖所示：

Recursive Division Algorithm（遞歸分割算法）

算法描述

  1. 讓迷宮全是迷宮單元
  2. 隨機選擇一偶數行和一偶數列讓其全部變為墻，通過這兩堵墻將整個迷宮分為四個子迷宮
  3. 在3面墻上各挖一個洞（為瞭確保連通）
  4. 如果子迷宮仍可分割成四個子迷宮，返回1. 繼續分割子迷宮

生成的迷宮特點
Recursive Division Algorithm十分高效，生成的迷宮較為簡單，有點像四叉樹，直路多且不扭曲。生成的51行51列迷宮如下圖所示：

迷宮尋路算法

由於迷宮相當於連通圖，所以通過使用圖論算法中由任意一點出發遍歷整個連通圖的其他所有頂點的遍歷算法即可找到一條從迷宮入口到迷宮出口的路徑，本遊戲軟件使用的是目前應用最為廣泛的Depth First Search Algorithm（深度優先搜索算法）和Breadth First Search Algorithm（廣度優先搜索算法）。註意，此時迷宮中所有可行走的點均視為迷宮單元，所有不可行走的點均視為墻壁。

Depth First Search Algorithm（深度優先搜索算法）

算法描述

  1. 訪問入口頂點v，並以此頂點為當前頂點
  2. 將當前頂點的未被訪問的鄰接點壓入棧中
  3. 彈棧，將彈出的頂點作為當前頂點
  4. 若當前頂點沒有未被訪問的鄰接點且棧不空，重復第3步，否則，重復第2步
  5. 重復第3、4步，直至搜索到出口頂點

生成的路徑特點：
Depth First Search Algorithm 在由Recursive Division Algorithm生成的51行51列迷宮中生成的路徑如下圖所示：

Breadth First Search Algorithm（廣度優先搜索算法）

算法描述

  1. 訪問入口頂點v，並以此頂點為當前頂點
  2. 將當前頂點的未被訪問的鄰接點逐個放入隊列中
  3. 隊首頂點出隊，並作為當前頂點
  4. 若當前頂點沒有未被訪問的鄰接點且隊列不空，重復第3步，否則重復第2步
  5. 重復第3、4步，直至搜索到出口頂點

生成的路徑特點：
Breadth First Search Algorithm 在由Recursive Division Algorithm生成的51行51列迷宮中生成的路徑如下圖所示：

以上就是Java實現的迷宮遊戲的詳細內容，更多關於Java 迷宮遊戲的資料請關註WalkonNet其它相關文章！

推薦閱讀：