建站
咨詢
售后
建站咨詢
新聞中心
這篇文章主要為大家展示了詳解java圖的深度優(yōu)先遍歷如何實(shí)現(xiàn)隨機(jī)生成迷宮，內(nèi)容簡(jiǎn)而易懂，希望大家可以學(xué)習(xí)一下，學(xué)習(xí)完之后肯定會(huì)有收獲的，下面讓小編帶大家一起來(lái)看看吧。
最近經(jīng)常在機(jī)房看同學(xué)在玩一個(gè)走迷宮的游戲,比較有趣，自己也用java寫(xiě)一個(gè)實(shí)現(xiàn)隨機(jī)生成迷宮的算法，其實(shí)就是一個(gè)圖的深度優(yōu)先遍歷算法.基本思想就是，迷宮中的每個(gè)點(diǎn)都有四面墻，然后呢。
1、從任意一點(diǎn)開(kāi)始訪問(wèn)(我的算法中固定是從(0,0)點(diǎn)開(kāi)始),往四個(gè)方向中的隨機(jī)一個(gè)訪問(wèn)(每訪問(wèn)到一個(gè)可訪問(wèn)的點(diǎn),就去掉該點(diǎn)的那個(gè)方向的墻),被訪問(wèn)點(diǎn)繼續(xù)以這種方識(shí)向下進(jìn)行訪問(wèn)。
2、對(duì)每個(gè)被訪問(wèn)的點(diǎn)都被標(biāo)識(shí)為已訪問(wèn),當(dāng)一個(gè)點(diǎn)對(duì)某個(gè)方向進(jìn)行訪問(wèn)時(shí)我們首先會(huì)判斷被訪問(wèn)點(diǎn)是否已被訪問(wèn),或者觸到邊界.如果該點(diǎn)四個(gè)方向皆已訪問(wèn)或已無(wú)法訪問(wèn),就退回上一個(gè)點(diǎn)。上一個(gè)點(diǎn)繼續(xù)這個(gè)過(guò)程。
這樣一次遍歷下來(lái)，可以確定每個(gè)點(diǎn)都被訪問(wèn)過(guò)，而且由于每次訪問(wèn)的方向都是隨機(jī)，這就會(huì)形成許多不同遍歷情況，同時(shí)每?jī)蓚€(gè)點(diǎn)之間的路徑是唯一，也就形成不同的迷宮，且是起點(diǎn)到終點(diǎn)只有唯一路徑，這是由于圖的深度遍歷算法的特點(diǎn)所決定的。算法的實(shí)現(xiàn)上,主要是利用棧,第一次,先把第一個(gè)點(diǎn)壓進(jìn)棧里,每訪問(wèn)到一個(gè)點(diǎn),就把該點(diǎn)壓進(jìn)棧里,我們?cè)賹?duì)棧頂?shù)狞c(diǎn)進(jìn)行四個(gè)方向的隨機(jī)訪問(wèn),訪問(wèn)到新點(diǎn),又把新點(diǎn)壓進(jìn)去,一旦這個(gè)點(diǎn)四個(gè)方向都無(wú)法訪問(wèn)了,就讓該點(diǎn)退棧,再對(duì)棧頂?shù)狞c(diǎn)的四個(gè)方向進(jìn)行訪問(wèn),以此類推,直到棧里的點(diǎn)都全部退出了,我們的遍歷就成功了,這是一個(gè)遞歸的過(guò)程,這個(gè)算法自然可以用遞歸的方法來(lái)實(shí)現(xiàn),不過(guò)這里我這樣做,而是手工用一個(gè)數(shù)組作為棧來(lái)實(shí)現(xiàn),呵呵~~說(shuō)了這么多,也不知道自己要表達(dá)的有沒(méi)表達(dá)出來(lái)。不過(guò)我感覺(jué)我的具體代碼設(shè)計(jì)還是寫(xiě)的不好，還有很多地方缺乏完善和優(yōu)化,權(quán)當(dāng)是算法練習(xí),以下是兩個(gè)關(guān)鍵類的核心代碼，至于表示層的代碼就不貼出來(lái)了，因?yàn)槟切┒己墁嵥椤?/p>
下面是效果圖:
迷宮的類：
//作者:zhongZw
//郵箱:zhong317@126.com
package cn.zhongZw.model;
import java.util.ArrayList;
import java.util.Random;
public class MazeModel {
private int width = 0;
private int height = 0;
private Random rnd = new Random();
public MazeModel() {
this.width = 50; //迷宮寬度
this.height = 50; //迷宮高度
}
public int getWidth() {
return width;
}
public void setWidth(int width) {
this.width = width;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public MazeModel(int width, int height) {
super();
this.width = width;
this.height = height;
}
public ArrayList < MazePoint > getMaze() {
ArrayList < MazePoint > maze = new ArrayList < MazePoint > ();
for (int h = 0; h < height; h++) {
for (int w = 0; w < width; w++) {
MazePoint point = new MazePoint(w, h);
maze.add(point);
}
}
return CreateMaze(maze);
}
private ArrayList < MazePoint > CreateMaze(ArrayList < MazePoint > maze) {
int top = 0;
int x = 0;
int y = 0;
ArrayList < MazePoint > team = new ArrayList < MazePoint > ();
team.add(maze.get(x + y * width));
while (top >= 0) {
int[] val = new int[] {
-1, -1, -1, -1
};
int times = 0;
boolean flag = false;
MazePoint pt = (MazePoint) team.get(top);
x = pt.getX();
y = pt.getY();
pt.visted = true;
ro1: while (times < 4) {
int dir = rnd.nextInt(4);
if (val[dir] == dir)
continue;
else
val[dir] = dir;
switch (dir) {
case 0: // 左邊
if ((x - 1) >= 0 && maze.get(x - 1 + y * width).visted == false) {
maze.get(x + y * width).setLeft();
maze.get(x - 1 + y * width).setRight();
team.add(maze.get(x - 1 + y * width));
top++;
flag = true;
break ro1;
}
break;
case 1: // 右邊
if ((x + 1) < width && maze.get(x + 1 + y * width).visted == false) {
maze.get(x + y * width).setRight();
maze.get(x + 1 + y * width).setLeft();
team.add(maze.get(x + 1 + y * width));
top++;
flag = true;
break ro1;
}
break;
case 2: // 上邊
if ((y - 1) >= 0 && maze.get(x + (y - 1) * width).visted == false) {
maze.get(x + y * width).setUp();
maze.get(x + (y - 1) * width).setDown();
team.add(maze.get(x + (y - 1) * width));
top++;
flag = true;
break ro1;
}
break;
case 3: // 下邊
if ((y + 1) < height && maze.get(x + (y + 1) * width).visted == false) {
maze.get(x + y * width).setDown();
maze.get(x + (y + 1) * width).setUp();
team.add(maze.get(x + (y + 1) * width));
top++;
flag = true;
break ro1;
}
break;
}
times += 1;
}
if (!flag) {
team.remove(top);
top -= 1;
}
}
return maze;
}
} 當(dāng)前名稱：詳解java圖的深度優(yōu)先遍歷如何實(shí)現(xiàn)隨機(jī)生成迷宮-創(chuàng)新互聯(lián)
鏈接分享：http://www.dlmjj.cn/article/jissp.html
