Flutter隨機(jī)迷宮生成和解迷宮小游戲功能的源碼
此博客旨在幫助大家更好的了解圖的遍歷算法,通過Flutter移動端平臺將圖的遍歷算法運(yùn)用在迷宮生成和解迷宮上,讓算法變成可視化且可以進(jìn)行交互,最終做成一個可進(jìn)行隨機(jī)迷宮生成和解迷宮的APP小游戲。本人是應(yīng)屆畢業(yè)生,希望能與大家一起討論和學(xué)習(xí)~
注:由于這是本人第一次寫博客,難免排版或用詞上有所欠缺,請大家多多包涵。
注:如需轉(zhuǎn)載文章,請注明出處,謝謝。
一、項(xiàng)目介紹:
1.概述
項(xiàng)目名:方塊迷宮
作者:沫小亮。
編程框架與語言:Flutter&Dart
開發(fā)環(huán)境:Android Studio 3.6.2
學(xué)習(xí)參考:慕課網(wǎng)-看得見的算法
項(xiàng)目完整源碼地址:(待更新)
游戲截圖:
2.迷宮生成原理
1.采用圖的遍歷進(jìn)行迷宮生成,其本質(zhì)就是生成一棵樹,樹中每個節(jié)點(diǎn)只能訪問一次,且每個節(jié)點(diǎn)之間沒有環(huán)路(迷宮的正確路徑只有一條)。
2.初始化:設(shè)置起點(diǎn)和終點(diǎn)位置,并給所有行坐標(biāo)為奇數(shù)且列坐標(biāo)為奇數(shù)的位置設(shè)置為路。其余位置設(shè)置為墻。(坐標(biāo)從0…開始算)
(如下圖,藍(lán)色位置為墻,橙色位置為路,橙色線條為可能即將打通的路,此圖來源于慕課網(wǎng)-看得見的算法)
3.在遍歷過程中,不斷遍歷每個位置,同時遍歷過的位置設(shè)為已訪問位置,結(jié)合迷宮生成算法(見迷宮特點(diǎn)第6點(diǎn))讓相鄰某個墻變成路,使之路徑聯(lián)通。直至所有位置都遍歷完成則迷宮生成結(jié)束(每個節(jié)點(diǎn)只能遍歷一次)。
(如下圖,藍(lán)色位置為墻,橙色位置為路,橙色線條為可能即將打通的路,此圖來源于慕課網(wǎng)-看得見的算法)
3.迷宮特點(diǎn)(可根據(jù)需求自行擴(kuò)展)
1.迷宮只有一個起點(diǎn)、一個終點(diǎn),且起點(diǎn)和終點(diǎn)的位置固定。
2.迷宮的正確路徑只有一條。
3.迷宮的正確路徑是連續(xù)的。
4.迷宮地圖是正方形,且方塊行數(shù)和列數(shù)都為奇數(shù)。
5.迷宮中每個方塊占用一個單元格。
6.迷宮生成算法:圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷相結(jié)合 + 隨機(jī)隊(duì)列(入隊(duì)和出隊(duì)隨機(jī)在隊(duì)頭或隊(duì)尾)+ 隨機(jī)方向遍歷順序(提高迷宮的隨機(jī)性)。
7.迷宮自動求解算法:圖的深度優(yōu)先遍歷(遞歸方法)。
4.玩法介紹(可根據(jù)需求自行擴(kuò)展)
1.游戲共設(shè)置有10個關(guān)卡,到達(dá)終點(diǎn)可以進(jìn)入下一關(guān),隨著關(guān)卡數(shù)的增加,迷宮地圖大?。ǚ綁K數(shù))增加,但限定時間也會增加。
2.點(diǎn)擊方向鍵可對玩家角色的位置進(jìn)行控制。
2.每個關(guān)卡都有限定時間,超過限定時間仍未到達(dá)終點(diǎn)則闖關(guān)失敗,可從本關(guān)繼續(xù)挑戰(zhàn)。
3.每個關(guān)卡都可以使用一次提示功能,可展示2秒的正確路徑,便于小白玩家入門。
4. 顏色對應(yīng):
藍(lán)灰色方塊->墻(不可經(jīng)過)
藍(lán)色方塊->玩家角色(可控制移動)
白色方塊->路(可經(jīng)過)
深橘色->終點(diǎn)(通關(guān))
橙色->正確路徑(提示功能)
二、項(xiàng)目源碼(主要部分):
pubspec.yaml //flutter配置清單
dependencies: flutter: sdk: flutter //toast庫 fluttertoast: ^3.1.3 //Cupertino主題圖標(biāo)集 cupertino_icons: ^0.1.2
maze_game_model.dart //迷宮游戲數(shù)據(jù)層
class MazeGameModel { int _rowSum; //迷宮行數(shù) int _columnSum; //迷宮列數(shù) int _startX, _startY; //迷宮入口坐標(biāo)([startX,startY]) int _endX, _endY; //迷宮出口坐標(biāo)([endX,endY]) static final int MAP_ROAD = 1; //1代表路 static final int MAP_WALL = 0; //0代表墻 List<List<int>> mazeMap; //迷宮地形(1代表路,0代表墻) List<List<bool>> visited; //是否已經(jīng)訪問過 List<List<bool>> path; //是否是正確解的路徑 List<List<int>> direction = [ [-1, 0], [0, 1], [1, 0], [0, -1] ]; //迷宮遍歷的方向順序(迷宮趨勢) int spendStepSum = 0; //求解的總步數(shù) int successStepLength = 0; //正確路徑長度 int playerX, playerY; //當(dāng)前玩家坐標(biāo) MazeGameModel(int rowSum, int columnSum) { if (rowSum % 2 == 0 || columnSum % 2 == 0) { throw "model_this->迷宮行數(shù)和列數(shù)不能為偶數(shù)"; } this._rowSum = rowSum; this._columnSum = columnSum; mazeMap = new List<List<int>>(); visited = new List<List<bool>>(); path = new List<List<bool>>(); //初始化迷宮起點(diǎn)與終點(diǎn)坐標(biāo) _startX = 1; _startY = 0; _endX = rowSum - 2; _endY = columnSum - 1; //初始化玩家坐標(biāo) playerX = _startX; playerY = _startY; //初始化迷宮遍歷的方向(上、左、右、下)順序(迷宮趨勢) //隨機(jī)遍歷順序,提高迷宮生成的隨機(jī)性(共12種可能性) for (int i = 0; i < direction.length; i++) { int random = Random().nextInt(direction.length); List<int> temp = direction[random]; direction[random] = direction[i]; direction[i] = temp; } //初始化迷宮地圖 for (int i = 0; i < rowSum; i++) { List<int> mazeMapList = new List(); List<bool> visitedList = new List(); List<bool> pathList = new List(); for (int j = 0; j < columnSum; j++) { //行和列都為基數(shù)則設(shè)置為路,否則設(shè)置為墻 if (i % 2 == 1 && j % 2 == 1) { mazeMapList.add(1); //設(shè)置為路 } else { mazeMapList.add(0); //設(shè)置為墻 } visitedList.add(false); pathList.add(false); } mazeMap.add(mazeMapList); visited.add(visitedList); path.add(pathList); } //初始化迷宮起點(diǎn)與終點(diǎn)位置 mazeMap[_startX][_startY] = 1; mazeMap[_endX][_endY] = 1; } //返回迷宮行數(shù) int getRowSum() { return _rowSum; } //返回迷宮列數(shù) int getColumnSum() { return _columnSum; } //返回迷宮入口X坐標(biāo) int getStartX() { return _startX; } //返回迷宮入口Y坐標(biāo) int getStartY() { return _startY; } //返回迷宮出口X坐標(biāo) int getEndX() { return _endX; } //返回迷宮出口Y坐標(biāo) int getEndY() { return _endY; } //判斷[i][j]是否在迷宮地圖內(nèi) bool isInArea(int i, int j) { return i >= 0 && i < _rowSum && j >= 0 && j < _columnSum; } }
position.dart //位置類(實(shí)體類)
注:x對應(yīng)二維數(shù)組中的行下標(biāo),y對應(yīng)二維數(shù)組中的列下標(biāo)(往后也是)
class Position extends LinkedListEntry<Position>{ int _x, _y; //X對應(yīng)二維數(shù)組中的行下標(biāo),y對應(yīng)二維數(shù)組中的列下標(biāo) Position _prePosition; //存儲上一個位置 Position(int x, int y, { Position prePosition = null } ) { this._x = x; this._y = y; this._prePosition = prePosition; } //返回X坐標(biāo)() int getX() { return _x; } //返回Y坐標(biāo)() int getY() { return _y; } //返回上一個位置 Position getPrePosition() { return _prePosition; } }
random_queue.dart //隨機(jī)隊(duì)列
入隊(duì):頭部或尾部(各50%的概率)
出隊(duì):頭部或尾部(各50%的概率)
底層數(shù)據(jù)結(jié)構(gòu):LinkedList
class RandomQueue { LinkedList<Position> _queue; RandomQueue(){ _queue = new LinkedList(); } //往隨機(jī)隊(duì)列里添加一個元素 void addRandom(Position position) { if (Random().nextInt(100) < 50) { //從頭部添加 _queue.addFirst(position); } //從尾部添加 else { _queue.add(position); } } //返回隨機(jī)隊(duì)列中的一個元素 Position removeRandom() { if (_queue.length == 0) { throw "數(shù)組元素為空"; } if (Random().nextInt(100) < 50) { //從頭部移除 Position position = _queue.first; _queue.remove(position); return position; } else { //從尾部移除 Position position = _queue.last; _queue.remove(position); return position; } } //返回隨機(jī)隊(duì)列元素?cái)?shù)量 int getSize() { return _queue.length; } //判斷隨機(jī)隊(duì)列是否為空 bool isEmpty() { return _queue.length == 0; } }
main.dart //迷宮游戲視圖層和控制層
1. APP全局設(shè)置
void main() => runApp(MyApp()); class MyApp extends StatelessWidget { @override Widget build(BuildContext context) { if (Platform.isAndroid) { // 以下兩行 設(shè)置android狀態(tài)欄為透明的沉浸。寫在組件渲染之后,是為了在渲染后進(jìn)行set賦值,覆蓋狀態(tài)欄,寫在渲染之前MaterialApp組件會覆蓋掉這個值。 SystemUiOverlayStyle systemUiOverlayStyle = SystemUiOverlayStyle(statusBarColor: Colors.transparent); SystemChrome.setSystemUIOverlayStyle(systemUiOverlayStyle); } return MaterialApp( title: '方塊迷宮', //應(yīng)用名 theme: ThemeData( primarySwatch: Colors.blue, //主題色 ), debugShowCheckedModeBanner: false, //不顯示debug標(biāo)志 home: MyHomePage(), //主頁面 ); } }
2.界面初始化
class MyHomePage extends StatefulWidget { MyHomePage({Key key}) : super(key: key); @override _MyHomePageState createState() => _MyHomePageState(); } class _MyHomePageState extends State<MyHomePage> { int gameWidth, gameHeight; //游戲地圖寬度和高度 double itemWidth, itemHeight; //每個小方塊的寬度和高度 int level = 1; //當(dāng)前關(guān)卡數(shù)(共10關(guān)) int rowSum = 15; //游戲地圖行數(shù) int columnSum = 15; //游戲地圖列數(shù) int surplusTime; //游戲剩余時間 bool isTip = false; //是否使用提示功能 Timer timer; //計(jì)時器 MazeGameModel _model; //迷宮游戲數(shù)據(jù)層 //初始化狀態(tài) @override void initState() { super.initState(); _model = new MazeGameModel(rowSum, columnSum); //新建一個事件循環(huán)隊(duì)列,確保不堵塞主線程 new Future(() { //生成一個迷宮 _doGenerator(_model.getStartX(), _model.getStartY() + 1); }); //設(shè)置倒計(jì)時 _setSurplusTime(level); }
3.界面整體結(jié)構(gòu)
@override Widget build(BuildContext context) { //獲取手機(jī)屏幕寬度,并讓屏幕高度等于屏幕寬度(確保形成正方形迷宮區(qū)域) //結(jié)果向下取整,避免出現(xiàn)實(shí)際地圖寬度大于手機(jī)屏幕寬度的情況 gameHeight = gameWidth = MediaQuery.of(context).size.width.floor(); //每一個小方塊的寬度和長度(屏幕寬度/列數(shù)) itemHeight = itemWidth = (gameWidth / columnSum); return Scaffold( appBar: PreferredSize( //設(shè)置標(biāo)題欄高度 preferredSize: Size.fromHeight(40), //標(biāo)題欄區(qū)域 child: _appBarWidget()), body: ListView( children: <Widget>[ //游戲地圖區(qū)域 _gameMapWidget(), //游戲提示與操作欄區(qū)域 _gameTipWidget(), //游戲方向控制區(qū)域 _gameControlWidget(), ], ), ); }
4.游戲地圖區(qū)域
注:由于游戲提示與操作欄區(qū)域、游戲方向鍵控制區(qū)域不是本文章要講的重點(diǎn),故不詳細(xì)介紹,有興趣的朋友可以到完整項(xiàng)目源碼地址中查看。
//游戲地圖區(qū)域 Widget _gameMapWidget(){ return Container( width: gameHeight.toDouble(), height: gameHeight.toDouble(), color: Colors.white, child: Center( //可堆疊布局(配合Positioned絕對布局使用) child: Stack( //按行遍歷 children: List.generate(_model.mazeMap.length, (i) { return Stack( //按列遍歷 children: List.generate(_model.mazeMap[i].length, (j) { //絕對布局 return Positioned( //每個方塊的位置 left: j * itemWidth.toDouble(), top: i * itemHeight.toDouble(), //每個方塊的大小和顏色 child: Container( width: itemWidth.toDouble(), height: itemHeight.toDouble(), //位于頂層的顏色應(yīng)放在前面進(jìn)行判斷,避免被其他顏色覆蓋 //墻->藍(lán)灰色 //路->白色 //玩家角色->藍(lán)色 //迷宮終點(diǎn)-> 深橘色 //迷宮正確路徑->橙色 color: _model.mazeMap[i][j] == 0 ? Colors.blueGrey : (_model.playerX == i && _model.playerY == j) ? Colors.blue : (_model.getEndX() == i && _model.getEndY() == j) ? Colors.deepOrange : _model.path[i][j] ? Colors.orange : Colors.white)); })); }), ), )); }
5.生成迷宮
//開始生成迷宮地圖 void _doGenerator(int x, int y) { RandomQueue queue = new RandomQueue(); //設(shè)置起點(diǎn) Position start = new Position(x, y); //入隊(duì) queue.addRandom(start); _model.visited[start.getX()][start.getY()] = true; while (queue.getSize() != 0) { //出隊(duì) Position curPosition = queue.removeRandom(); //對上、下、左、右四個方向進(jìn)行遍歷,并獲得一個新位置 for (int i = 0; i < 4; i++) { int newX = curPosition.getX() + _model.direction[i][0] * 2; int newY = curPosition.getY() + _model.direction[i][1] * 2; //如果新位置在地圖范圍內(nèi)且該位置沒有被訪問過 if (_model.isInArea(newX, newY) && !_model.visited[newX][newY]) { //入隊(duì) queue.addRandom(new Position(newX, newY, prePosition: curPosition)); //設(shè)置該位置為已訪問 _model.visited[newX][newY] = true; //設(shè)置該位置為路 _setModelWithRoad(curPosition.getX() + _model.direction[i][0], curPosition.getY() + _model.direction[i][1]); } } } }
6.自動解迷宮(提示功能)
//自動解迷宮(提示功能) //從起點(diǎn)位置開始(使用遞歸的方式)求解迷宮,如果求解成功則返回true,否則返回false bool _doSolver(int x, int y) { if (!_model.isInArea(x, y)) { throw "坐標(biāo)越界"; } //設(shè)置已訪問 _model.visited[x][y] = true; //設(shè)置該位置為正確路徑 _setModelWithPath(x, y, true); //如果該位置為終點(diǎn)位置,則返回true if (x == _model.getEndX() && y == _model.getEndY()) { return true; } //對四個方向進(jìn)行遍歷,并獲得一個新位置 for (int i = 0; i < 4; i++) { int newX = x + _model.direction[i][0]; int newY = y + _model.direction[i][1]; //如果該位置在地圖范圍內(nèi),且該位置為路,且該位置沒有被訪問過,則繼續(xù)從該點(diǎn)開始遞歸求解 if (_model.isInArea(newX, newY) && _model.mazeMap[newX][newY] == MazeGameModel.MAP_ROAD && !_model.visited[newX][newY]) { if (_doSolver(newX, newY)) { return true; } } } //如果該位置不是正確的路徑,則將該位置設(shè)置為非正確路徑所途徑的位置 _setModelWithPath(x, y, false); return false; }
7.控制玩家角色移動
移動到新位置
//控制玩家角色移動 void _doPlayerMove(String direction) { switch (direction) { case "上": //如果待移動的目標(biāo)位置在迷宮地圖內(nèi),且該位置是路,則進(jìn)行移動 if (_model.isInArea(_model.playerX - 1, _model.playerY) && _model.mazeMap[_model.playerX - 1][_model.playerY] == 1) { setState(() { _model.playerX--; }); } break; //省略其他三個方向的代碼
玩家到達(dá)終點(diǎn)位置
//如果玩家角色到達(dá)終點(diǎn)位置 if (_model.playerX == _model.getEndX() && _model.playerY == _model.getEndY()) { isTip = false; //刷新可提示次數(shù) timer.cancel(); //取消倒計(jì)時 //如果當(dāng)前關(guān)是第10關(guān) if (level == 10) { showDialog( barrierDismissible: false, context: context, builder: (BuildContext context) { return AlertDialog( content: Text("你已成功挑戰(zhàn)10關(guān),我看你骨骼驚奇,適合玩迷宮(狗頭"), actions: <Widget>[ new FlatButton( child: new Text('繼續(xù)挑戰(zhàn)第10關(guān)(新地圖)', style: TextStyle(fontSize: 16)), onPressed: () { setState(() { _model.playerX = _model.getStartX(); _model.playerY = _model.getStartY(); }); //重新初始化數(shù)據(jù) _model = new MazeGameModel(rowSum, columnSum); //生成迷宮和設(shè)置倒計(jì)時 _doGenerator(_model.getStartX(), _model.getStartY() + 1); _setSurplusTime(level); Navigator.of(context).pop(); }, ) ], ); }); } //如果當(dāng)前關(guān)不是第10關(guān) else { showDialog( barrierDismissible: false, context: context, builder: (BuildContext context) { return AlertDialog( content: Text("恭喜闖關(guān)成功"), actions: <Widget>[ new FlatButton( child: new Text('挑戰(zhàn)下一關(guān)', style: TextStyle(fontSize: 16)), onPressed: () { setState(() { //關(guān)卡數(shù)+1,玩家角色回到起點(diǎn) level++; _model.playerX = _model.getStartX(); _model.playerY = _model.getStartY(); }); //重新初始化數(shù)據(jù) _model = new MazeGameModel(rowSum = rowSum + 4, columnSum = columnSum + 4); //生成迷宮和設(shè)置倒計(jì)時 _doGenerator(_model.getStartX(), _model.getStartY() + 1); _setSurplusTime(level); Navigator.of(context).pop(); }, ) ], ); }); } }
注:其他與控制邏輯相關(guān)的方法不在此文中詳細(xì)介紹,有興趣的朋友可以到完整項(xiàng)目源碼地址中瀏覽。
總結(jié)
到此這篇關(guān)于Flutter隨機(jī)迷宮生成和解迷宮小游戲功能的源碼的文章就介紹到這了,更多相關(guān)Flutter迷宮小游戲內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Android基于Xposed修改微信運(yùn)動步數(shù)實(shí)例
這篇文章主要介紹了Android基于Xposed修改微信運(yùn)動步數(shù)實(shí)例,需要的朋友可以參考下2017-06-06Android編程實(shí)現(xiàn)通訊錄中聯(lián)系人的讀取,查詢,添加功能示例
這篇文章主要介紹了Android編程實(shí)現(xiàn)通訊錄中聯(lián)系人的讀取,查詢,添加功能,涉及Android權(quán)限控制及通訊錄相關(guān)操作技巧,需要的朋友可以參考下2017-07-07Android 個人理財(cái)工具五:顯示賬單明細(xì) 上
本文主要介紹 Android 個人理財(cái)工具顯示賬單明細(xì),這里提供了示例代碼,和實(shí)現(xiàn)效果圖,幫助大家學(xué)習(xí)理解ListView的用法,有興趣的小伙伴可以參考下2016-08-08解決android studio引用遠(yuǎn)程倉庫下載慢(JCenter下載慢)
這篇文章主要介紹了解決android studio引用遠(yuǎn)程倉庫下載慢(JCenter下載慢),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03Android中TextView局部變色功能實(shí)現(xiàn)
這篇文章給大家詳細(xì)講解了一下Android中TextView實(shí)現(xiàn)部分文字不同顏色的功能實(shí)現(xiàn)過程,有這方面需要的朋友們一起學(xué)習(xí)下吧。2017-12-12Android?通過productFlavors實(shí)現(xiàn)多渠道打包方法示例
這篇文章主要為大家介紹了Android?通過productFlavors實(shí)現(xiàn)多渠道打包方法示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-02-02Android實(shí)現(xiàn)上拉加載更多以及下拉刷新功能(ListView)
這篇文章主要介紹了Android實(shí)現(xiàn)上拉加載更多功能以及下拉刷新功能的相關(guān)資料,需要的朋友可以參考下2016-01-01Android裁剪圖片為圓形圖片的實(shí)現(xiàn)原理與代碼
這個方法是根據(jù)傳入的圖片的高度(height)和寬度(width)決定的,如果是 width <= height時,則會裁剪高度,裁剪的區(qū)域是寬度不變高度從頂部到寬度width的長度2013-01-01