项目要求: 一个网格迷宫由n行n列的单元格组成,每个大院个要么是空地(用0表示),要么是障碍物(用1表示),你的任务是找一条从起点到终点的移动序列,其中只能上下左右移动
项目要求:
一个网格迷宫由n行n列的单元格组成,每个大院个要么是空地(用0表示),要么是障碍物(用1表示),你的任务是找一条从起点到终点的移动序列,其中只能上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中,也不能走到迷宫之外,起点为左上角和终点右下角。
项目功能:
解决迷宫路径查找问题,寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径,0代表可走,1代表能走,找到请输出最终的迷宫和路径信息,找不到请输出不存在有效路径。
思路:
1、定义一个迷宫节点类型(MazeNode)的二维数组
2、初始化每个格子中的value值,给二维数组每个格子存放对象。对象的value值只能为0(当前格子可以走)或者1(当前格子不能走)
3、初始化每个格子四个方向(东西南北)是否是可走状态(0可走,1不可走)
4、开始走迷宫。采用栈操作,记录行走的路径,将左上角元素入栈,判断当前栈顶元素的哪个方向可走,将其中一个可走方向进行入栈操作,知道右下角元素停止。栈中保存走过的路径。注意:如果遇到走入死胡同问题,此时需要将是栈顶元素并且栈顶元素的四个方向都不能行走,此时将其出栈,选择新方向再次入栈,直到右下角元素停止。
代码和运行截图:
迷宫的结点类:
package cc; public class MazeNode { private int value;//迷宫节点数据0或者1 private int i;//迷宫节点所在的行 private int j;//迷宫节点所在的列 private boolean[] state;//当前节点可走或不可走 /*构造*/ public MazeNode(int value,int i,int j) { this.value=value; this.i=i; this.j=j; state=new boolean[Constant.SIZE]; } /*get和set*/ public int getValue() { return value; } public void setValue(int value) { this.value = value; } public int getI() { return i; } public int getJ() { return j; } public void setState(int direction,boolean state) { this.state[direction]=state; } public boolean getState(int direction) { return state[direction]; } }
常量的类:
package cc; public class Constant { public static final int SIZE=4;//四个方向 public static final int EAST=0;//东 public static final int WEAST=1;//西 public static final int SORTH=2;//南 public static final int NORTH=3;//北 public static final int ABLE=0;//可走 }
迷宫类:
package cc; import java.util.Scanner; import java.util.Stack; /* * @author : CC * @data : 2020-12-14 * */ public class Maze { private MazeNode[][] mazeNodes;//迷宫数组 private int column;//列 private int row;//行 private Stack<MazeNode> stack;//栈 /*构造*/ public Maze(int row,int column) { this.mazeNodes=new MazeNode[row][column]; this.column=column; this.row=row; stack=new Stack<MazeNode>(); } /*初始化迷宫*/ private void initValue() { Scanner sc=new Scanner(System.in); System.out.println("请输入迷宫路径:"); for(int i=0;i<row;i++) { for(int j=0;j<column;j++) { this.mazeNodes[i][j]=new MazeNode(sc.nextInt(),i,j); } } sc.close(); } /*初始化迷宫节点的状态*/ private void initState() { for(int i=0;i<row;i++) { for(int j=0;j<column;j++) { if(mazeNodes[i][j].getValue()==Constant.ABLE) { //东 if(j+1<column&&mazeNodes[i][j+1].getValue()==Constant.ABLE) { mazeNodes[i][j].setState(Constant.EAST,true); } //南 if(i+1<row&&mazeNodes[i+1][j].getValue()==Constant.ABLE) { mazeNodes[i][j].setState(Constant.SORTH,true); } //西 if(j-1>=0&&mazeNodes[i][j-1].getValue()==Constant.ABLE) { mazeNodes[i][j].setState(Constant.WEAST,true); } //北 if(i-1>=0&&mazeNodes[i-1][j].getValue()==Constant.ABLE) { mazeNodes[i][j].setState(Constant.NORTH,true); } } } } } /*走迷宫*/ public void goMaze() { initValue(); initState(); if(mazeNodes[0][0].getValue()!=Constant.ABLE) { //如果连起点都不能走的话,就表示没有路径 System.out.println("没有迷宫路径!"); return; } //起点入栈 stack.push(mazeNodes[0][0]); //开始走迷宫 while(!stack.isEmpty()) { MazeNode top=stack.peek();//获取栈顶元素 int i=top.getI(); int j=top.getJ(); if(i==row-1&&j==column-1) { //找到了终点 System.out.println("找到迷宫路径!"); show(); return; } //判断栈顶元素是否是死胡同 if(top.getState(Constant.EAST)==false&&top.getState(Constant.WEAST)==false&&top.getState(Constant.NORTH)==false&&top.getState(Constant.SORTH)==false) { //如果是,直接出栈 stack.pop(); } //判断各个位置是否可走 //由于起点在左上角,所以我们从东边开始判断 if(top.getState(Constant.EAST)) { stack.push(mazeNodes[i][j+1]);//东边入栈 //当前节点的东边false mazeNodes[i][j].setState(Constant.EAST, false); //当前节点的东边节点的西边false mazeNodes[i][j+1].setState(Constant.WEAST, false); } //南 if(top.getState(Constant.SORTH)) { stack.push(mazeNodes[i+1][j]);//南边入栈 mazeNodes[i][j].setState(Constant.SORTH, false); mazeNodes[i+1][j].setState(Constant.NORTH, false); } //西 if(top.getState(Constant.WEAST)) { stack.push(mazeNodes[i][j-1]);//西边入栈 mazeNodes[i][j].setState(Constant.WEAST, false); mazeNodes[i][j-1].setState(Constant.EAST, false); } //北 if(top.getState(Constant.NORTH)) { stack.push(mazeNodes[i-1][j]);//北边入栈 mazeNodes[i][j].setState(Constant.NORTH, false); mazeNodes[i-1][j].setState(Constant.SORTH, false); } } System.out.println("此迷宫无解!"); } /*输出路径*/ private void show(){ while (!stack.isEmpty()) { MazeNode top = stack.peek();// 获取栈顶元素 top.setValue(2); stack.pop();// 出栈操作 } System.out.println("所找到的路径为值2的坐标:"); for(int i = 0;i<row;i++){ for(int j = 0;j<column;j++){ System.out.print(mazeNodes[i][j].getValue()+" "); } System.out.println(); } } }
测试类:
package cc; public class Test { public static void main(String[] args) { Maze t1=new Maze(4,5); t1.goMaze(); } }
运行截图:
如有不足和建议,欢迎指正和讨论。
总结
到此这篇关于Java小项目之迷宫游戏实现的文章就介绍到这了,更多相关Java迷宫小项目内容请搜索易盾网络以前的文章或继续浏览下面的相关文章希望大家以后多多支持易盾网络!