代码之家 › 专栏 › 技术社区 › Rxzlion

Python-回溯迷宫生成递归函数理解

backtracking depth-first-search recursion python-3.x python

Rxzlion · 技术社区 · 7 年前

我在寻找用python创建迷宫的方法。
我在 rosettacode 。
我知道代码使用递归来构建迷宫。
我理解代码行,知道我在读什么,我想使用这些代码,但我对这些代码缺乏关键的理解。

这段代码中的递归函数究竟如何知道何时停止?

from random import shuffle, randrange

def make_maze(w = 16, h = 8):
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

    def walk(x, y):
        vis[y][x] = 1

        d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
        shuffle(d)
        for (xx, yy) in d:
            if vis[yy][xx]: continue
            if xx == x: hor[max(y, yy)][x] = "+  "
            if yy == y: ver[y][max(x, xx)] = "   "
            walk(xx, yy)

    walk(randrange(w), randrange(h))

    s = ""
    for (a, b) in zip(hor, ver):
        s += ''.join(a + ['\n'] + b + ['\n'])
    return s

if __name__ == '__main__':
    print(make_maze())

1 回复 | 直到 7 年前

Patrick Artner 7 年前

已将调试打印应用于代码:

from random import shuffle, randrange

def make_maze(w = 3, h =3):
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

    def debugPrint():
        print("-"*16)
        s = ""
        for (a, b) in zip(hor, ver):
            s += ''.join(a + ['\n'] + b + ['\n'])
        print(s )

        for r in vis:
            print(r) 


    def walk(x, y):
        debugPrint()

        vis[y][x] = 1

        d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
        shuffle(d)
        for (xx, yy) in d:
            if vis[yy][xx]: continue
            if xx == x: hor[max(y, yy)][x] = "+  "
            if yy == y: ver[y][max(x, xx)] = "   "

            walk(xx, yy)



    walk(randrange(w), randrange(h))

    s = ""
    for (a, b) in zip(hor, ver):
        s += ''.join(a + ['\n'] + b + ['\n'])
    return s

if __name__ == '__main__':
    print(make_maze())

要可视化正在发生的事情:

----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+--+--+--+


[0, 0, 0, 1]
[0, 0, 0, 1]
[0, 0, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+--+
|  |  |  |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[0, 0, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+--+
|     |  |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+--+
|        |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[1, 1, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |     |
+--+--+  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 0, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|        |
+--+--+  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 1, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|        |
+--+  +  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[1, 1, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]

最终输出:

+--+--+--+
|        |
+--+  +  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+