快捷導航

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

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

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

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

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

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

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

您可能感興趣的文章: