算法學(xué)習自 作者eastecho 在IndieNova上發(fā)表的文章 簡單的使用回溯法生成 Tile Based 迷宮 ，
我只是簡單做了一下Unity的實現(xiàn)抢野。
基礎(chǔ)算法的簡單說明
簡單說明一下算法步驟：
- 先生成基礎(chǔ)地圖。
- 選擇基礎(chǔ)地圖的一個點（一個格子）囊嘉，將它標記為已訪問過的亚皂，并將這個點加入到堆棧中儲存起來。
- 取出堆棧頂?shù)倪@個點作為基準點陡厘，檢查附近有沒有未訪問過的點。
- 如果附近有未訪問過的點特占，則隨機選取其中的一個點糙置，將它標記為已訪問過的，并加入到堆棧中儲存是目。
- 重復(fù)第二步谤饭，直到出現(xiàn)一個點，基于這個點在附近找不到未訪問過的點了胖笛。
- 將這個堆棧頂部的點移除网持，基于新的頂部的點重復(fù)第二步。
- 當堆棧為空時长踊，說明迷宮已經(jīng)生成完畢功舀。
經(jīng)過以上步驟，我們就可以得到一個完美迷宮身弊，從迷宮中的任何一點都可以到達迷宮中的另外一點辟汰。
這個算法就像是忒修斯走米諾斯迷宮，進入迷宮時將毛線頭系在迷宮入口阱佛，然后隨意走向能走的地方帖汞，直到走到了死胡同，就順著毛線返回到上一個還能走的地方凑术。
而我們的算法則像是在空地順著路線擺磚塊翩蘸，直到擺不了磚塊了便返回上一個可以擺磚塊的地方繼續(xù)擺磚塊。
適合Tile Based地圖的改進算法
我們先假設(shè)我們希望生成的迷宮中有兩種大小相同的部件淮逊，墻 和 地面催首。
墻是不能移動到的部分,地面是玩家可以移動的部分。
假如未被訪問的點是墻泄鹏，已被訪問的點是地面郎任，我們的算法也可以看作是一個人在布滿墻的空間里挖路。
這個時候我們發(fā)現(xiàn)备籽，如果使用上一個算法舶治，找到身邊可以挖開的墻壁然后挖開，最后所有的墻壁都會被我們鑿開。
所以我們需要為我們的墻壁預(yù)留空間霉猛。
我們稍加改良尺锚。
簡單說明一下改良后的算法步驟：
- 先生成基礎(chǔ)地圖。
- 選擇基礎(chǔ)地圖的一個點（一個格子）韩脏，將它標記為已訪問過的缩麸，并將這個點加入到堆棧中儲存起來铸磅。
- 取出堆棧頂?shù)倪@個點作為基準點赡矢，檢查有沒有與這個點相隔一個格子距離，同時又未訪問過的點阅仔。
- 如果有這樣的點吹散，則隨機選取其中的一個點，將它標記為已訪問過的八酒，并加入到堆棧中儲存空民。
- 將這兩個點之間的也標記為已訪問過的點，但不將這個點放入堆棧羞迷。所以需注意界轩，這個時候堆棧頂部的點是剛才檢查到的，距離一個格子的點衔瓮，而不是附近的這個點浊猾。將中間這個點設(shè)置為已訪問的作用是連通當前點和下一個目標點。
- 重復(fù)第二步热鞍，直到出現(xiàn)一個點葫慎，基于這個點在附近距離一個格子的范圍找不到未訪問過的點了。
- 將這個堆棧頂部的點移除薇宠，基于新的頂部的點重復(fù)第二步偷办。
- 當堆棧為空時，說明迷宮已經(jīng)生成完畢澄港。
不同的地方在于查找下一個目標點的時候椒涯，跳過了一個格子。最后只要將已訪問過的點設(shè)置為路面回梧，將未訪問過的點設(shè)置為墻面就可以完成迷宮的生成了废岂。
代碼實現(xiàn)
首先我們先說明一下變量
c#
//需要生成地圖的行數(shù)
public int row = 35;
//需要生成地圖的列數(shù)
public int column = 30;
//生成地圖的基準點
public Vector2 originPoint;
//格子之間的偏移
public float offset;
//地面格子預(yù)設(shè)
public GameObject floorPrefab;
//墻壁格子預(yù)設(shè)
public GameObject wallPrefab;
//迷宮的邏輯地圖
private int[,] _maze;
//根據(jù)邏輯地圖生成的實際地圖
private GameObject[,] _map;
//儲存目標點的容器
private List<Vector2> _moves = new List<Vector2>();
首先我們初始化邏輯地圖和實際地圖兩個地圖，然后以（0漂辐，0）為起始點開始找尋下一個目標點泪喊。即，我們從（0髓涯，0）開始挖墻袒啼。
c#
void Start()
{
//初始化地形
InitTerrain();
}
void InitTerrain()
{
//初始化邏輯地圖
_maze = new int[row, column];
//初始化實際地圖
_map = new GameObject[row, column];
//以（0，0）為基準點開始查找目標點生成迷宮
QueryRoad(0, 0);
}
接下來我們來看看關(guān)鍵的挖墻部分
c#
void QueryRoad(int r, int c)
{
string dirs = "";
//檢查北面的格子是否被訪問
if ((r - 2 >= 0) && (_maze[r - 2, c] == 0)) dirs += "N";
//檢查西面的格子是否被訪問
if ((c - 2 >= 0) && (_maze[r, c - 2] == 0)) dirs += "W";
//檢查南面的格子是否被訪問
if ((r + 2 < row) && (_maze[r + 2, c] == 0)) dirs += "S";
//檢查東面的格子是否被訪問
if ((c + 2 < column) && (_maze[r, c + 2] == 0)) dirs += "E";
//如果方位為空，則說明沒有未訪問的格子了
if (dirs == "")
{
//刪除頂上的這個格子
_moves.RemoveAt(_moves.Count - 1);
if (_moves.Count == 0)
{
//如果容器空了蚓再，說明迷宮生成完畢滑肉，可以開始繪制迷宮了
DrawTerrain();
}
else
{
//否則基于新的點，繼續(xù)查找下一個目標點
QueryRoad((int)_moves[_moves.Count - 1].x, (int)_moves[_moves.Count - 1].y);
}
}
else
{
//隨機一個可以被訪問的點
int ran = Random.Range(0, dirs.Length);
char dir = dirs[ran];
//連通目標點和當前點之間的這個點
switch (dir)
{
case 'E':
//將中間這個點設(shè)置為已訪問的
_maze[r, c + 1] = 1;
c = c + 2;
break;
case 'S':
//將中間這個點設(shè)置為已訪問的
_maze[r + 1, c] = 1;
r = r + 2;
break;
case 'W':
//將中間這個點設(shè)置為已訪問的
_maze[r, c - 1] = 1;
c = c - 2;
break;
case 'N':
//將中間這個點設(shè)置為已訪問的
_maze[r - 1, c] = 1;
r = r - 2;
break;
}
//將這個新的目標點設(shè)置為已訪問的
_maze[r, c] = 1;
//將這個新的目標點加入容器
_moves.Add(new Vector2(r, c));
//基于新的點摘仅，繼續(xù)查找下一個目標點
QueryRoad(r, c);
}
}
算法原理和之前敘述的是一樣的靶庙。
最后只需要將實際地圖根據(jù)邏輯地圖繪制出來就好了。
c#
void DrawTerrain()
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
switch (_maze[i, j])
{
case 1:
if (_map[i, j] != null)
{
if (_map[i, j].tag == "Floor")
{
continue;
}else if (_map[i, j].tag == "Wall")
{
Destroy(_map[i, j]);
_map[i, j] = null;
}
}
_map[i, j] = Instantiate(floorPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
break;
case 0:
if (_map[i, j] != null)
{
if (_map[i, j].tag == "Wall")
{
continue;
}
else if (_map[i, j].tag == "Floor")
{
Destroy(_map[i, j]);
_map[i, j] = null;
}
}
_map[i, j] = Instantiate(wallPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
break;
}
}
}
}
如何讓繪制迷宮的過程可見
迷宮一下就出現(xiàn)難免有些無趣娃属，畢竟看著空無一物的地圖逐漸被道路充滿也是一種樂趣六荒。我真心覺得看著迷宮漸漸生成非常令人愉悅。所以提供一種讓迷宮的生成可見的方法矾端。
c#
//用來儲存目標點
private Vector2 _currentPoint;
這是關(guān)鍵變量掏击，將之前的遞歸改為一幀一次，相當于每一幀挖一塊墻秩铆，獲取到了新的目標點之后不會立刻找下一個砚亭，而是等到下一幀再執(zhí)行。
記得增加執(zhí)行條件殴玛，以免無限執(zhí)行查找捅膘。
我這里設(shè)置成如果這個點是（-1，-1）則不執(zhí)行查找滚粟。當我在繪制完成最后的實際地圖后會將這個點設(shè)置成（-1寻仗，-1）。
那么首先我們對初始化的部分進行一點修改坦刀。
c#
void InitTerrain()
{
_maze = new int[row, column];
_map = new GameObject[row, column];
//初始化時先將目標點設(shè)置為（0愧沟，0）
_currentPoint = new Vector2(0, 0);
}
然后我們每一幀根據(jù)當前的目標點查找下一個目標點。
c#
void Update()
{
//如果當前目標點_currentPoint是合法的話就查找下一個目標點
if (_currentPoint != new Vector2(-1, -1))
{
QueryRoad((int) _currentPoint.x, (int) _currentPoint.y);
}
}
然后我們的查找目標點也從遞歸改成僅僅查找下一個目標點鲤遥。
c#
//修改查找部分沐寺，取消遞歸。
void QueryRoad(int x, int y)
{
string dirs = "";
if ((x - 2 >= 0) && (_maze[x - 2, y] == 0)) dirs += "N";
if ((y - 2 >= 0) && (_maze[x, y - 2] == 0)) dirs += "W";
if ((x + 2 < row) && (_maze[x + 2, y] == 0)) dirs += "S";
if ((y + 2 < column) && (_maze[x, y + 2] == 0)) dirs += "E";
if (dirs == "")
{
_moves.RemoveAt(_moves.Count - 1);
if (_moves.Count == 0)
{
DrawTerrain();
//這是最后一個點了盖奈，這個點以外已經(jīng)沒有符合條件的點混坞，所以在這次繪制完畢后將不再執(zhí)行查找。
_currentPoint = new Vector2(-1, -1);
}
else
{
//這里取消遞歸钢坦，改為設(shè)置目標點究孕，下一幀再處理這個目標點
//QueryRoad((int) _moves[_moves.Count - 1].x, (int) _moves[_moves.Count - 1].y);
//因為這個目標點附近已經(jīng)沒有符合要求的點了，所以找到上一個點爹凹，并將其設(shè)置為新的目標基點厨诸。
_currentPoint = _moves[_moves.Count - 1];
}
}
else
{
int ran = Random.Range(0, dirs.Length);
char dir = dirs[ran];
switch (dir)
{
case 'E':
_maze[x, y + 1] = 1;
y = y + 2;
break;
case 'S':
_maze[x + 1, y] = 1;
x = x + 2;
break;
case 'W':
_maze[x, y - 1] = 1;
y = y - 2;
break;
case 'N':
_maze[x - 1, y] = 1;
x = x - 2;
break;
}
_maze[x, y] = 1;
_moves.Add(new Vector2(x, y));
//這里依然取消遞歸
//QueryRoad(x, y);
//這里將目標基點_currentPoint設(shè)置為新的目標點。
_currentPoint = new Vector2(x, y);
//每一次找到了新的目標點都要繪制一次實際地圖
DrawTerrain();
}
}
每一次找到了新的目標點都要繪制一次實際地圖禾酱，這樣才能把你挖通的道路顯示出來微酬。
下一步就是繪制地圖部分绘趋，這一部分沒有什么變化。
c#
void DrawTerrain()
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
switch (_maze[i, j])
{
case 1:
if (_map[i, j] != null)
{
if (_map[i, j].tag == "Floor")
{
continue;
}else if (_map[i, j].tag == "Wall")
{
Destroy(_map[i, j]);
_map[i, j] = null;
}
}
_map[i, j] = Instantiate(floorPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
break;
case 0:
if (_map[i, j] != null)
{
if (_map[i, j].tag == "Wall")
{
continue;
}
else if (_map[i, j].tag == "Floor")
{
Destroy(_map[i, j]);
_map[i, j] = null;
}
}
_map[i, j] = Instantiate(wallPrefab, originPoint + new Vector2(j * offset, i * offset), Quaternion.identity);
break;
}
}
}
}
最后
大家可以自己嘗試一下這種生成迷宮的方法颗管。
如果大家有什么問題或者指教陷遮，也歡迎來與我交流。
