Maze generation

迷宮生成演算法是一種用於創建迷宮的演算法，其目標是生成一個具有一定難度和趣味性的迷宮。常見的迷宮生成演算法包括深度優先搜索演算法、隨機追踪演算法、分割演算法和Eller's演算法等。

深度優先搜索演算法是一種簡單而有效的迷宮生成演算法。它從一個起始位置開始，在迷宮中隨機選擇一個未訪問的相鄰位置，並將其標記為通過，然後遞歸地探索該位置，直到無法繼續前進為止。然後，回溯回到之前的位置，並選擇另一個未訪問的相鄰位置，重複上述過程，直到所有的位置都被訪問。

以下我們但簡介深度優先搜索法，又叫backtracking。

1. 準備好格


x
1
# A demo of backtracking maze generator
2

3
cols = rows = 20
4
spots = []
5

6
def setup():
7
    global spots
8
    size(630, 630)
9
    rectMode(CENTER)
10

11
    for i in range(cols):
12
        temp = []
13
        for j in range(rows):
14
            temp.append(Spot(i, j))
15
        spots.append(temp)
16

17
def draw():
18
    for i in range(cols):
19
        for j in range(rows):
20
            spots[i][j].show()
21

22
class Spot(object):
23

24
    def __init__(self, _i, _j):
25
        self.i = _i
26
        self.j = _j
27
        self.w = width / (cols + 1 )
28
        self.h = height / (rows +1 )
29
        self.x = (self.i+1) * self.w + self.w / 2
30
        self.y = (self.j+1) * self.h + self.h / 2
31
        self.wall = False
32

33
    def show(self):
34
        stroke('#555555')
35
        if self.wall:
36
            fill('#999999')
37
        else:
38
            fill(255)
39
        rect(self.x, self.y, self.w, self.h)

跟以往一樣，我們首先準備好格的class。今次比較特別的是，我們會準備n+1格，20x20的話就會是21x21格，因為要為迷宮準備好四面牆。

2. 加入cell class


xxxxxxxxxx
85
1
# A demo of backtracking maze generator
2

3
cols = rows = 20
4
spots = []
5
cells = []
6

7
def setup():
8
    global spots, cells
9
    size(630, 630)
10
    rectMode(CENTER)
11

12
    # create new spots
13
    for i in range(cols):
14
        temp = []
15
        for j in range(rows):
16
            temp.append(Spot(i, j))
17
        spots.append(temp)
18

19
    # create new cells
20
    for i in range(cols/2):
21
        temp = []
22
        for j in range(rows/2):
23
            temp.append(Cell(i, j))
24
        cells.append(temp)
25
        
26
    # add spots to each cell and add neighbors to each cell
27
    for i in range(cols/2):
28
        for j in range(rows/2):
29
            cells[i][j].addSpots(spots)
30
            cells[i][j].addNeighbors(cells)
31
            
32

33
def draw():
34
    for i in range(cols):
35
        for j in range(rows):
36
            spots[i][j].show()
37

38
class Spot(object):
39

40
    def __init__(self, _i, _j):
41
        self.i = _i
42
        self.j = _j
43
        self.w = width / (cols + 1 )
44
        self.h = height / (rows +1 )
45
        self.x = (self.i+1) * self.w + self.w / 2
46
        self.y = (self.j+1) * self.h + self.h / 2
47
        self.wall = False
48

49
    def show(self):
50
        stroke('#555555')
51
        if self.wall:
52
            fill('#999999')
53
        else:
54
            fill(255)
55
        rect(self.x, self.y, self.w, self.h)
56

57
class Cell(object):
58
    # every cell has 4 spots
59
    def __init__(self, _i, _j):
60
        self.i = _i
61
        self.j = _j
62
        self.cells = [None, None, None, None]
63
        self.neighbors = []
64
        self.visited = False
65

66
    def addSpots(self, _spots):
67
        #every cell has 4 spots, the bottom right is always wall
