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 迷宫游戏的资料请关注我们其它相关文章!

(0)

相关推荐

  • java图的深度优先遍历实现随机生成迷宫

    最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢. 1.从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中的随机一个访问(每访问到一个可访问的点,就去掉该点的那个方向的墙),被访问点继续以这种方识向下进行访问. 2.对每个被访问的点都被标识为已访问,当一个点对某个方向进行访问时我们首先会判断被访问点是否已被访问,或者触到边界.如果该点四个方向皆已访

  • Java编写迷宫小游戏

    缘起: 去年(大三上学期)比较喜欢写小游戏,于是想试着写个迷宫试一下. 程序效果: 按下空格显示路径: 思考过程: 迷宫由一个一个格子组成,要求从入口到出口只有一条路径. 想了一下各种数据结构,似乎树是比较合适的,从根节点到每一个子节点都只有一条路径.假设入口是根节点,出口是树中某个子节点,那么,从根节点到该子节点的路径肯定是唯一的. 所以如果能构造一棵树把所有的格子都覆盖到,也就能够做出一个迷宫了. 另外还要求树的父节点和子节点必须是界面上相邻的格子. 在界面显示时,父节点和子节点之间共用的边

  • Java实现走迷宫回溯算法

    以一个M×N的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍.设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. (1) 根据二维数组,输出迷宫的图形. (2) 探索迷宫的四个方向:RIGHT为向右,DOWN向下,LEFT向左,UP向上,输出从入口到出口的行走路径. 例子: 左上角(1,1)为入口,右下角(8,9)为出口. 可使用回溯方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进:否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通

  • Java小项目之迷宫游戏的实现方法

    项目要求: 一个网格迷宫由n行n列的单元格组成,每个大院个要么是空地(用0表示),要么是障碍物(用1表示),你的任务是找一条从起点到终点的移动序列,其中只能上下左右移动到相邻单元格.任何时候都不能在有障碍物的单元格中,也不能走到迷宫之外,起点为左上角和终点右下角. 项目功能: 解决迷宫路径查找问题,寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径,0代表可走,1代表能走,找到请输出最终的迷宫和路径信息,找不到请输出不存在有效路径. 思路: 1.定义一个迷宫节点类型(MazeNode)的二维

  • java寻找迷宫路径的简单实现示例

    迷宫项目实现设计文档 项目介绍: 一个网格迷宫由n行m列的单元格组成,每个大院个要么是空地(用0表示),要么是障碍物(用1表示).你的任务是找一条从起点到终点的移动序列,其中只能上下左右移动到相邻单元格.任何时候都不能在有障碍物的单元格中,也不能走到迷宫之外.起点为左上角和终点右下角. 项目功能: 解决迷宫路径查找问题,寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径,0代表可走,1代表不能行走,找到请输出最终的迷宫和路径信息,找不到请输出不存在有效路径. 项目所用知识点: 采用Java面

  • Java遗传算法之冲出迷宫

    遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法.它能解决很多问题,比如数学方程的最大最小值,背包问题,装箱问题等.在游戏开发中遗传算法的应用也十分频繁,不少的游戏 AI 都利用遗传算法进行编码. 就个人理解,遗传算法是模拟神奇的大自然中生物"优胜劣汰"原则指导下的进化过程,好的基因有更多的机会得到繁衍,这样一来,随着繁衍的进行,生物种群会朝着一个趋势收敛.而生物繁衍过程中的基因杂交和变异会给种群提供更好的基因序列

  • Java基于深度优先遍历的随机迷宫生成算法

    这两天因为要做一个随机的地图生成系统,所以一直在研究随机迷宫生成算法,好吧,算是有一点小小的成果. 随机迷宫生成我自己的理解简而言之分为以下几步: 1.建立一张地图,我用的二维数组表示,地图上全是障碍物.然后再创建一个用来表示每个格子是否被访问过的二维数组.再创建一个用来表示路径的栈结构. 2.随机选择地图上的一点,呃为了方便我初始点直接取的是左上角即坐标表示为0,0的格子.终点的话因为不涉及到交互就暂时没有. 3.查找当前格子的邻接格(注意,这里的邻接格子都是还未被访问的,下面的代码里有写).

  • java实现单词搜索迷宫游戏

    本文实例讲述了java实现单词搜索迷宫游戏.分享给大家供大家参考.具体分析如下: 我们在杂志上,经常能够看到找单词的小游戏,在一个二维表格中,存在各种字母,我们可以从八个方向找单词.这个用计算机处理十分方便,但是,算法的好坏很重要,因为要是用蛮力算法实现,那么耗费的时间是不可想象的. 这是数据结构与问题求解Java语言描述一书中给的实现思路 完整代码如下,注释写的很明白了 import java.io.BufferedReader; import java.io.FileReader; impo

  • Java项目实现寻找迷宫出路

    本文实例为大家分享了Java实现寻找迷宫出路的具体代码,供大家参考,具体内容如下 项目名称 寻找迷宫出路 项目描述 给定一个自定义迷宫,0表示能通过,1表示不能通过.通过程序找出正确的迷宫出路,并将正确的路线改为2输出. 代码实现 测试类 public class Test { public static void main(String[] args) { Maze maze = new Maze(); maze.begin(); } } 主类:实现主方法 public class Maze

  • 使用栈的迷宫算法java版代码

    本文为大家分享了使用栈的迷宫算法java版,主要考察栈的使用,供大家参考,具体内容如下 主要思路如下: do { if(当前位置可通过) { 标记此位置已走过; 保存当前位置并入栈; if(当前位置为终点) { 程序结束; } 获取下一个位置; } else { if(栈非空) { 出栈: while(当前位置方向为4且栈非空) { 标记当前位置不可走; 出栈; } if(当前位置的方向小于4) { 方向+1; 重新入栈; 获取下一个位置; } } } } while (栈非空); java代码

  • java 实现迷宫回溯算法示例详解

    用一个7 x 7的矩形表示迷宫,0和1分别表示的是通路和障碍.通过设计编写程序找到蓝色小球达到蓝色旗子的路线 思路: 构建一个迷宫(用二维数组)实现找通路的方法findRoad() 构建二维数组不难,我们主要是要实现findRoad()这个方法,在实现这个方法前,我们需要约定好一下几个点:小球的位置当作入口(1,1),小旗的位置当作出口(5,5)数组里数的含义分别为(0没有走过).(1障碍).(2走过且为正确的路线).(3走过且为错误的路线)将我们每一步的走法称为策略:下 -> 右 -> 上

随机推荐