完整項(xiàng)目地址：
https://github.com/richenyunqi/Maze-game
軟件總體框架
該軟件主要分為如下三個(gè)模塊：
- 參數(shù)設(shè)置模塊
- 按鈕功能模塊按鈕功能模塊
- 迷宮主界面模塊迷宮主界面模塊
軟件各模塊介紹
參數(shù)設(shè)置模塊
1.迷宮大小相關(guān)參數(shù)：
- ROWS（即迷宮行數(shù)，默認(rèn)設(shè)置為奇數(shù)，最小值為11，最大值為99，默認(rèn)值為11）；
- COLS（即迷宮列數(shù)，默認(rèn)設(shè)置為奇數(shù)，最小值為11，最大值為99，默認(rèn)值為11）；
- Lattice's width（即組成迷宮的格子的寬度，迷宮格子默認(rèn)設(shè)置為正方形，指定了迷宮格子的寬度相當(dāng)于指定了迷宮格子的大小，默認(rèn)設(shè)置為自然數(shù)，最小值為5，最大值為30，默認(rèn)值為15）。
這些參數(shù)設(shè)置的顯示圖下圖所示：
2.迷宮創(chuàng)建算法相關(guān)參數(shù) 本游戲中創(chuàng)建一個(gè)迷宮的算法有三種：
- Depth First Search Algorithm（深度優(yōu)先搜索算法）
- Randomized Prim's Algorithm（隨機(jī)普利姆算法）
- Recursive Division Algorithm（遞歸分割算法）。 用戶需在同時(shí)也只能在這三種迷宮創(chuàng)建算法中任意選擇一種，默認(rèn)選擇的迷宮創(chuàng)建算法為Depth First Search Algorithm（深度優(yōu)先搜索算法）。迷宮創(chuàng)建算法相關(guān)參數(shù)的顯示圖如下圖所示：
3.迷宮尋路算法相關(guān)參數(shù) 本游戲中走出一個(gè)迷宮的迷宮尋路算法有兩種：
- Depth First Search Algorithm（深度優(yōu)先搜索算法）
- Breadth First Search Algorithm（廣度優(yōu)先搜索算法）。 用戶需在同時(shí)也只能在這兩種迷宮創(chuàng)建算法中任意選擇一種，默認(rèn)選擇的迷宮創(chuàng)建算法為Depth First Search Algorithm（深度優(yōu)先搜索算法）。迷宮尋路算法相關(guān)參數(shù)的顯示圖如下圖所示：
4.整個(gè)參數(shù)設(shè)置模塊的顯示圖如下圖所示：
按鈕功能模塊
本游戲中，按進(jìn)行游戲的主體不同共設(shè)計(jì)兩個(gè)游戲狀態(tài)：
- 用戶進(jìn)行游戲的狀態(tài)
- 計(jì)算機(jī)進(jìn)行游戲的狀態(tài)
本游戲軟件剛剛運(yùn)行時(shí)刻，按鈕功能模塊的顯示圖如下圖所示：
該模塊涉及到的游戲功能按鈕及相關(guān)的適用狀態(tài)有以下六種：
- Restart按鈕：即重新開始游戲按鈕，在用戶進(jìn)行游戲的狀態(tài)和計(jì)算機(jī)進(jìn)行游戲的狀態(tài)兩種狀態(tài)下均可使用。點(diǎn)擊該按鈕，當(dāng)前所有正在進(jìn)行的游戲行為都立刻被終止，程序使用參數(shù)設(shè)置模塊的相關(guān)參數(shù)——用戶選中的迷宮創(chuàng)建算法按照用戶選擇的迷宮行列數(shù)創(chuàng)建一個(gè)新的迷宮，并以用戶選擇的格子寬度顯示在游戲界面上。
- Pause/Continue按鈕：即暫停/繼續(xù)按鈕，只能在用戶進(jìn)行游戲的狀態(tài)下才能使用。在用戶進(jìn)行游戲的狀態(tài)下，點(diǎn)擊Pause按鈕，當(dāng)前迷宮游戲被暫停，游戲計(jì)時(shí)器、游戲計(jì)步器被停止，按鈕上的Pause文字被立刻替換成Continue文字；當(dāng)用戶點(diǎn)擊Continue按鈕時(shí)，被暫停的迷宮游戲可以繼續(xù)進(jìn)行，游戲計(jì)時(shí)器、游戲計(jì)步器也在被停止的地方再次開始，按鈕上的Continue文字被立刻替換成Pause文字。
- Prompt按鈕：即提示按鈕，只能在用戶進(jìn)行游戲的狀態(tài)下才能使用。在用戶進(jìn)行游戲的狀態(tài)下，Prompt按鈕的主要提示功能是在迷宮主界面上會(huì)顯示出一條綠色的由用戶當(dāng)前的游戲位置到迷宮出口處的路徑，進(jìn)而對(duì)用戶走出迷宮的路徑進(jìn)行提示。在用戶點(diǎn)擊Prompt按鈕時(shí)，會(huì)跳出一個(gè)對(duì)話框要求用戶指定提示路徑的顯示時(shí)間，用戶可選擇的顯示時(shí)間有：1s、3s、5s、10s、forever。
- Play do按鈕：即指定游戲轉(zhuǎn)換為用戶進(jìn)行游戲狀態(tài)的按鈕，只能在計(jì)算機(jī)進(jìn)行游戲的狀態(tài)下才能使用。在用戶進(jìn)行游戲的狀態(tài)下，點(diǎn)擊Play do按鈕，當(dāng)前計(jì)算機(jī)進(jìn)行的游戲行為被立刻終止，游戲狀態(tài)切換到用戶進(jìn)行游戲的狀態(tài)，將進(jìn)行游戲的控制權(quán)由計(jì)算機(jī)轉(zhuǎn)交給用戶。
- Computer do按鈕：即指定游戲轉(zhuǎn)換為計(jì)算機(jī)進(jìn)行游戲狀態(tài)的按鈕，只能在用戶進(jìn)行游戲的狀態(tài)下才能使用。在用戶進(jìn)行游戲的狀態(tài)下，點(diǎn)擊Computer do按鈕，會(huì)跳出一個(gè)對(duì)話框要求用戶指定計(jì)算機(jī)進(jìn)行游戲時(shí)每走一步的所用速度，用戶可選擇的速度有：lower seed 、low speed、 medium speed、 high speed、 higher speed。用戶選擇后，當(dāng)前用戶進(jìn)行的游戲行為被立刻終止，游戲狀態(tài)切換到計(jì)算機(jī)進(jìn)行游戲的狀態(tài)，將進(jìn)行游戲的控制權(quán)由用戶轉(zhuǎn)交給計(jì)算機(jī)。在計(jì)算機(jī)取得游戲控制權(quán)后，程序?qū)⑹褂脜?shù)設(shè)置模塊中用戶選中的迷宮尋路算法計(jì)算出從游戲入口到游戲出口的路徑，并按用戶進(jìn)行游戲的形式按用戶選擇的進(jìn)行游戲時(shí)每走一步的所用時(shí)間將從入口到出口的行走路徑演示一遍。
- 聲音設(shè)置按鈕：即指定是否開啟背景音樂的按鈕，在用戶進(jìn)行游戲的狀態(tài)和計(jì)算機(jī)進(jìn)行游戲的狀態(tài)兩種狀態(tài)下均可使用。
迷宮主界面模塊
本游戲軟件剛剛運(yùn)行時(shí)刻，迷宮主界面模塊的顯示圖如下圖所示：
整個(gè)迷宮使用大量的方格（正方形）進(jìn)行顯示，其中，可行走的路徑用白色方格顯示，不可行走的路徑即障礙物用黑色方格表示，出口用紅色方格表示，用戶用于行走的標(biāo)識(shí)用綠色小球（圓形）表示。用戶通過鍵盤上上下左右的方向鍵操縱小球在迷宮主界面上運(yùn)動(dòng)。
參數(shù)設(shè)計(jì)模塊中的ROWS（即迷宮行數(shù)）、COLS（即迷宮列數(shù)）在迷宮主界面的表示分別指的是迷宮主界面中每行、每列方格的數(shù)量，參數(shù)設(shè)計(jì)模塊中的Lattice's width（即組成迷宮的格子的寬度）在迷宮主界面的表示是迷宮主界面中每個(gè)方格的寬。此外，在迷宮主界面模塊的正上方，存在統(tǒng)計(jì)用戶進(jìn)行游戲的當(dāng)前時(shí)刻的所用時(shí)間和所走步數(shù)的計(jì)時(shí)器和計(jì)步器。
迷宮整體界面
軟件設(shè)計(jì)方案
軟件相關(guān)原理說明
要設(shè)計(jì)一款迷宮的游戲軟件，其中最主要也是必須要解決的兩大主要問題就是如何去生成一個(gè)隨機(jī)的迷宮以及如何在一個(gè)隨機(jī)生成的迷宮中找到從迷宮入口到迷宮出口的路徑。在圖論中，這兩個(gè)問題的表示就是：
- 如何隨機(jī)生成一個(gè)無權(quán)連通圖
- 如何在一個(gè)找到一個(gè)無權(quán)連通圖中任意兩點(diǎn)間的路徑
關(guān)于這兩個(gè)問題的解決，目前存在許多算法，本款軟件采取并實(shí)現(xiàn)了目前應(yīng)用最為廣泛的三大隨機(jī)無權(quán)連通圖生成算法：
- Depth First Search Algorithm（深度優(yōu)先搜索算法）
- Randomized Prim's Algorithm（隨機(jī)普利姆算法）
- Recursive Division Algorithm（遞歸分割算法）
以及兩大無權(quán)連通圖遍歷算法：
- Depth First Search Algorithm（深度優(yōu)先搜索算法）
- Breadth First Search Algorithm（廣度優(yōu)先搜索算法）
迷宮生成算法
在對(duì)迷宮生成算法進(jìn)行具體闡述之前，有兩個(gè)概念首先要明確定義一下：迷宮單元和墻。迷宮單元可以映射到無權(quán)連通圖中的點(diǎn)，而墻壁則可以映射到無權(quán)連通圖中兩點(diǎn)之間的邊。如果墻壁是打通的，則記為無權(quán)連通圖中的墻壁兩側(cè)的點(diǎn)間有邊；如果墻壁是沒有打通的，則記為無權(quán)連通圖中的墻壁兩側(cè)的點(diǎn)間沒有邊。要生成一個(gè)隨機(jī)的迷宮，就需要做到迷宮中任意兩個(gè)迷宮單元之間都有一條路徑。
我們用二維數(shù)組表示一個(gè)迷宮，每個(gè)迷宮單元表示為一個(gè)二維數(shù)組元素，由于生成算法的限制，迷宮的行數(shù)和列數(shù)均需設(shè)置為奇數(shù)，在了解了相關(guān)算法原理后，就能明白其中原因。在下列迷宮生成算法執(zhí)行之前，假設(shè)位于奇數(shù)行奇數(shù)列的點(diǎn)為迷宮單元，位于偶數(shù)行或者偶數(shù)列的點(diǎn)為墻壁，且所有的點(diǎn)均初始化為未訪問狀態(tài)、不可通過狀態(tài)。
Depth First Search Algorithm（深度優(yōu)先搜索算法）
算法描述
將起點(diǎn)作為當(dāng)前迷宮單元并標(biāo)記為已訪問
當(dāng)還存在未標(biāo)記的迷宮單元，進(jìn)行循環(huán)
如果當(dāng)前迷宮單元有未被訪問過的的相鄰的迷宮單元
隨機(jī)選擇一個(gè)未訪問的相鄰迷宮單元
將當(dāng)前迷宮單元入棧
移除當(dāng)前迷宮單元與相鄰迷宮單元的墻
標(biāo)記相鄰迷宮單元并用它作為當(dāng)前迷宮單元
如果當(dāng)前迷宮單元不存在未訪問的相鄰迷宮單元，并且棧不空
棧頂?shù)拿詫m單元出棧
令其成為當(dāng)前迷宮單元
生成的迷宮特點(diǎn)
一般來說，Depth First Search Algorithm生成的迷宮極度扭曲，有著一條明顯的主路。生成的51行51列迷宮如下圖所示：
Randomized Prim's Algorithm（隨機(jī)普利姆算法）
算法描述
讓迷宮全是墻.
隨機(jī)選一個(gè)單元格作為迷宮的通路，然后把它的鄰墻放入列表
當(dāng)列表里還有墻時(shí)
從列表里隨機(jī)選一個(gè)墻，如果這面墻分隔的兩個(gè)單元格只有一個(gè)單元格被訪問過
那就從列表里移除這面墻，即把墻打通，讓未訪問的單元格成為迷宮的通路
把這個(gè)格子的墻加入列表
如果墻兩面的單元格都已經(jīng)被訪問過，那就從列表里移除這面墻
生成的迷宮特點(diǎn)
相對(duì)于深度優(yōu)先的算法，Randomized Prim's Algorithm不是優(yōu)先選擇最近選中的單元格，而是隨機(jī)的從所有的列表中的單元格進(jìn)行選擇，新加入的單元格和舊加入的單元格同樣概率會(huì)被選擇，新加入的單元格沒有優(yōu)先權(quán)。因此其分支更多，生成的迷宮更復(fù)雜，岔路更多，難度更大，也更自然。生成的51行51列迷宮如下圖所示：
Recursive Division Algorithm（遞歸分割算法）
算法描述
- 讓迷宮全是迷宮單元
- 隨機(jī)選擇一偶數(shù)行和一偶數(shù)列讓其全部變?yōu)閴?，通過這兩堵墻將整個(gè)迷宮分為四個(gè)子迷宮
- 在3面墻上各挖一個(gè)洞（為了確保連通）
- 如果子迷宮仍可分割成四個(gè)子迷宮，返回1. 繼續(xù)分割子迷宮
生成的迷宮特點(diǎn)
Recursive Division Algorithm十分高效，生成的迷宮較為簡(jiǎn)單，有點(diǎn)像四叉樹，直路多且不扭曲。生成的51行51列迷宮如下圖所示：
迷宮尋路算法
由于迷宮相當(dāng)于連通圖，所以通過使用圖論算法中由任意一點(diǎn)出發(fā)遍歷整個(gè)連通圖的其他所有頂點(diǎn)的遍歷算法即可找到一條從迷宮入口到迷宮出口的路徑，本游戲軟件使用的是目前應(yīng)用最為廣泛的Depth First Search Algorithm（深度優(yōu)先搜索算法）和Breadth First Search Algorithm（廣度優(yōu)先搜索算法）。注意，此時(shí)迷宮中所有可行走的點(diǎn)均視為迷宮單元，所有不可行走的點(diǎn)均視為墻壁。
Depth First Search Algorithm（深度優(yōu)先搜索算法）
算法描述
- 訪問入口頂點(diǎn)v，并以此頂點(diǎn)為當(dāng)前頂點(diǎn)
- 將當(dāng)前頂點(diǎn)的未被訪問的鄰接點(diǎn)壓入棧中
- 彈棧，將彈出的頂點(diǎn)作為當(dāng)前頂點(diǎn)
- 若當(dāng)前頂點(diǎn)沒有未被訪問的鄰接點(diǎn)且棧不空，重復(fù)第3步，否則，重復(fù)第2步
- 重復(fù)第3、4步，直至搜索到出口頂點(diǎn)
生成的路徑特點(diǎn)：
Depth First Search Algorithm 在由Recursive Division Algorithm生成的51行51列迷宮中生成的路徑如下圖所示：
Breadth First Search Algorithm（廣度優(yōu)先搜索算法）
算法描述
- 訪問入口頂點(diǎn)v，并以此頂點(diǎn)為當(dāng)前頂點(diǎn)
- 將當(dāng)前頂點(diǎn)的未被訪問的鄰接點(diǎn)逐個(gè)放入隊(duì)列中
- 隊(duì)首頂點(diǎn)出隊(duì)，并作為當(dāng)前頂點(diǎn)
- 若當(dāng)前頂點(diǎn)沒有未被訪問的鄰接點(diǎn)且隊(duì)列不空，重復(fù)第3步，否則重復(fù)第2步
- 重復(fù)第3、4步，直至搜索到出口頂點(diǎn)
生成的路徑特點(diǎn)：
Breadth First Search Algorithm 在由Recursive Division Algorithm生成的51行51列迷宮中生成的路徑如下圖所示：
以上就是Java實(shí)現(xiàn)的迷宮游戲的詳細(xì)內(nèi)容，更多關(guān)于Java其他項(xiàng)目的資料請(qǐng)關(guān)注W3Cschool其它相關(guān)文章！