68
        i = self.i
69
        j = self.j
70
        self.cells[0] = _spots[i*2][j*2] # top left
71
        self.cells[1] = _spots[i*2+1][j*2] # top right
72
        self.cells[2] = _spots[i*2+1][j*2+1] # bottom right
73
        self.cells[3] = _spots[i*2][j*2+1] # bottom left
74
        self.cells[2].wall = True
75

76
    def addNeighbors(self, _cells):
77
        i = self.i
78
        j = self.j
79
        self.neighbors.append(_cells[i-1][j]) if i >0 else None
80
        self.neighbors.append(_cells[i][j+1]) if j < rows/2-1 else None
81
        self.neighbors.append(_cells[i+1][j]) if i < cols/2-1 else None
82
        self.neighbors.append(_cells[i][j-1]) if j >0 else None
83

84
    def isVisited(self):
85
        return self.visited


xxxxxxxxxx
18
1
class Cell(object):
2
    # every cell has 4 spots
3
    def __init__(self, _i, _j):
4
        self.i = _i
5
        self.j = _j
6
        self.cells = [None, None, None, None]
7
        self.neighbors = []
8
        self.visited = False
9
        
10
     def addSpots(self, _spots):
11
        #every cell has 4 spots, the bottom right is always wall
12
        i = self.i
13
        j = self.j
14
        self.cells[0] = _spots[i*2][j*2] # top left
15
        self.cells[1] = _spots[i*2+1][j*2] # top right
16
        self.cells[2] = _spots[i*2+1][j*2+1] # bottom right
17
        self.cells[3] = _spots[i*2][j*2+1] # bottom left
18
        self.cells[2].wall = True

新增一個cell class，這個class為迷宮的單元格。每個單元格包含4個spot，表示單元和的四個角落，其中右下角的Spot被標記為牆。


xxxxxxxxxx
10
1
  def addNeighbors(self, _cells):
2
        i = self.i
3
        j = self.j
4
        self.neighbors.append(_cells[i-1][j]) if i >0 else None
5
        self.neighbors.append(_cells[i][j+1]) if j < rows/2-1 else None
6
        self.neighbors.append(_cells[i+1][j]) if i < cols/2-1 else None
7
        self.neighbors.append(_cells[i][j-1]) if j >0 else None
8

9
    def isVisited(self):
10
        return self.visited

此外，每個單元格還包含了一個neighbors列表，表示與該單元格相鄰的單元格。在program2中，程式會將每個Spot添加到相應的單元格中，並且將每個單元格的相鄰單元格添加到neighbors列表中。這種方法可以減少程式生成迷宮時的計算量，提高程式的性能。


xxxxxxxxxx
21
1
cols = rows = 20
2
spots = []
3
cells = []
4

5
def setup():
6
    global spots, cells
7
    size(630, 630)
8
    #(same as before)
9

10
    # create new cells
11
    for i in range(cols/2):
12
        temp = []
13
        for j in range(rows/2):
14
            temp.append(Cell(i, j))
15
        cells.append(temp)
16
        
17
    # add spots to each cell and add neighbors to each cell
18
    for i in range(cols/2):
19
        for j in range(rows/2):
20
            cells[i][j].addSpots(spots)
21
            cells[i][j].addNeighbors(cells)

接著返回主程式，在setup()中，新增cols/2和row/2個cell(因為每4個spot為一個cell，所以只要一半就可以了)，接著跟之前一樣幫這此cell加係鄰居。

3. 加入左邊界和右邊界


xxxxxxxxxx
104
1
# A demo of backtracking maze generator
2

3
cols = rows = 20
4
spots = []
5
cells = []
6
wallSpots = []
7

8

9
def setup():
10
    global spots, cells, wallSpots
11
    size(630, 630)
12
    rectMode(CENTER)
13

14
    # create the left and top wall
15
    for i in range(-1, cols):
16
        wallSpots.append(Spot(i, -1)) 
