Java實現的迷宮遊戲

完整專案地址：

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 迷宮遊戲的資料請關注it145.com其它相關文章！