摘要：本人郵箱歡迎轉載轉載請注明網(wǎng)址代碼已經(jīng)全部托管有需要的同學自行下載引言迷宮對于大家都不會陌生那么迷宮是怎么生成已經(jīng)迷宮要如何找到正確的路徑呢用代碼又怎么實現(xiàn)帶著這些問題我們繼續(xù)往下看并查集朋友圈有一種算法就做并查集什么意思呢比如現(xiàn)在有零
本人郵箱:
歡迎轉載,轉載請注明網(wǎng)址 http://blog.csdn.net/tianshi_kco
github: https://github.com/kco1989/kco
代碼已經(jīng)全部托管github有需要的同學自行下載
引言
迷宮對于大家都不會陌生.那么迷宮是怎么生成,已經(jīng)迷宮要如何找到正確的路徑呢?用java代碼又怎么實現(xiàn)?帶著這些問題.我們繼續(xù)往下看.
并查集(find-union)
朋友圈
有一種算法就做并查集(find-union).什么意思呢?比如現(xiàn)在有零散的甲乙丙丁戊五個人.他們之間剛開始互相不認識.用代碼解釋就是find(person1, person2) == false,之后在某一次聚合中,甲認識了乙,乙認識了丙,丙認識了戊和丁等等,那么就可以用代碼解釋如下.
union("甲", "乙");
union("乙", "丙");
union("丙", "戊");
union("丙", "丁");
那么這個時候甲就可以通過乙認識到了丙在通過丙認識到庚和丁.
這是甲乙丙丁戊通過朋友或者朋友的朋友最終都互相認識.換另一種說法就是如果甲要認識丁,那么甲必須先通過乙認識丙,再通過丙去認識丁就行了.
迷宮
對于迷宮生成,其實更上面朋友圈有點類似.生成步驟如下
首先,先創(chuàng)建一個n*m的二維密室.每個單元格四方都是墻.
隨機選擇密室中的一個單元格.之后在隨機選擇一面要打通的墻壁.
判斷要打通的墻壁是否為邊界.是則返回步驟3,不是則繼續(xù)
判斷步驟的單元個和要打通的墻壁的對面是否聯(lián)通(用find算法)
如果兩個單元格不聯(lián)通,則把步驟2選中的墻壁打通(用union算法).否則返回步驟2.
判斷迷宮起點和終點是否已經(jīng)聯(lián)通,是則迷宮生成結束,否則返回步驟2.
對于并查集(find-union)的實現(xiàn),網(wǎng)絡上有不少實現(xiàn),這里不展開說明了.
實現(xiàn)代碼
墻壁
public enum Wall {
/**
* 墻壁
*/
BLOCK,
/**
* 通道
*/
ACCESS
}
墻壁,是一個枚舉變量,用于判斷當前的墻壁是否可以通行.
單元格
public class Box {
private Wall[] walls;
public Box(){
walls = new Wall[4];
for (int i = 0; i < walls.length; i ++){
walls[i] = Wall.BLOCK;
}
}
public void set(Position position, Wall wall){
walls[position.getIndex()] = wall;
}
public Wall get(Position position){
return walls[position.getIndex()];
}
}
一個單元格(小房間)是有四面墻組成的,剛開始四面墻都是墻壁.
方向
public enum Position {
TOP(0), RIGHT(1), DOWN(2), LEFT(3);
public int index;
Position(int index) {
this.index = index;
}
public static Position indexOf(int index){
int pos = index % Position.values().length;
switch (pos){
case 0:
return TOP;
case 1:
return RIGHT;
case 2:
return DOWN;
case 3:
default:
return LEFT;
}
}
public Position anotherSide(){
switch (this){
case TOP:
return DOWN;
case RIGHT:
return LEFT;
case DOWN:
return TOP;
case LEFT:
default:
return RIGHT;
}
}
public int getIndex() {
return index;
}
}
方向,枚舉類,用于判斷單元格的那一面墻壁需要打通.
迷宮生成類
這里我使用find-union的兩種實現(xiàn)方式實現(xiàn),
一種是用數(shù)組的方式MazeArrayBuilder
一種使用map的方式實現(xiàn)MazeMapBuilder
所以我把迷宮生成的一些共同方法和屬性抽取出現(xiàn),編寫了一個抽象類AbstractMazeBuilder.然后再在MazeArrayBuilder或MazeMapBuilder做具體的實現(xiàn).
現(xiàn)在我們來看看AbstractMazeBuilder這個類
public abstract class AbstractMazeBuilder {
/**
* 迷宮行列最大值
*/
public static final int MAX_ROW_LINE = 200;
/**
* 行
*/
protected int row;
/**
* 列
*/
protected int line;
/**
* 迷宮格子集合,每個格子有四面墻
*/
protected Box[][] boxes;
/**
* 求解迷宮中間變量
*/
protected int[][] solverPath;
/**
* 迷宮時候已經(jīng)算出最佳路徑
*/
protected boolean isSolver;
/**
* 使用貪婪算法,算出最佳路徑集合
*/
protected List bestPath;
protected Random random;
public AbstractMazeBuilder(int row, int line){
if (row < 3 || row > MAX_ROW_LINE || line < 3 || line > MAX_ROW_LINE){
throw new IllegalArgumentException("row/line 必須大于3,小于" + MAX_ROW_LINE);
}
this.row = row;
this.line = line;
isSolver = false;
boxes = new Box[row][line];
solverPath = new int[row][line];
bestPath = new ArrayList();
random = new Random();
for (int i = 0; i < row; i ++){
for (int j = 0; j < line; j ++){
boxes[i][j] = new Box();
solverPath[i][j] = Integer.MAX_VALUE;
}
}
}
/**
* 查詢與point點聯(lián)通的最大格子的值
* @param point point
* @return 查詢與point點聯(lián)通的最大格子的值
*/
protected abstract int find(MazePoint point);
/**
* 聯(lián)通point1和point2點
* @param point1 point1
* @param point2 point2
*/
protected abstract void union(MazePoint point1, MazePoint point2);
/**
* 判斷時候已經(jīng)生成迷宮路徑
* @return 判斷時候已經(jīng)生成迷宮路徑
*/
protected abstract boolean hasPath();
/**
* 生成迷宮
*/
public void makeMaze(){
while (hasPath()){
// 生成 當前點, 當前點聯(lián)通的方向, 當前點聯(lián)通的方向對應的點
ThreeTuple tuple = findNextPoint();
if (tuple == null){
continue;
}
union(tuple.one, tuple.three);
breakWall(tuple.one, tuple.two);
breakWall(tuple.three, tuple.two.anotherSide());
}
breakWall(new MazePoint(0,0), Position.LEFT);
breakWall(new MazePoint(row - 1, line - 1), Position.RIGHT);
}
/**
* 生成 當前點, 當前點聯(lián)通的方向, 當前點聯(lián)通的方向對應的點
* @return
* ThreeTuple.one 當前點
* ThreeTuple.two 當前點聯(lián)通的方向
* ThreeTuple.three 當前點聯(lián)通的方向對應的點
*/
private ThreeTuple findNextPoint() {
MazePoint currentPoint = new MazePoint(random.nextInt(row), random.nextInt(line));
Position position = Position.indexOf(random.nextInt(Position.values().length));
MazePoint nextPoint = findNext(currentPoint, position);
if (nextPoint == null || find(currentPoint) == find(nextPoint)){
return null;
}
return new ThreeTuple(currentPoint, position, nextPoint);
}
/**
* 打通墻
* @param point 當前點
* @param position 當前點的方向
*/
private void breakWall(MazePoint point, Position position) {
boxes[point.x][point.y].set(position, Wall.ACCESS);
}
/**
* 通過當前點以及對應當前點的方向找到下一個點
* @param currentPoint 當前點
* @param position 方向
* @return 下個點,若該點在迷宮內,這返回,否則返回null
*/
private MazePoint findNext(MazePoint currentPoint, Position position) {
MazePoint nextPoint;
switch (position){
case TOP:
nextPoint = new MazePoint(currentPoint.x - 1, currentPoint.y);
break;
case RIGHT:
nextPoint = new MazePoint(currentPoint.x, currentPoint.y + 1);
break;
case DOWN:
nextPoint = new MazePoint(currentPoint.x + 1, currentPoint.y);
break;
case LEFT:
default:
nextPoint = new MazePoint(currentPoint.x, currentPoint.y - 1);
break;
}
if (nextPoint.x < 0 || nextPoint.x >= row || nextPoint.y < 0 || nextPoint.y >= line){
return null;
}
return nextPoint;
}
public Box getBoxes(int x, int y) {
return boxes[x][y];
}
public int getRow() {
return row;
}
public int getLine() {
return line;
}
/**
* 求解迷宮路徑
* @return 迷宮路徑
*/
public List solvePath(){
// 1 迷宮時候已經(jīng)求解完成,是的話,則直接返回,不必再次計算
if (isSolver){
return bestPath;
}
// 2 否則計算迷宮最佳路徑
bestPath = new ArrayList();
solverPath(new MazePoint(0, 0), 0);
addPath(new MazePoint(row - 1, line - 1));
Collections.reverse(bestPath);
isSolver = true;
return bestPath;
}
/**
* 從終點逆推,添加最佳路徑
* @param point 當前點
*/
private void addPath(MazePoint point) {
bestPath.add(point);
// 遍歷當前點的每個方向,如果該方向能聯(lián)通,這步數(shù)跟當前點的步數(shù)相差1步,這添加改點,遞歸計算下去
for (Position position :Position.values()){
MazePoint next = findNext(point, position);
if (next == null || getBoxes(point.x, point.y).get(position) == Wall.BLOCK){
continue;
}
if (solverPath[point.x][point.y] - 1 == solverPath[next.x][next.y]){
addPath(next);
return;
}
}
}
/**
* 遞歸求解迷宮最佳路徑
* @param point 當前點
* @param count 從開始走到當前點所需要的步數(shù)
*/
private void solverPath(MazePoint point, int count) {
// 判斷當前點的步數(shù)時候小于現(xiàn)在走到這個點的步數(shù),
// 如果當前點的步數(shù)比較小,則直接返回
if (solverPath[point.x][point.y] <= count){
return;
}
// 否則表示當前點,有更短的路徑
solverPath[point.x][point.y] = count;
// 再遍歷當前點的每個方向
for (Position position : Position.values()){
MazePoint next = findNext(point, position);
// 如果下一個點不在迷宮內,或當前點對應的方向是一面墻壁,則跳過繼續(xù)編寫下一個方向
if (next == null || getBoxes(point.x, point.y).get(position) == Wall.BLOCK){
continue;
}
// 否則,步數(shù)加1, 遞歸計算
solverPath(next, count + 1);
}
}
public static class MazePoint{
public final int x;
public final int y;
public MazePoint(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "MazePoint{" +
"x=" + x +
", y=" + y +
"}";
}
}
}
代碼上有注釋,理解起來還是比較容易.MazeArrayBuilder和MazeMapBuilder的實現(xiàn)就參考github了.
AbstractMazeBuilder 中還包括了迷宮的求解.
迷宮的求解
迷宮的求解,一般我會使用以下兩種方法
右手規(guī)則,從起點出發(fā),遇到墻壁,則向右手邊轉,按照這個規(guī)則.一般是可以找到出口的.不過如果迷宮有閉環(huán),則無法求解,而且解出來的路徑也不是最短路徑.
迷宮最短路徑算法.
從起點出發(fā),計數(shù)count=0
遍歷該點的任意方向,如果是墻壁,則忽略,不然count++,進入下一個聯(lián)通的格子
判斷當前格子的的count(默認值一般是比較大的數(shù))是否比傳入的參數(shù)大,是說明該格子是一條捷徑,將當前各自的count=入?yún)?繼續(xù)第2步;否則,說明該點已經(jīng)被探索過且不是一條捷徑,忽略
如果反復,暴力遍歷所有單元格,即可以求出最短路徑
遍歷完之后,從出口開始找,此時出口的數(shù)字,表示從入口走到出口需要的最小步數(shù).依次減1,找到下一個格子,直到找打入口.則最短路徑就生成了.
附加運行結果
打賞
如果覺得我的文章寫的還過得去的話,有錢就捧個錢場,沒錢給我捧個人場(幫我點贊或推薦一下)