17
    for j in range(-1, rows):
18
        wallSpots.append(Spot(-1, j)) 
19

20
    # create new spots
21
    for i in range(cols):
22
        temp = []
23
        for j in range(rows):
24
            temp.append(Spot(i, j))
25
        spots.append(temp)
26

27
    # create new cells
28
    for i in range(cols/2):
29
        temp = []
30
        for j in range(rows/2):
31
            temp.append(Cell(i, j))
32
        cells.append(temp)
33

34
    # add spots to each cell and add neighbors to each cell
35
    for i in range(cols/2):
36
        for j in range(rows/2):
37
            cells[i][j].addSpots(spots)
38
            cells[i][j].addNeighbors(cells)
39

40

41
def draw():
42
    # display the wall
43
    for spot in wallSpots:
44
        spot.wall = True
45
        spot.show()
46

47
    # display the cells
48
    for i in range(cols):
49
        for j in range(rows):
50
            spots[i][j].show()
51

52

53
class Spot(object):
54

55
    def __init__(self, _i, _j):
56
        self.i = _i
57
        self.j = _j
58
        self.w = width / (cols + 1)
59
        self.h = height / (rows + 1)
60
        self.x = (self.i+1) * self.w + self.w / 2
61
        self.y = (self.j+1) * self.h + self.h / 2
62
        self.wall = False
63

64
    def show(self):
65
        stroke('#555555')
66
        if self.wall:
67
            fill('#999999')
68
        else:
69
            fill(255)
70
        rect(self.x, self.y, self.w, self.h)
71

72

73
class Cell(object):
74
    # every cell has 4 spots
75
    def __init__(self, _i, _j):
76
        self.i = _i
77
        self.j = _j
78
        self.cells = [None, None, None, None]
79
        self.neighbors = []
80
        self.visited = False
81

82
    def addSpots(self, _spots):
83
        # every cell has 4 spots, the bottom right is always wall
84
        i = self.i
85
        j = self.j
86
        self.cells[0] = _spots[i*2][j*2]  # top left
87
        self.cells[1] = _spots[i*2+1][j*2]  # top right
88
        self.cells[2] = _spots[i*2+1][j*2+1]  # bottom right
89
        self.cells[3] = _spots[i*2][j*2+1]  # bottom left
90
        
91
        self.cells[1].wall = True
92
        self.cells[2].wall = True
93
        self.cells[3].wall = True
94

95
    def addNeighbors(self, _cells):
96
        i = self.i
97
        j = self.j
98
        self.neighbors.append(_cells[i-1][j]) if i > 0 else None
99
        self.neighbors.append(_cells[i][j+1]) if j < rows/2-1 else None
100
        self.neighbors.append(_cells[i+1][j]) if i < cols/2-1 else None
101
        self.neighbors.append(_cells[i][j-1]) if j > 0 else None
102

103
    def isVisited(self):
104
        return self.visited


xxxxxxxxxx
24
1
# A demo of backtracking maze generator
2

3
#(same as before)
4
wallSpots = []
5

6

7
def setup():
8
    global spots, cells, wallSpots
9
    size(630, 630)
10
    rectMode(CENTER)
11

12
    # create the left and top wall
13
    for i in range(-1, cols):
14
        wallSpots.append(Spot(i, -1)) 
15
    for j in range(-1, rows):
16
        wallSpots.append(Spot(-1, j)) 
17
    
18
    #(same as before)
19

20
def draw():
21
    # display the wall
22
    for spot in wallSpots:
23
        spot.wall = True
24
        spot.show()

加入一個wallSpot=[]，將左邊界和上邊界都填滿，這是迷宮的四面牆。


xxxxxxxxxx
12
1
    def addSpots(self, _spots):
2
        # every cell has 4 spots, the bottom right is always wall
3
        i = self.i
4
        j = self.j
5
        self.cells[0] = _spots[i*2][j*2]  # top left
6
        self.cells[1] = _spots[i*2+1][j*2]  # top right
