java圖的深度優(yōu)先遍歷實現(xiàn)隨機生成迷宮

更新時間：2020年05月27日 09:29:47 作者：woshizoe

這篇文章主要為大家詳細(xì)介紹了java圖的深度優(yōu)先遍歷實現(xiàn)隨機生成迷宮，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

最近經(jīng)常在機房看同學(xué)在玩一個走迷宮的游戲,比較有趣，自己也用java寫一個實現(xiàn)隨機生成迷宮的算法，其實就是一個圖的深度優(yōu)先遍歷算法.基本思想就是，迷宮中的每個點都有四面墻，然后呢。

1、從任意一點開始訪問(我的算法中固定是從(0,0)點開始),往四個方向中的隨機一個訪問(每訪問到一個可訪問的點,就去掉該點的那個方向的墻),被訪問點繼續(xù)以這種方識向下進(jìn)行訪問。

2、對每個被訪問的點都被標(biāo)識為已訪問,當(dāng)一個點對某個方向進(jìn)行訪問時我們首先會判斷被訪問點是否已被訪問,或者觸到邊界.如果該點四個方向皆已訪問或已無法訪問,就退回上一個點。上一個點繼續(xù)這個過程。

這樣一次遍歷下來，可以確定每個點都被訪問過，而且由于每次訪問的方向都是隨機，這就會形成許多不同遍歷情況，同時每兩個點之間的路徑是唯一，也就形成不同的迷宮，且是起點到終點只有唯一路徑，這是由于圖的深度遍歷算法的特點所決定的。算法的實現(xiàn)上,主要是利用棧,第一次,先把第一個點壓進(jìn)棧里,每訪問到一個點,就把該點壓進(jìn)棧里,我們再對棧頂?shù)狞c進(jìn)行四個方向的隨機訪問,訪問到新點,又把新點壓進(jìn)去,一旦這個點四個方向都無法訪問了,就讓該點退棧,再對棧頂?shù)狞c的四個方向進(jìn)行訪問,以此類推,直到棧里的點都全部退出了,我們的遍歷就成功了,這是一個遞歸的過程,這個算法自然可以用遞歸的方法來實現(xiàn),不過這里我這樣做,而是手工用一個數(shù)組作為棧來實現(xiàn),呵呵~~說了這么多,也不知道自己要表達(dá)的有沒表達(dá)出來。不過我感覺我的具體代碼設(shè)計還是寫的不好，還有很多地方缺乏完善和優(yōu)化,權(quán)當(dāng)是算法練習(xí),以下是兩個關(guān)鍵類的核心代碼，至于表示層的代碼就不貼出來了，因為那些都很瑣碎。

下面是效果圖:

迷宮的類：

//作者: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; 
 } 
}

迷宮

//作者:zhongZw 
//郵箱:zhong317@126.com 
package cn.zhongZw.model; 
import java.util.*; 
import java.lang.*; 
public class MazePoint { 
 private int left = 0; 
 private int right = 0; 
 private int up = 0; 
 private int down = 0; 
 private int x; 
 private int y; 
 public boolean visted; 
 public MazePoint(int x, int y) { 
  this.x = x; 
  this.y = y; 
 } 
 public int getLeft() { 
  return left; 
 } 
 
 public void setLeft() { 
  this.left = 1; 
 } 
 public int getRight() { 
  return right; 
 } 
 public void setRight() { 
  this.right = 1; 
 } 
 public int getUp() { 
  return up; 
 } 
 
 public void setUp() { 
  this.up = 1; 
 } 
 public int getDown() { 
  return down; 
 } 
 
 public void setDown() { 
  this.down = 1; 
 } 
 public int getX() { 
  return x; 
 } 
 public void setX(int x) { 
  this.x = x; 
 } 
 public int getY() { 
  return y; 
 } 
 public void setY(int y) { 
  this.y = y; 
 } 
 
 
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: