Eller's Algorithm 迷宮生成算法

發表於 分類於 閱讀次數： 文章字數： 802 所需閱讀時間 ≈ 4 分鐘
maze

Eller’s Algorithm 算法介紹

Eller’s Algorithm 是一種神奇動態迷宮生成算法，可以在線性時間內逐行生成迷宮，用我自己的理解來說，算法的精神就是:

每個格子一開始都是被分隔開的「區域」，隨機打通格子間的牆壁使區域間可以相通。

步驟拆解

Eller’s Algorithm 大致上可以拆解為以下幾個步驟:

  1. 初始化第一行
    每個格子都有一個唯一的區域編號，彼此之間都是分隔的。
    step1
  2. 橫向連接
    隨機打通相鄰格子之間的橫向牆壁，將它們合併到同一個區域中。
    step2
  3. 垂直連接
    每個區域至少有一個格子向下連接，確保迷宮在下一行是連通的。
    step3
  4. 新增區域
    分配新的區域編號給尚未連接的格子，由於算法只關注最新的一行，所以前面的幾行都不用管了。
    step4
  5. 迭代生成
    重複 2~4 的步驟
    step5_1
    step5_2
    step5_3
  6. 處理最後一行
    確保最後一行所有格子都連接 (打通所有區域)，以形成一個完整的迷宮。
    ps. 連通的是區域，不代表最後一列沒有橫向的牆壁
    step6

Python 實現

雖然說算法邏輯是打通區域，但區域是個抽象的概念，實際上程式寫起來會比較像在各個格子間「建牆」。

生成迷宮

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import random
from collections import Counter

def replace(row, old_v, new_v):
    for i, v in enumerate(row):
        if v == old_v:
            row[i] = new_v

def ellers_algorithm(height, width, prob=0.5):
    maze = [[0]*width for _ in range(height)]
    areas = [i for i in range(width)]
    next_area = width

    for i in range(height):
        # Horizontal connections
        for j in range(width-1):
            # no wall (connect areas)
            if areas[j] != areas[j+1] and random.random() > prob:
                replace(areas, areas[j+1], areas[j])
            # build wall
            else:
                maze[i][j] |= 1
        
        # Last row (connect all areas)
        if i == height-1:
            for j in range(width-1):
                if areas[j] != areas[j+1]:
                    replace(areas, areas[j+1], areas[j])
                    maze[i][j] &= ~1
            break

        # Vertical connections
        area_count = Counter(areas)
        for j, cell in enumerate(areas):
            # build wall
            if area_count[cell] > 1 and random.random() < prob:
                area_count[cell] -= 1
                areas[j] = next_area
                next_area += 1
                maze[i][j] |= 2

    return maze

繪製迷宮

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import matplotlib.pyplot as plt
import matplotlib.lines as lines

def line(x1, x2, y1, y2, color='black'):
    return lines.Line2D([x1, x2], [y1, y2], color=color, linewidth=2)

def plot_maze(maze):
    height, width = len(maze), len(maze[0])
    fig, ax = plt.subplots()

    # boarder
    ax.add_line(line(0, 0, 0, height))
    ax.add_line(line(0, width, 0, 0))
    ax.add_line(line(width, width, 0, height))
    ax.add_line(line(0, width, height, height))

    for i in range(height):
        for j in range(width):
            if maze[i][j] & 1:  # Wall to the right
                ax.add_line(line(j+1, j+1, height-i-1, height-i))
            if maze[i][j] & 2:  # Wall below
                ax.add_line(line(j, j+1, height-i-1, height-i-1))

    ax.set_xlim(0, width)
    ax.set_ylim(0, height)
    ax.set_aspect('equal')
    ax.axis('off')
    
    return fig, ax

執行結果

1
2
3
4
5
6
7
height = 20
width = 30
    
maze = ellers_algorithm(height, width)
fig, ax = plot_maze(maze)
plt.tight_layout()
plt.show()

成果如下:
maze

預告

下一篇文章用 A* 算法走迷宮 ~