完整項(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按鈕:即重新開(kāi)始游戲按鈕,在用戶進(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ì)步器也在被停止的地方再次開(kāi)始,按鈕上的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è)置按鈕:即指定是否開(kāi)啟背景音樂(lè)的按鈕,在用戶進(jìn)行游戲的狀態(tài)和計(jì)算機(jī)進(jìn)行游戲的狀態(tài)兩種狀態(tài)下均可使用。
迷宮主界面模塊
本游戲軟件剛剛運(yùn)行時(shí)刻,迷宮主界面模塊的顯示圖如下圖所示:
整個(gè)迷宮使用大量的方格(正方形)進(jìn)行顯示,其中,可行走的路徑用白色方格顯示,不可行走的路徑即障礙物用黑色方格表示,出口用紅色方格表示,用戶用于行走的標(biāo)識(shí)用綠色小球(圓形)表示。用戶通過(guò)鍵盤(pán)上上下左右的方向鍵操縱小球在迷宮主界面上運(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)原理說(shuō)明
要設(shè)計(jì)一款迷宮的游戲軟件,其中最主要也是必須要解決的兩大主要問(wèn)題就是如何去生成一個(gè)隨機(jī)的迷宮以及如何在一個(gè)隨機(jī)生成的迷宮中找到從迷宮入口到迷宮出口的路徑。在圖論中,這兩個(gè)問(wèn)題的表示就是:
- 如何隨機(jī)生成一個(gè)無(wú)權(quán)連通圖
- 如何在一個(gè)找到一個(gè)無(wú)權(quán)連通圖中任意兩點(diǎn)間的路徑
關(guān)于這兩個(gè)問(wèn)題的解決,目前存在許多算法,本款軟件采取并實(shí)現(xiàn)了目前應(yīng)用最為廣泛的三大隨機(jī)無(wú)權(quán)連通圖生成算法:
- Depth First Search Algorithm(深度優(yōu)先搜索算法)
- Randomized Prim's Algorithm(隨機(jī)普利姆算法)
- Recursive Division Algorithm(遞歸分割算法)
以及兩大無(wú)權(quán)連通圖遍歷算法:
- Depth First Search Algorithm(深度優(yōu)先搜索算法)
- Breadth First Search Algorithm(廣度優(yōu)先搜索算法)
迷宮生成算法
在對(duì)迷宮生成算法進(jìn)行具體闡述之前,有兩個(gè)概念首先要明確定義一下:迷宮單元和墻。迷宮單元可以映射到無(wú)權(quán)連通圖中的點(diǎn),而墻壁則可以映射到無(wú)權(quán)連通圖中兩點(diǎn)之間的邊。如果墻壁是打通的,則記為無(wú)權(quán)連通圖中的墻壁兩側(cè)的點(diǎn)間有邊;如果墻壁是沒(méi)有打通的,則記為無(wú)權(quán)連通圖中的墻壁兩側(cè)的點(diǎn)間沒(méi)有邊。要生成一個(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)均初始化為未訪問(wèn)狀態(tài)、不可通過(guò)狀態(tài)。
Depth First Search Algorithm(深度優(yōu)先搜索算法)
算法描述
將起點(diǎn)作為當(dāng)前迷宮單元并標(biāo)記為已訪問(wèn)
當(dāng)還存在未標(biāo)記的迷宮單元,進(jìn)行循環(huán)
如果當(dāng)前迷宮單元有未被訪問(wèn)過(guò)的的相鄰的迷宮單元
隨機(jī)選擇一個(gè)未訪問(wèn)的相鄰迷宮單元
將當(dāng)前迷宮單元入棧
移除當(dāng)前迷宮單元與相鄰迷宮單元的墻
標(biāo)記相鄰迷宮單元并用它作為當(dāng)前迷宮單元
如果當(dāng)前迷宮單元不存在未訪問(wèn)的相鄰迷宮單元,并且棧不空
棧頂?shù)拿詫m單元出棧
令其成為當(dāng)前迷宮單元
生成的迷宮特點(diǎn)
一般來(lái)說(shuō),Depth First Search Algorithm生成的迷宮極度扭曲,有著一條明顯的主路。生成的51行51列迷宮如下圖所示:
Randomized Prim's Algorithm(隨機(jī)普利姆算法)
算法描述
讓迷宮全是墻.
隨機(jī)選一個(gè)單元格作為迷宮的通路,然后把它的鄰墻放入列表
當(dāng)列表里還有墻時(shí)
從列表里隨機(jī)選一個(gè)墻,如果這面墻分隔的兩個(gè)單元格只有一個(gè)單元格被訪問(wèn)過(guò)
那就從列表里移除這面墻,即把墻打通,讓未訪問(wèn)的單元格成為迷宮的通路
把這個(gè)格子的墻加入列表
如果墻兩面的單元格都已經(jīng)被訪問(wèn)過(guò),那就從列表里移除這面墻
生成的迷宮特點(diǎn)
相對(duì)于深度優(yōu)先的算法,Randomized Prim's Algorithm不是優(yōu)先選擇最近選中的單元格,而是隨機(jī)的從所有的列表中的單元格進(jìn)行選擇,新加入的單元格和舊加入的單元格同樣概率會(huì)被選擇,新加入的單元格沒(méi)有優(yōu)先權(quán)。因此其分支更多,生成的迷宮更復(fù)雜,岔路更多,難度更大,也更自然。生成的51行51列迷宮如下圖所示:
Recursive Division Algorithm(遞歸分割算法)
算法描述
- 讓迷宮全是迷宮單元
- 隨機(jī)選擇一偶數(shù)行和一偶數(shù)列讓其全部變?yōu)閴?,通過(guò)這兩堵墻將整個(gè)迷宮分為四個(gè)子迷宮
- 在3面墻上各挖一個(gè)洞(為了確保連通)
- 如果子迷宮仍可分割成四個(gè)子迷宮,返回1. 繼續(xù)分割子迷宮
生成的迷宮特點(diǎn)
Recursive Division Algorithm十分高效,生成的迷宮較為簡(jiǎn)單,有點(diǎn)像四叉樹(shù),直路多且不扭曲。生成的51行51列迷宮如下圖所示:
迷宮尋路算法
由于迷宮相當(dāng)于連通圖,所以通過(guò)使用圖論算法中由任意一點(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)先搜索算法)
算法描述
- 訪問(wèn)入口頂點(diǎn)v,并以此頂點(diǎn)為當(dāng)前頂點(diǎn)
- 將當(dāng)前頂點(diǎn)的未被訪問(wèn)的鄰接點(diǎn)壓入棧中
- 彈棧,將彈出的頂點(diǎn)作為當(dāng)前頂點(diǎn)
- 若當(dāng)前頂點(diǎn)沒(méi)有未被訪問(wè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)先搜索算法)
算法描述
- 訪問(wèn)入口頂點(diǎn)v,并以此頂點(diǎn)為當(dāng)前頂點(diǎn)
- 將當(dāng)前頂點(diǎn)的未被訪問(wèn)的鄰接點(diǎn)逐個(gè)放入隊(duì)列中
- 隊(duì)首頂點(diǎn)出隊(duì),并作為當(dāng)前頂點(diǎn)
- 若當(dāng)前頂點(diǎn)沒(méi)有未被訪問(wè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)文章!