Java小項目之迷宮遊戲的實現方法

Posted on by

項目要求：

一個網格迷宮由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迷宮小項目內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：