7
        self.cells[2] = _spots[i*2+1][j*2+1]  # bottom right
8
        self.cells[3] = _spots[i*2][j*2+1]  # bottom left
9
        
10
        self.cells[1].wall = True
11
        self.cells[2].wall = True
12
        self.cells[3].wall = True

此外，在cell class中，在加係spot的同時，除了右下角的Spot被標記為牆以外，右上角和左下角的Spot也被標記為牆。因backtracking演算法是將走過的地方的牆拆除，而不是建牆的。

4. Backtracking


xxxxxxxxxx
161
1
# A demo of backtracking maze generator
2

3
from random import *
4

5
cols = rows = 20
6
spots = []
7
cells = []
8
wallSpots = []
9
current = None
10
stack = []
11

12

13
def setup():
14
    global spots, cells, wallSpots, current
15
    size(630, 630)
16
    rectMode(CENTER)
17
    frameRate(10)
18

19
    # create the left and top wall
20
    for i in range(-1, cols):
21
        wallSpots.append(Spot(i, -1)) 
22
    for j in range(-1, rows):
23
        wallSpots.append(Spot(-1, j)) 
24

25
    # create new spots
26
    for i in range(cols):
27
        temp = []
28
        for j in range(rows):
29
            temp.append(Spot(i, j))
30
        spots.append(temp)
31

32
    # create new cells
33
    for i in range(cols/2):
34
        temp = []
35
        for j in range(rows/2):
36
            temp.append(Cell(i, j))
37
        cells.append(temp)
38

39
    # add spots to each cell and add neighbors to each cell
40
    for i in range(cols/2):
41
        for j in range(rows/2):
42
            cells[i][j].addSpots(spots)
43
            cells[i][j].addNeighbors(cells)
44

45
    # start from the top left cell
46
    current = cells[0][0]
47
    current.visited = True
48

49

50
def draw():
51
    global current, stack
52

53
    # display the wall
54
    for spot in wallSpots:
55
        spot.wall = True
56
        spot.show()
57
    
58
    # display the cells
59
    for i in range(cols):
60
        for j in range(rows):
61
            spots[i][j].show()
62

63
     # display the current cell
64
    current.highLight()
65
   
66
    # generate the maze
67
    unvisitedNeighbors = current.checkNeighbors()
68
    if len(unvisitedNeighbors) > 0:
69
            next = choice(unvisitedNeighbors)
70
            stack.append(current)
71
            removeWall(current, next)
72
            next.visited = True
73
            current = next
74
    elif len(stack) > 0:
75
        current = stack.pop()
76
        
77
   
78

79
def removeWall(a, b):
80
    x = a.i - b.i
81
    y = a.j - b.j
82

83
    if x == 1: # a is on the right of b
84
        b.cells[1].wall = False
85
    if x == -1: # a is on the left of b
86
        a.cells[1].wall = False
87
    if y == 1: # a is below b
88
        b.cells[3].wall = False
89
    if y == -1: # a is above b
90
        a.cells[3].wall = False
91

92

93

94
class Spot(object):
95

96
    def __init__(self, _i, _j):
97
        self.i = _i
98
        self.j = _j
99
        self.w = width / (cols + 1)
100
        self.h = height / (rows + 1)
101
        self.x = (self.i+1) * self.w + self.w / 2
102
        self.y = (self.j+1) * self.h + self.h / 2
103
        self.wall = False
104

105
    def show(self):
106
        stroke('#555555')
107
        if self.wall:
108
            fill('#999999')
109
        else:
110
            fill(255)
111
        rect(self.x, self.y, self.w, self.h)
112

113
    def highLight(self):
114
        stroke('#555555')
115
        fill('#FF0000')
116
        rect(self.x, self.y, self.w, self.h)
117

118

119
class Cell(object):
120
    # every cell has 4 spots
121
    def __init__(self, _i, _j):
122
        self.i = _i
123
        self.j = _j
