穴掘り法で迷路生成

pythonで迷路生成を実装したのでメモしておきます．
今回は穴掘り方を使用しました．

前置き
コード
できた迷路

前置き

穴掘り法については[迷路穴掘り法]で検索していただくとして．

非常に眠いのであまり丁寧に説明できませんが，基本的に以下の点を工夫しています．
・外周を通路に設定して探索点の内外判定を省略
・[偶数，偶数]となる点群のみを探索候補としてもっておくことにより高速化

コード

import random

# 幅と奥行きの設定 (どちらも奇数である必要がある)
height = 25
width = 35
maze = [[1 if 0<i<width-1 else 0 for i in range(width)] if 0<j<height-1 else [0 for i in range(width)] for j in range(height)] #通路:0 壁:1


def mazeprint(maze):  #数字で表現された面を●や◯に変換する関数
    c_dict={0:"□",  1:"■"}
    c_maze = [[c_dict[maze[j][i]] for i in range(width)] for j in range(height)]
    for i in range(height):
            print("".join(c_maze[i]) )
    print("")

#開始点を定める
wl = [[2*i+2,2*j+2] for i in range(int((width-1)/2)-1) for j in range(int((height-1)/2)-1)] #未探索リスト
stt = wl.pop(random.randint(0, len(wl)-1)) #ランダムに開始点を定める
ps = [stt]  #探索済みリスト

print("start Point: ", stt)
maze[stt[1]][stt[0]] = 0  #壁(1)を通路(0)に書き換える
mazeprint(maze)  #迷路出力



#探索する
dr =[[-1,0], [1,0], [0,-1], [0,1]] #探索方向のリスト

while(len(wl)>0): 
    random.shuffle(dr)  #探索方向順をランダムに
    for i in range(4):  #このfor文内ではある座標sttの周辺４方向に対する探索のみ行う
        nxtx = stt[0]+dr[i][0]*2 #探索候補のx座標
        nxty = stt[1]+dr[i][1]*2 #探索候補のy座標
        if maze[nxty][nxtx]==1 :  #2マス先が通路でないとき
            wl.remove([nxtx,nxty])  #未探索リストから削除
            ps.append([nxtx,nxty])  #探索済みリストに追加
            maze[nxty][nxtx] = 0 #2マス先を通路に変更
            maze[nxty-dr[i][1]][nxtx-dr[i][0]] = 0 #1マス先を通路に変更
            break
            if i==3:
                ps.remove([nxtx,nxty])
        stt = ps[random.randint(0, len(ps)-1)]

#完成した迷路を出力
mazeprint(maze)