完整項目地址：

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

軟件總體框架

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

1. 參數(shù)設(shè)置模塊
2. 按鈕功能模塊按鈕功能模塊
3. 迷宮主界面模塊迷宮主界面模塊
   

軟件各模塊介紹

參數(shù)設(shè)置模塊

1.迷宮大小相關(guān)參數(shù)：

• ROWS（即迷宮行數(shù)，默認設(shè)置為奇數(shù)，最小值為11，最大值為99，默認值為11）；
• COLS（即迷宮列數(shù)，默認設(shè)置為奇數(shù)，最小值為11，最大值為99，默認值為11）；
• Lattice's width（即組成迷宮的格子的寬度，迷宮格子默認設(shè)置為正方形，指定了迷宮格子的寬度相當(dāng)于指定了迷宮格子的大小，默認設(shè)置為自然數(shù)，最小值為5，最大值為30，默認值為15）。
  

這些參數(shù)設(shè)置的顯示圖下圖所示：

2.迷宮創(chuàng)建算法相關(guān)參數(shù) 本游戲中創(chuàng)建一個迷宮的算法有三種：

• Depth First Search Algorithm（深度優(yōu)先搜索算法）
• Randomized Prim's Algorithm（隨機普利姆算法）
• Recursive Division Algorithm（遞歸分割算法）。 用戶需在同時也只能在這三種迷宮創(chuàng)建算法中任意選擇一種，默認選擇的迷宮創(chuàng)建算法為Depth First Search Algorithm（深度優(yōu)先搜索算法）。迷宮創(chuàng)建算法相關(guān)參數(shù)的顯示圖如下圖所示：

3.迷宮尋路算法相關(guān)參數(shù) 本游戲中走出一個迷宮的迷宮尋路算法有兩種：

• Depth First Search Algorithm（深度優(yōu)先搜索算法）
• Breadth First Search Algorithm（廣度優(yōu)先搜索算法）。 用戶需在同時也只能在這兩種迷宮創(chuàng)建算法中任意選擇一種，默認選擇的迷宮創(chuàng)建算法為Depth First Search Algorithm（深度優(yōu)先搜索算法）。迷宮尋路算法相關(guān)參數(shù)的顯示圖如下圖所示：

4.整個參數(shù)設(shè)置模塊的顯示圖如下圖所示：

按鈕功能模塊

本游戲中，按進行游戲的主體不同共設(shè)計兩個游戲狀態(tài)：

• 用戶進行游戲的狀態(tài)
• 計算機進行游戲的狀態(tài)

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

該模塊涉及到的游戲功能按鈕及相關(guān)的適用狀態(tài)有以下六種：

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

迷宮主界面模塊

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

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

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

迷宮整體界面

軟件設(shè)計方案

軟件相關(guān)原理說明

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

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

關(guān)于這兩個問題的解決，目前存在許多算法，本款軟件采取并實現(xiàn)了目前應(yīng)用最為廣泛的三大隨機無權(quán)連通圖生成算法：

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

以及兩大無權(quán)連通圖遍歷算法：

• Depth First Search Algorithm（深度優(yōu)先搜索算法）
• Breadth First Search Algorithm（廣度優(yōu)先搜索算法）
  

迷宮生成算法

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

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

Depth First Search Algorithm（深度優(yōu)先搜索算法）

算法描述

將起點作為當(dāng)前迷宮單元并標記為已訪問

當(dāng)還存在未標記的迷宮單元，進行循環(huán)

如果當(dāng)前迷宮單元有未被訪問過的的相鄰的迷宮單元

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

如果當(dāng)前迷宮單元不存在未訪問的相鄰迷宮單元，并且棧不空

棧頂?shù)拿詫m單元出棧

令其成為當(dāng)前迷宮單元

生成的迷宮特點

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

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

算法描述

讓迷宮全是墻.

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

當(dāng)列表里還有墻時

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

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

如果墻兩面的單元格都已經(jīng)被訪問過，那就從列表里移除這面墻

生成的迷宮特點

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

Recursive Division Algorithm（遞歸分割算法）

算法描述

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

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

迷宮尋路算法

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

Depth First Search Algorithm（深度優(yōu)先搜索算法）

算法描述

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

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

Breadth First Search Algorithm（廣度優(yōu)先搜索算法）

算法描述

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

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

以上就是Java實現(xiàn)的迷宮游戲的詳細內(nèi)容，更多關(guān)于Java其他項目的資料請關(guān)注W3Cschool其它相關(guān)文章！