快捷導(dǎo)航

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

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

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

最近經(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),以此類(lèi)推,直到棧里的點(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)的核心代碼，至于表示層的代碼就不貼出來(lái)了，因?yàn)槟切┒己墁嵥椤?/p>

下面是效果圖:

迷宮的類(lèi)：

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

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

您可能感興趣的文章: