java迷宮算法的理解(遞歸分割,遞歸回溯,深搜,廣搜)
更新時(shí)間：2021年06月12日 10:54:25 作者：Justin3go
本文主要使用的算法（自動(dòng)生成地圖：遞歸分割法、遞歸回溯法；尋找路徑：深度優(yōu)先、廣度優(yōu)先算法），非常具有實(shí)用價(jià)值，需要的朋友可以參考下
最近這學(xué)期做了一個(gè)java迷宮的課程設(shè)計(jì)，這里代碼及其算法邏輯就分享出來。
首先簡(jiǎn)單的說一下其中我使用的算法（自動(dòng)生成地圖：遞歸分割法、遞歸回溯法；尋找路徑：深度優(yōu)先、廣度優(yōu)先算法）
遞歸分割法：
地圖外面一圈被墻圍住，然后在空白區(qū)域生成十字墻壁，再隨機(jī)選擇三面墻，將其打通，這樣就能保證迷宮的流動(dòng)性，再分別對(duì)剛才分好的四個(gè)區(qū)域以同樣的方式執(zhí)行分割，一直遞歸下去，直到空間不足以分割就return。
遞歸回溯法：
遞歸回溯法與深度優(yōu)先算法在大致算法上其實(shí)差不多，具體只有一些細(xì)微的差別，都是通過判斷當(dāng)前點(diǎn)的是四個(gè)方向是否可以通過，當(dāng)某個(gè)點(diǎn)堵住就向上退一步操作。遞歸回溯法具體算法如下：
（1）初始化，建立一個(gè)所有單元格都被墻隔開的迷宮。
（2）從起點(diǎn)開始，以此單元格開始打通墻壁。
（3）以當(dāng)前單元格為基準(zhǔn)，隨機(jī)選擇一個(gè)方向，若此方向的鄰接單元格沒有被訪問過，則打通這兩個(gè)單元格之間的墻壁，并將此單元格作為當(dāng)前單元格，重復(fù)步驟3.
（4）若當(dāng)前單元格之間的四個(gè)鄰接單元格都已經(jīng)被訪問過，則退回到進(jìn)入當(dāng)前單元格的鄰接單元格，且以此單元格為當(dāng)前單元格，重復(fù)步驟3、4。
（5）直至起始點(diǎn)單元格被退回，則算法結(jié)束。
深度優(yōu)先算法和遞歸回溯差不太多，只是把鄰接單元格變?yōu)榈南噜彽膯卧?，就直接是探尋周圍是否有路可走，而不再是打通墻壁了?/p>
廣度優(yōu)先
以步驟為主導(dǎo)，向四周擴(kuò)散，比如第一步往四周走一格，第二步就四周的那幾個(gè)單元格再往他們的四周走一格，一直下去，直到找到終點(diǎn)為止，這樣返回的就是步驟數(shù)，同時(shí)因?yàn)檫@是遍歷了整個(gè)地圖，所以找到的一定是最短的路徑。
深度優(yōu)先：
以路徑為主導(dǎo)，一直找下去，如果堵住了或者遇到已經(jīng)訪問過的，就返回上一格，隨機(jī)另一條路繼續(xù)下去，直到找到終點(diǎn)為止，這種方式找到的路并不是最短的，僅僅提供一條路徑而已。
下面是遞歸分割法、遞歸回溯法以及文件加載地圖實(shí)現(xiàn)的類map
//注意看注釋，不然可能會(huì)看不懂，稍微有點(diǎn)亂
遞歸分割法：RandomMap1(),genMaze(),OpenADoor()//這三種方法實(shí)現(xiàn)，1加載的后面兩種方法，2實(shí)現(xiàn)十字分割，3實(shí)現(xiàn)打開兩點(diǎn)為一線之間的一堵墻。
遞歸回溯法：RandomMap2(),list(),digMaze()//這三種方法實(shí)現(xiàn)，1加載的后面兩種方法，2連接兩格單元格，即把中間的單元格變?yōu)橥罚?實(shí)現(xiàn)如果往下沒路可走就返回一個(gè)單元格進(jìn)行繼續(xù)找路。
文件加載地圖：FileMap()方法
package migong;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.io.File;
public class Map{
Random r = new Random();
int l1,l2;
int x,y;//在回溯法中代表當(dāng)前點(diǎn)
boolean bool2 = true;//使用在getMaze()與list()方法中
//判斷是否執(zhí)行了第二個(gè)if，如果都沒執(zhí)行，說明當(dāng)前點(diǎn)的相鄰點(diǎn)要么被訪問過了，要么在邊界之外，就需要退一步
Map(int l1, int l2){
this.l1 = l1;
this.l2 = l2;
}
Stack<Integer> steps = new Stack<>();
public int[][] RandomMap2(int l1, int l2){//遞歸回溯法自動(dòng)生成迷宮
//規(guī)定0是墻，1是路，2是已經(jīng)被探尋過的單元，也可以看做路
int [][] map = new int[l1][l2];
for(int i = 1;i < l1; i = i + 2) {//初始化迷宮生成所有單元都被墻隔開的迷宮
for(int j = 1; j < l2;j = j + 2) {
map[i][j] = 1;
map[j][i] = 1;
}
}
map[1][1] = 2;
digMaze(1,1,map);
return map;
}
public boolean list(int x, int y, int[][] map) {//(x,y)代表當(dāng)前單元格，初始單元格為起點(diǎn)
this.x = x;
this.y = y;
int isOpen = r.nextInt(4);//0代表左邊，逆時(shí)針旋轉(zhuǎn)
boolean bool1 = true;
//判斷第一個(gè)if是否執(zhí)行，如果四個(gè)都沒執(zhí)行，就遞歸在執(zhí)行一次，因?yàn)橛锌赡茈S機(jī)產(chǎn)生的數(shù)過大，把非邊界路就已經(jīng)給排除了
//分別判斷相鄰四個(gè)點(diǎn)（x,y-2）（x+2,y）（x,y+2）（x-2,y）
switch(isOpen) {
case 0:{
if((this.y-2) > 0 && (this.y- 2) < l2 - 1) {
bool1 = false;
if(map[this.x][this.y-2] == 1) {
map[this.x][this.y-2] = 2;//表示這個(gè)點(diǎn)被訪問了
map[this.x][this.y-1] = 1;//打通墻壁
this.y = this.y - 2;//改變當(dāng)前點(diǎn)
bool2 = false;
steps.push(0);
}
}
}
case 1:{
if((this.x+2) > 0 && (this.x+2) < l1 -1) {
bool1 = false;
if(map[this.x+2][this.y] == 1) {
map[this.x+2][this.y] = 2;
map[this.x+1][this.y] = 1;
this.x = this.x + 2;
bool2 = false;
steps.push(1);
}
}
}
case 2:{
if((this.y+2) > 0 && (this.y+2) < l2 - 1) {
bool1 = false;
if(map[this.x][this.y+2] == 1) {
map[this.x][this.y+2] = 2;
map[this.x][this.y+1] = 1;
this.y = this.y + 2;
bool2 = false;
steps.push(2);
}
}
}
case 3:{
if((this.x-2) > 0 && (this.x-2) < l1 -1) {
bool1 = false;
if(map[this.x-2][this.y] == 1) {
map[this.x-2][this.y] = 2;
map[this.x-1][this.y] = 1;
this.x = this.x - 2;
bool2 = false;
steps.push(3);
}
}
}
default:{
if(bool1) {
list(this.x,this.y,map);
}
}
}
return bool2;
}
public void digMaze(int x, int y, int[][] map) {
this.x = x;
this.y = y;
this.bool2 = true;
//不能將bool2定義在list方法中，因?yàn)檫f歸調(diào)用它會(huì)讓其變?yōu)閠rue但后面switch并不會(huì)到第二層if中
//從而這條注釋下面的if就會(huì)判斷失誤
if(list(this.x,this.y,map)) {
try {
switch((int)steps.pop()) {//當(dāng)當(dāng)前點(diǎn)的下一點(diǎn)全都被訪問了就執(zhí)行退回操作
case 0:{
y = y + 2;
break;
}
case 1:{
x = x -2;
break;
}
case 2:{
y = y - 2;
break;
}
case 3:{
x = x + 2;
}
default:
}
}catch(Exception ex) {
return;
}
}
// if(x == l1 - 2 && y == l2 - 2){//判斷是否到達(dá)終點(diǎn)(l1-2,l2-2)
// return;
// }
// if(map[l1-3][l2-2] == 1 && map[l1-2][l2-3] == 1) {
// return;
// }
if(steps.empty()) {//當(dāng)起始點(diǎn)操作被退回是結(jié)束遞歸，這樣生成的地圖對(duì)比上面兩種要更好些
return;
}
digMaze(this.x,this.y,map);
}
public int[][] RandomMap1(int l1, int l2){//遞歸分割法自動(dòng)生成迷宮
int [][] map = new int[l1][l2];
//0代表墻，1代表路
for(int i = 1; i < l1 - 1; i++) {
for(int j = 1; j < l2 - 1; j++) {
map[i][j] = 1;
}
}
genMaze(1,1,l1,l2,map);
return map;
}
private void openAdoor(int x1, int y1, int x2, int y2, int[][] map) {
//以傳參的兩點(diǎn)為直線，打開這條線的某一點(diǎn),分割的點(diǎn)存在于x1~(x2-1)或y1~(y2-1)
int pos;//打開的那一點(diǎn)
if(x1 == x2) {
pos = y1 + r.nextInt((int)((y2 - y1)/2 + 1))*2;//在奇數(shù)行開門
map[x1][pos] = 1;
}
else if(y1 == y2) {
pos = x1 + r.nextInt((int)((x2 - x1)/2 + 1))*2;//在奇數(shù)列開門
map[pos][y1] = 1;
}
else {
System.out.println("錯(cuò)誤");
}
}
//x,y代表要分割區(qū)域的左上點(diǎn)坐標(biāo),l1代表的行數(shù)，l2代表的列數(shù)
public void genMaze(int x, int y, int l1, int l2, int[][] map) {
int Xpos, Ypos;
if(l1 <= 3 || l2 <= 3)
return;
//Xpos,Ypos只能?。▁或y，l - 1）之間的偶數(shù)，這里是開區(qū)間
//橫著畫線，在偶數(shù)位置畫線,
Xpos = x + r.nextInt((int)(l1/2) - 1)*2 + 1;//Xpos,Ypos相當(dāng)于兩條分割線交叉點(diǎn)的坐標(biāo)
for(int i = y; i < y + l2 - 2;i++) {
map[Xpos][i] = 0;
}
//豎著畫一條線，在偶數(shù)位置畫線
Ypos = y + r.nextInt((int)(l2/2) - 1)*2 + 1;
for(int i = x; i < x + l1 - 2;i++) {
map[i][Ypos] = 0;
}
//隨機(jī)開三扇門，左側(cè)墻壁為1，逆時(shí)針旋轉(zhuǎn)
int isClosed = r.nextInt(4) + 1;
switch (isClosed)
{
case 1://1開234門，依次下去
openAdoor(Xpos + 1, Ypos, x + l1 - 2, Ypos, map);// 2
openAdoor(Xpos, Ypos + 1, Xpos, y + l2 - 2, map);// 3
openAdoor(x, Ypos, Xpos, Ypos, map);// 4
break;
case 2:
openAdoor(Xpos, Ypos + 1, Xpos, y + l2 - 2, map);// 3
openAdoor(x, Ypos, Xpos, Ypos, map);// 4
openAdoor(Xpos, y, Xpos, Ypos, map);// 1
break;
case 3:
openAdoor(x, Ypos, Xpos, Ypos, map);// 4
openAdoor(Xpos, y, Xpos, Ypos, map);// 1
openAdoor(Xpos + 1, Ypos, x + l1 - 2, Ypos, map);// 2
break;
case 4:
openAdoor(Xpos, y, Xpos, Ypos, map);// 1
openAdoor(Xpos + 1, Ypos, x + l1 - 2, Ypos, map);// 2
openAdoor(Xpos, Ypos + 1, Xpos, y + l2 - 2, map);// 3
break;
default:
break;
}
//左上角
genMaze(x, y, Xpos + 2 - x, Ypos + 2 - y, map);
//右上角
genMaze(x, Ypos + 1, Xpos + 2 - x, l2 - Ypos, map);
//左下角
genMaze(Xpos + 1, y, l1 - Xpos, Ypos + 2 - y, map);
//右下角
genMaze(Xpos + 1, Ypos + 1, l1 - Xpos , l2 - Ypos, map);
}
public static int[][] FileMap(String filename) throws Exception{//手動(dòng)生成迷宮的方法
//讀取沒有空格的數(shù)字方陣
File file = new File(filename);
if(!file.exists()) {
System.out.println("文件不存在");
}
Scanner input = new Scanner(file);
int l1 = 0, l2 = 0;//l1代表行數(shù)，l2代表列數(shù)
String[] str = new String[1024];
while(input.hasNext()) {
str[l1++] = input.nextLine();//獲取行數(shù)同時(shí)把每一行分別賦給str數(shù)組的各個(gè)元素
l2 = str[0].length();
}
int [][]map = new int[l1][l2];
for(int i = 0;i < l1;i++) {
for(int j = 0; j < l2;j++) {
map[i][j] = str[i].charAt(j) - '0';//通過兩個(gè)Ascll碼之差獲得其數(shù)值
// map[i][j] = Integer.parseInt(str[i].charAt(j) + "");
}
}
input.close();
return map;
}
public void show(int[][] map,int l1,int l2) {
for(int i = 0; i < l1; i++) {
for(int j = 0; j < l2; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println("\n");
}
}
public static void main(String[] args) throws Exception{
// String filename = "C:\\Users\\21974\\Desktop\\map.txt";
// for(int i = 0; i < 2; i++) {
// for(int j = 0; j < 4; j++) {
// System.out.print(Map.FileMap(filename)[i][j] + " ");
// }
// System.out.println("\n");
// }
int l1 = 15,l2 = 15;//奇數(shù)
Map m = new Map(l1, l2);
m.show(m.RandomMap1(l1, l2),l1,l2);
}
}
下面是深度優(yōu)先與廣度優(yōu)先的類findpath：
package migong;
import java.util.LinkedList;
import java.util.Stack;
public class findPath {
public LinkedList<GPS> steps1 = new LinkedList<>();
public Stack<Integer> steps2 = new Stack<>();
int x,y;
public boolean bool = true;
//判斷是否執(zhí)行了第二個(gè)if，如果都沒執(zhí)行，說明當(dāng)前點(diǎn)的相鄰點(diǎn)是墻，要么被訪問過了，要么在邊界之外，就需要退一步
public String shortestPath(int[][] map,int l1, int l2){//最優(yōu)路徑
//創(chuàng)建一個(gè)方向數(shù)組,方向的優(yōu)先級(jí)為 "下左上右"
Direction[] di = new Direction[] {new Direction(1,0),new Direction(0,-1),new Direction(-1,0),new Direction(0,1)};
//創(chuàng)建一個(gè)字符數(shù)組,其中DLUR分別表示向下、向上、向左、向右走。
StringBuffer[] step = new StringBuffer[] {new StringBuffer("D"),new StringBuffer("L"),new StringBuffer("U"),new StringBuffer("R")};
//創(chuàng)建一個(gè)標(biāo)識(shí)符,判斷迷宮是否有解
boolean b = false;
int x=1,y=1,stepNumber=0;
String startStep = "";//代表空,沒有操作
GPS temp = new GPS(x,y,stepNumber,startStep); //將起始點(diǎn)的信息加入隊(duì)列
map[x][y] = 2; //將當(dāng)前位置標(biāo)記為已經(jīng)走過
steps1.addLast(temp);
Loop:while(!steps1.isEmpty()) {
temp = steps1.poll() ; //彈出隊(duì)頭元素進(jìn)行擴(kuò)展
for(int i=0;i<4;i++) { //按照優(yōu)先級(jí)"下左上右",依次進(jìn)行擴(kuò)展
int row = temp.x + di[i].inc_x;
int col = temp.y + di[i].inc_y;
StringBuffer ts = step[i]; //當(dāng)前方向的字母表示//當(dāng)前方向的字母表示
if(map[row][col] == 1) {
int tempStepNumber = temp.stepNumber+1;
String tempStepPath = temp.stb + ts;
steps1.addLast(new GPS(row,col,tempStepNumber,tempStepPath)); //符合條件的坐標(biāo)加入隊(duì)列
map[row][col] = 2; //將該結(jié)點(diǎn)的值設(shè)為2,擴(kuò)展該結(jié)點(diǎn)
if(row == l1-2 && col == l2-2) { //判斷是否到達(dá)了終點(diǎn)
b = true;
break Loop; //跳出標(biāo)記所在的循環(huán)
}
}
}
}
if(b) {
return steps1.getLast().stb;
}else {return "無解";}
}
public void sMove(int x, int y, int[][] map) {
}
public Stack<Integer> path(int x, int y, int[][] map){//深度優(yōu)先自動(dòng)尋路
map[1][1] = 3;
searchMaze(x,y,map);
return this.steps2;
}
public boolean move(int x, int y,int[][] map){
//分別判斷相鄰四個(gè)點(diǎn)（x,y-1）（x+1,y）（x,y+1）（x-1,y）
switch(0) {//0代表左，逆時(shí)針
case 0:{
if((this.y-1) > 0 && (this.y- 1) < map[0].length - 1) {
if(map[this.x][this.y-1] == 1 || map[this.x][this.y-1] == 2) {
//0代表墻，1代表路，2代表生成迷宮時(shí)被訪問了的路，在這里也相當(dāng)于路，3代表這里找路時(shí)被訪問了的路
map[this.x][this.y-1] = 3;//標(biāo)明改點(diǎn)已經(jīng)走過了
this.y = this.y - 1;//改變當(dāng)前點(diǎn)
bool = false;
steps2.push(0);
break;
}
}
}
case 1:{
if((this.x+1) > 0 && (this.x+1) < map.length -1) {
if(map[this.x+1][this.y] == 1 || map[this.x+1][this.y] == 2) {
map[this.x+1][this.y] = 3;
this.x = this.x + 1;
bool = false;
steps2.push(1);
break;
}
}
}
case 2:{
if((this.y+1) > 0 && (this.y+1) < map[0].length - 1) {
if(map[this.x][this.y+1] == 1 || map[this.x][this.y+1] == 2) {
map[this.x][this.y+1] = 3;
this.y = this.y + 1;
bool = false;
steps2.push(2);
break;
}
}
}
case 3:{
if((this.x-1) > 0 && (this.x-1) < map.length - 1) {
if(map[this.x-1][this.y] == 1 || map[this.x-1][this.y] == 2) {
map[this.x-1][this.y] = 3;
this.x = this.x - 1;
bool = false;
steps2.push(3);
break;
}
}
}
default:
}
return bool;
}
public void searchMaze(int x, int y, int[][] map) {//這里是空返回，以后要調(diào)用棧直接用類名加數(shù)據(jù)名
this.x = x;
this.y = y;
this.bool = true;
if(move(this.x,this.y,map)) {
try {
switch((int)steps2.pop()) {//當(dāng)當(dāng)前點(diǎn)的下一點(diǎn)全都被訪問了就執(zhí)行退回操作
case 0:{
this.y = y + 1;
break;
}
case 1:{
this.x = x - 1;
break;
}
case 2:{
this.y = y - 1;
break;
}
case 3:{
this.x = x + 1;
}
default:
}
}catch(Exception ex) {
return;
}
}
if(map[map.length - 2][map[0].length - 2] == 3){//判斷是否到達(dá)終點(diǎn)(l1-2,l2-2)
return;
}
searchMaze(this.x,this.y,map);
}
public void show(Stack<Integer> stack) {
while(!stack.empty()) {
System.out.println((int)stack.pop());
}
}
public static void main(String[]args) {
int l1 = 5,l2 = 5;
Map m = new Map(l1,l2);
findPath find = new findPath();
int[][] map = m.RandomMap1(l1, l2);
// String s = find.path(l1,l2,map);
// System.out.println(s);
// System.out.println("地圖為");
// m.show(map, l1, l2);
find.path(1,1,map);
System.out.println("路為");
m.show(map, l1, l2);
find.show(find.steps2);
}
}
class Direction{
int inc_x; //x方向的增量
int inc_y; //y方向的增量
public Direction(int inc_x,int inc_y) {
this.inc_x = inc_x;
this.inc_y = inc_y;
}
}
/*
GPS類,成員變量x,y表示坐標(biāo),stepNumber表示步數(shù)
*/
class GPS{
int x;
int y;
int stepNumber;
String stb; //用來記錄路徑
public GPS(int x,int y,int stepNumber,String stb){
this.x = x;
this.y = y;
this.stepNumber = stepNumber;
this.stb = stb;
}
}
能看到這里說明我的文章對(duì)你有所幫助，支持一下唄，第一次寫博客有些還不夠規(guī)范。
到此這篇關(guān)于java迷宮算法的理解(遞歸分割,遞歸回溯,深搜,廣搜)的文章就介紹到這了,更多相關(guān)java迷宮算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
運(yùn)用springboot搭建并部署web項(xiàng)目的示例
這篇文章主要介紹了運(yùn)用springboot搭建并部署web項(xiàng)目的示例，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-06-06
Java中Lambda表達(dá)式的進(jìn)化之路詳解
本文通過示例大家給大家介紹了Java中Lambda表達(dá)式的進(jìn)化之路，感興趣的的朋友一起看看吧，希望能夠給你帶來幫助2021-11-11
2020最新IDEA SpringBoot整合Dubbo的實(shí)現(xiàn)(zookeeper版)
這篇文章主要介紹了2020最新IDEA SpringBoot整合Dubbo(zookeeper版)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
這篇文章主要介紹了詳解Java如何給按鈕添加監(jiān)視器,使用匿名對(duì)象、實(shí)現(xiàn)接口、實(shí)現(xiàn)類、Lambda表達(dá)式、注解等,需要的朋友可以參考下2023-04-04
本篇文章主要介紹了java后臺(tái)接受app上傳的圖片的示例代碼，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-08-08
spring cloud oauth2 實(shí)現(xiàn)用戶認(rèn)證登錄的示例代碼
這篇文章主要介紹了spring cloud oauth2 實(shí)現(xiàn)用戶認(rèn)證登錄的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
Java FTPClient實(shí)現(xiàn)文件上傳下載
這篇文章主要為大家詳細(xì)介紹了Java FTPClient實(shí)現(xiàn)文件上傳下載的相關(guān)資料,需要的朋友可以參考下2016-04-04
Java對(duì)象初始化過程代碼塊和構(gòu)造器的調(diào)用順序
這篇文章主要介紹了Java對(duì)象初始化過程代碼塊和構(gòu)造器的調(diào)用順序，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要給大家介紹了關(guān)于SpringMVC的執(zhí)行過程的相關(guān)資料，文中通過圖文介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者使用SpringMVC具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
JAVA實(shí)現(xiàn)連接本地打印機(jī)并打印文件的實(shí)現(xiàn)代碼
這篇文章主要介紹了JAVA實(shí)現(xiàn)連接本地打印機(jī)并打印文件的實(shí)現(xiàn)代碼,需要的朋友可以參考下2019-10-10