124
        self.cells = [None, None, None, None]
125
        self.neighbors = []
126
        self.visited = False
127

128
    def addSpots(self, _spots):
129
        # every cell has 4 spots, the bottom right is always wall
130
        i = self.i
131
        j = self.j
132
        self.cells[0] = _spots[i*2][j*2]  # top left
133
        self.cells[1] = _spots[i*2+1][j*2]  # top right
134
        self.cells[2] = _spots[i*2+1][j*2+1]  # bottom right
135
        self.cells[3] = _spots[i*2][j*2+1]  # bottom left
136
        
137
        self.cells[1].wall = True
138
        self.cells[2].wall = True
139
        self.cells[3].wall = True
140

141
    def addNeighbors(self, _cells):
142
        i = self.i
143
        j = self.j
144
        self.neighbors.append(_cells[i-1][j]) if i > 0 else None
145
        self.neighbors.append(_cells[i][j+1]) if j < rows/2-1 else None
146
        self.neighbors.append(_cells[i+1][j]) if i < cols/2-1 else None
147
        self.neighbors.append(_cells[i][j-1]) if j > 0 else None
148

149
    def isVisited(self):
150
        return self.visited
151

152
    def checkNeighbors(self):
153
        unvisitedNeighbors = []
154
        for neighbor in self.neighbors:
155
            if not neighbor.isVisited():
156
                unvisitedNeighbors.append(neighbor)
157

158
        return unvisitedNeighbors
159

160
    def highLight(self):
161
        self.cells[0].highLight()


xxxxxxxxxx
10
1
# A demo of backtracking maze generator
2

3
from random import *
4

5
cols = rows = 20
6
spots = []
7
cells = []
8
wallSpots = []
9
current = None
10
stack = []

在程式的最開始，加入current作為backtracking演算法的現存位置，另外加入stack作為演算法的堆疊，用以紀錄演算法到過的地方。


xxxxxxxxxx
5
1
def setup():
2
    #(same as before)
3
    # start from the top left cell
4
    current = cells[0][0]
5
    current.visited = True

在setup()的最低下加入current的位置，當然你也可以將current的初始位置隨機擺放。


xxxxxxxxxx
16
1
def draw():
2
    #(same as before)
3
    
4
    # display the current cell
5
    current.highLight()
6
   
7
    # generate the maze
8
    unvisitedNeighbors = current.checkNeighbors()
9
    if len(unvisitedNeighbors) > 0:
10
            next = choice(unvisitedNeighbors)
11
            stack.append(current)
12
            removeWall(current, next)
13
            next.visited = True
14
            current = next
15
    elif len(stack) > 0:
16
        current = stack.pop()

在draw()的最底下，加入highlight()，highligt current這一格方便觀察。

之後便是核心的backtracking演算法，

找出current所有未訪問的鄰居
如果有未訪問的鄰居:
1. 隨機挑選一個
2. 將current放入stack推疊
3. 將current和next中間的牆拆去
4. 將next標示為已訪問
5. 將next變成current開始新一輪的操作
如果沒有未訪問的鄰居，即到達掘頭路
1. 就將stack推疊逐個釋放出來，直到上一個有鄰居(分岔路)的格。


xxxxxxxxxx
12
1
def removeWall(a, b):
2
    x = a.i - b.i
3
    y = a.j - b.j
4

5
    if x == 1: # a is on the right of b
6
        b.cells[1].wall = False
7
    if x == -1: # a is on the left of b
8
        a.cells[1].wall = False
9
    if y == 1: # a is below b
10
        b.cells[3].wall = False
11
    if y == -1: # a is above b
12
        a.cells[3].wall = False

在setup()和draw()外加入removeWall()函數。由於所有牆都是cell的右方和下方，所以要分清楚這個兩cell哪一個在左右、哪一個在上下。

考考你

為程式加入上一章的AStar找尋路徑的演算法，做到跟我下面的程式一樣，先生成地圖再找路徑