【Python/Tkinter】穴掘り法とA*アルゴリズムによる迷路自動生成プログラムの作成

はじめに

今回はPythonのTkinterを使ってプレイすることのできる迷路自動生成プログラムを作ってみました。
プログラムの説明というよりかは穴掘り法とA*アルゴリズムの説明になっています。
簡単で分かりやすく説明したつもりなのでよかったら見ていってください。
また、classをまだあまり使いこなせていないのでこのプログラムはclassなしの物になっています。

1. 穴掘り法とは?

穴掘り法というのは迷路を作成するためのアルゴリズムの1つで、その名の通り「壁に穴を掘っていく」ことで迷路を作成するアルゴリズムです。
穴を掘り、その穴からさらにランダムに決めた方向に穴を掘るを繰り返すことで迷路を作成します。これによりほかの迷路を作成するアルゴリズムよりも比較的簡単で複雑な迷路を作成することができます。

実際の流れ

① 奇数×奇数のすべて壁でできたマス目を作る。​
② 現在地を決定し、そこを道とする。​
③ ランダムで進む方向を決める。（上下左右）​
④ 進む方向の2マス先が道or迷路の外ではないかを確認し、違う場合は穴を掘りながら現在地を２マス先に移動する。​
⑤ 行ける場所がなくなったら一つ前の現在地に戻り③、④をもう一度行う。​
⑥ ③～⑤を行ける場所がなくなるまで繰り返す
このような流れで迷路を作っていきます。

黄色の場所が現在地です。
穴掘り法の性質上一番初めに現在地にした場所は一方向にしか伸びることがないのでゴール地点を最初の現在地としています。
プログラムの性質上リストの範囲外を呼び出そうとするとエラーが起きてしまうので、このプログラムでは迷路自体をあらかじめ道で囲っておいて範囲外を呼び出せないようにしています。

2. A*アルゴリズムとは

A*アルゴリズムはスタート地点からゴール地点の最短経路を求めるアルゴリズムの1つですです。
すべての道を探索することで確実に最短経路が求めることができるが探索するべき場所を計算によって求めることでできるだけ少ない探索回数で最短経路を効率的に求めることができる。

A*アルゴリズムを扱う上で必要な知識

スタートからの距離とゴールまでの距離について

A*アルゴリズムで実際に使うのは以下の2つです。
・スタートからの距離
・スタートからの距離とゴールまでの距離の合計

スタートからの距離というのは通ってきた道の数を数えれば簡単に求まります。
ですがゴールまでの距離というのは実際には分かっていない状態なので予想して計算しています。
具体的にはゴールから現在地までの横方向の距離と縦方向の距離を足し合わせています。
この予想したゴールまでの距離は正しい正解の道を導くために実際のゴールまでの距離よりも短くなければいけません。

親とは

マスが探索された時の現在地の座標が探索されたマスにおける親となります。
例として、黄色のマスを現在地、青色のマスを探索されたマス(次に現在地とすることができるマス)とすると、上の図では黄色のマスが青色のマスの親となります
最終的にゴールが見つかった時にゴールから親の座標を順に辿っていくことで正解の道を導くことができます。

実際の流れ

① スタート地点を現在地とする。
② 現在地の上下左右のマスが道であった場合、そのマスのスタート地点からの距離、その値とゴール地点からの距離の合計、その地点における親を記録する。
③ 合計が少ないところを現在地とし、合計が同じ場合はスタート地点からの距離が大きいところを現在地とし、それも同じ場合は合計が少ないところをランダムで現在地とする。
④ ②～③をゴール地点に行くまで繰り返す。
⑤ ゴール地点から親をたどり正解のルートを導く。

黄色のマスが現在地、青色のマスが探索されたマス(次に現在地とすることができるマス)、灰色のマスが探索が終わって現在地になることが出来ないマスです。
また、左の数字がスタートからの距離、右の数字がスタートからの距離とゴールまでの距離の合計です。

実際のプログラム

いろいろな機能を盛り込んだら800行超える長文プログラムになってしまいました。
読みづらいかもしれませんが、わかりやすくコメントアウトを付けたつもりです。

穴掘り法はmaze_print()の関数内、A*アルゴリズムはanswer()の関数内で実装されてます。

import tkinter as tk
from random import randint
import numpy as np
import threading
from datetime import datetime
from tkinter import filedialog
import subprocess
import win32gui
import win32ui
from ctypes import windll
from PIL import Image, ImageTk
import time
import os

def button1_press():    #スタートボタンを押したときの動作

    global maze_state, print_state

    if print_state == False:
        if answer_state == False:
            if maze_state == False:
                setup()
                maze_create()

            else:
                maze_state = False
                s3.set("スタート(Enter)")
                txt.config(state = tk.NORMAL)   #入力欄を有効化

def button2_press():    #解答ボタンを押したときの動作


    global maze_state, answer_state, answer_create, count

    if maze_clear == False:
        if print_state == False:
            if answer_create == True:
                if answer_create == True:
                    maze_state = False
                    answer_state = True

                    count = 0   #解答表示時のリストの要素指定変数を初期化
                    txt.config(state = tk.DISABLED) #入力欄を無効化
                    s3.set("現在利用できません")
                    s4.set("現在利用できません")
                    answer_print()

def setup():    #初期化関数

    global maze_side, maze, maze_y, maze_x, block_side, location_y, location_x, maze_ready, maze_start, maze_clear, passed, thread_sg_print, thread_answer, thread_stopwatch, screenshot_state, timer

    #穴掘り法の現在地を初期化
    location_y = 2
    location_x = 2

    #入力欄に何も入力されていなかった場合
    if txt.get() == "":
        maze_ready = False
        s1.set("値を入力してください。")

    #偶数または5未満の場合
    elif (int(txt.get()) + 2) % 2 == 0 or int(txt.get()) + 2 < 7:
        maze_ready = False
        s1.set("無効な値です。")

    #有効な数値の場合
    else:
        maze_start = True
        screenshot_state = False
        root.attributes("-toolwindow",True)    #最小化ボタンを非表示に
        maze_side = int(txt.get()) + 2  #入力された値に迷路の周りの分を足す
        block_side = canvas_size / (maze_side - 1)  #四角の大きさを計算
        maze_ready = True
        maze_clear = False
        s1.set("辺の長さを入力してください。")

        #ラベル、ボタン、キャンバスの配置
        canvas.grid(row = 0, column = 2, rowspan = 7)
        label1.grid(row = 1, column = 0, padx = 10, pady = 10)
        label2.grid(row = 1, column = 1, padx = 10, pady = 10)
        label4.grid(row = 2, column = 0, padx = 10, pady = 10)
        label5.grid(row = 2, column = 1, padx = 10, pady = 10)
        label6.grid(row = 3, column = 0, padx = 10, pady = 10)
        label7.grid(row = 3, column = 1, padx = 10, pady = 10)
        button2.grid(row = 4, column = 0, padx = 10, pady = 10)
        button3.grid(row = 6, column = 1, padx = 10, pady = 10)
        button4.grid(row = 6, column = 0, padx = 10, pady = 10)

        root.geometry("+0+0")   #rootを左上に固定

        #各関数をthreadingに代入
        thread_sg_print = threading.Thread(target = sg_print, daemon = True)
        thread_answer = threading.Thread(target = answer, daemon = True)
        thread_stopwatch = threading.Thread(target = stopwatch, daemon = True)

        #タイマー初期化
        s2.set("0.0秒")
        timer = 0.0
        txt.config(state =tk.DISABLED)  #入力欄を無効化
        canvas.delete("maze_block", "start", "goal", "answer_block", "oval", "passed", "image") #迷路の要素を削除

        #ゴール地点の座標を代入
        maze_y.append(maze_side - 3)
        maze_x.append(maze_side - 3)

        maze = [[0 for i in range(maze_side)] for j in range(maze_side)]    #迷路本体の変数

        #プレイヤーが通った場所を記憶する変数の初期化
        passed = [[0 for i in range(maze_side)] for j in range(maze_side)]
        passed[2][2] = 1
        passed[maze_side - 3][maze_side - 3] = 1

        #迷路の周りを壁に
        for i in range(maze_side):
            maze[0][i] = 1
            maze[i][0] = 1
            maze[maze_side - 1][i] = 1
            maze[i][maze_side - 1] = 1

def maze_create():  #迷路生成の初期化

    global complete, maze_state, print_state, answer_create, maze_start

    if maze_ready == True:
        print_state = True
        answer_create = False
        maze_start = True
        txt.config(state = tk.DISABLED) #入力欄を無効化
        s3.set("現在利用できません")
        s4.set("現在利用できません")
        s7.set("現在利用できません")
        s5.set("0回")
        s6.set("")
        canvas.delete("text")   #CLEARの文字を削除
        maze[maze_y[-1]][maze_x[-1]] = 1    #穴掘り法の現在地(ゴール地点)を道に

        #ゴール地点に四角を表示
        canvas.create_rectangle(
            (maze_side - 3) * block_side,
            (maze_side - 3) * block_side,
            (maze_side - 3) * block_side + block_side,
            (maze_side - 3) * block_side + block_side,
            width = 0, fill = "white", tag = "maze_block")
        complete = False    #迷路が完成したか
        for _ in range(maze_side // 30 + 1):    #迷路の大きさに合わせて関数を多重に呼び出し
            maze_print()

def maze_print():   #迷路生成(穴掘り法)

    global complete, maze_start, maze_state

    if maze[maze_y[-1]][maze_x[-1] - 2] == 0 or maze[maze_y[-1] + 2][maze_x[-1]] == 0 or maze[maze_y[-1]][maze_x[-1] + 2] == 0 or maze[maze_y[-1] - 2][maze_x[-1]] == 0:    #進める方向があるか確認
        direction = randint(0, 3)   #ランダムで方向を決定

        #現在地の2マス左が壁だった場合
        if direction == 0 and maze[maze_y[-1]][maze_x[-1] - 2] == 0:
            #2マス先まで道にする
            for i in range(1, 3):
                maze[maze_y[-1]][maze_x[-1] - i] = 1    #mazeのデータを壁から道に変更
                #道を描画
                canvas.create_rectangle(
                    (maze_x[-1] - i) * block_side,
                    maze_y[-1] * block_side,
                    (maze_x[-1] - i) * block_side + block_side,
                    maze_y[-1] * block_side + block_side,
                    width = 0, fill = "white", tag = "maze_block")
            #道筋に現在地を追加
            maze_y.append(maze_y[-1])
            maze_x.append(maze_x[-1] - 2)

        #現在地の2マス下が壁だった場合
        elif direction == 1 and maze[maze_y[-1] + 2][maze_x[-1]] == 0:
            #2マス先まで道にする
            for i in range(1, 3):
                maze[maze_y[-1] + i][maze_x[-1]] = 1    #mazeのデータを壁から道に変更
                #道を描画
                canvas.create_rectangle(
                    maze_x[-1] * block_side,
                    (maze_y[-1] + i) * block_side,
                    maze_x[-1] * block_side + block_side,
                    (maze_y[-1] + i) * block_side + block_side,
                    width = 0, fill = "white", tag = "maze_block")
            #道筋に現在地を追加
            maze_y.append(maze_y[-1] + 2)
            maze_x.append(maze_x[-1])

        #現在地の2マス右が壁だった場合
        elif direction == 2 and maze[maze_y[-1]][maze_x[-1] + 2] == 0:
            #2マス先まで道にする
            for i in range(1, 3):
                maze[maze_y[-1]][maze_x[-1] + i] = 1    #mazeのデータを壁から道に変更
                #道を描画
                canvas.create_rectangle(
                    (maze_x[-1] + i) * block_side,
                    maze_y[-1] * block_side,
                    (maze_x[-1] + i) * block_side + block_side,
                    maze_y[-1] * block_side + block_side,
                    width = 0, fill = "white", tag = "maze_block")
            #道筋に現在地を追加
            maze_y.append(maze_y[-1])
            maze_x.append(maze_x[-1] + 2)

        #現在地の2マス上が壁だった場合
        elif direction == 3 and maze[maze_y[-1] - 2][maze_x[-1]] == 0:
            #2マス先まで道にする
            for i in range(1, 3):
                maze[maze_y[-1] - i][maze_x[-1]] = 1    #mazeのデータを壁から道に変更
                #道を描画
                canvas.create_rectangle(
                    maze_x[-1] * block_side,
                    (maze_y[-1] - i) * block_side,
                    maze_x[-1] * block_side + block_side,
                    (maze_y[-1] - i) * block_side + block_side,
                    width = 0, fill = "white", tag = "maze_block")
            #道筋に現在地を追加
            maze_y.append(maze_y[-1] - 2)
            maze_x.append(maze_x[-1])
        
        if complete == False:
            root.after(1, maze_print)   #maze_printをもう一度繰り返す

    #進める方向がなく、道筋にひとつ前の現在地がある場合
    elif len(maze_y) >= 2:
        #道筋を一つ消して最後の値をひとつ前の現在地にする
        maze_y.pop()
        maze_x.pop()

        if complete == False:
            root.after(1, maze_print)   #maze_printをもう一度繰り返す

    #迷路が完成した場合
    else:
        maze_state = True
        maze_start = False
        if complete == False:
            thread_sg_print.start() #スタート地点とゴール地点を表示
            complete = True
            thread_answer.start()   #裏で解答を生成する

def sg_print(): #スタート、ゴール表示

    global print_state, maze_state, screenshot_state

    if maze_ready == True:
        #スタート地点を表示
        canvas.create_rectangle(
            2 * block_side,
            2 * block_side,
            2 * block_side + block_side,
            2 * block_side + block_side,
            width = 0, fill = "red", tag = "start")
        #ゴール地点を表示   
        canvas.create_rectangle(
            (maze_side - 3) * block_side,
            (maze_side - 3) * block_side,
            (maze_side - 3) * block_side + block_side,
            (maze_side - 3) * block_side + block_side,
            width = 0, fill = "blue", tag = "goal")
        screenshot()    #迷路保存
        s3.set("ストップ(Enter)")
        s7.set("保存(p)")
        stopwatch() #ストップウォッチ開始
        print_state = False
        #プレイヤー表示
        canvas.create_oval(
            location_x * block_side,
            location_y * block_side,
            location_x * block_side + block_side,
            location_y * block_side + block_side,
            width = 0, fill = "springgreen", tag = "oval")
        root.update()   #ウィンドウを更新

def answer():   #解答作成(A*アルゴリズム)

    global answer_create, maze_start

    #A*アルゴリズムの現在地の初期化
    answer_y = 2
    answer_x = 2

    #各変数初期化
    #・各座標の親（１個前の現在地）を代入するリスト
    parent_y = [[0 for i in range(maze_side)] for j in range(maze_side)]
    parent_x = [[0 for i in range(maze_side)] for j in range(maze_side)]

    #・スタートからの距離とゴールからの距離を足した値を代入するリスト
    total = [[maze_side * 2 for i in range(maze_side)] for j in range(maze_side)]

    #・スタートからの距離を代入するリスト
    start = [[0 for i in range(maze_side)] for j in range(maze_side)]

    #・探索を行える場所や行った場所を代入するリスト
    explored = [[0 for i in range(maze_side)] for j in range(maze_side)]

    #mazeの0,1を反転させてexploredに代入
    for i in range(maze_side):
        for j in range(maze_side):
            explored[i][j] = 1 if maze[i][j] == 0 else 0
    explored[2][2] = 2
    total_MIN = []  #totalの要素が最小である時の要素番号を代入するリスト
    start_MAX = []  #startの要素が最小である時の要素番号を代入するリスト

    while 1:

        #現在地の左が未探索の場合
        if explored[answer_y][answer_x - 1] == 0:
            start[answer_y][answer_x - 1] = start[answer_y][answer_x] + 1   #startにスタートからの距離を代入
            total[answer_y][answer_x - 1] = 2 * maze_side - answer_y - answer_x - 4 + start[answer_y][answer_x - 1] #totalにスタートからの距離とゴールからの距離を足した値を代入
            explored[answer_y][answer_x - 1] = 2    #現在地の左を探索可に
            #親の座標を代入
            parent_y[answer_y][answer_x - 1] = answer_y
            parent_x[answer_y][answer_x - 1] = answer_x

        #現在地の下が未探索の場合
        if explored[answer_y + 1][answer_x] == 0:
            start[answer_y + 1][answer_x] = start[answer_y][answer_x] + 1   #startにスタートからの距離を代入
            total[answer_y + 1][answer_x] = 2 * maze_side - answer_y - answer_x - 6 + start[answer_y + 1][answer_x] #totalにスタートからの距離とゴールからの距離を足した値を代入
            explored[answer_y + 1][answer_x] = 2    #現在地の下を探索可に
            #親の座標を代入
            parent_y[answer_y + 1][answer_x] = answer_y
            parent_x[answer_y + 1][answer_x] = answer_x

        #現在地の右が未探索の場合
        if explored[answer_y][answer_x + 1] == 0:
            start[answer_y][answer_x + 1] = start[answer_y][answer_x] + 1   #startにスタートからの距離を代入
            total[answer_y][answer_x + 1] = 2 * maze_side - answer_y - answer_x - 6 + start[answer_y][answer_x + 1] #totalにスタートからの距離とゴールからの距離を足した値を代入
            explored[answer_y][answer_x + 1] = 2    #現在地の右を探索可に
            #親の座標を代入
            parent_y[answer_y][answer_x + 1] = answer_y
            parent_x[answer_y][answer_x + 1] = answer_x

        #現在地の上が未探索の場合
        if explored[answer_y - 1][answer_x] == 0:
            start[answer_y - 1][answer_x] = start[answer_y][answer_x] + 1   #startにスタートからの距離を代入
            total[answer_y - 1][answer_x] = 2 * maze_side - answer_y - answer_x - 4 + start[answer_y - 1][answer_x] #totalにスタートからの距離とゴールからの距離を足した値を代入
            explored[answer_y - 1][answer_x] = 2    #現在地の上を探索可に
            #親の座標を代入
            parent_y[answer_y - 1][answer_x] = answer_y
            parent_x[answer_y - 1][answer_x] = answer_x

        explored[answer_y][answer_x] = 3    #現在地を探索済みに
        
        #ゴール地点が探索済みでない場合
        if explored[maze_side - 3][maze_side - 3] != 3:

            explored_2 = np.argwhere(np.array(explored) == 2).tolist()  #探索ができる場所(explored = 2)の座標を取得

            min = total[explored_2[0][0]][explored_2[0][1]] #explored_2で取得した探索できる場所の１つ目の値をminに代入
            total_MIN.clear()   #total_MINを初期化
            total_MIN.append(explored_2[0]) #total_MINにexplored_2の１つ目の値の座標を代入

            #探索できる場所が複数ある場合
            if len(explored_2) > 1:
                #explored_2の要素の数だけ繰り返す
                for i in range(1, len(explored_2)):
                    #i個目のtotalの値がminと同じ場合
                    if total[explored_2[i][0]][explored_2[i][1]] == min:
                        total_MIN.append(explored_2[i]) #total_MINにexplored_2のi個目の値の座標を代入

                    #i個目のtotalの値がminより小さい場合
                    elif total[explored_2[i][0]][explored_2[i][1]] < min:
                        min = total[explored_2[i][0]][explored_2[i][1]] #explored_2で取得した探索できる場所のiつ目の値をminに代入
                        total_MIN.clear()   #total_MINを初期化
                        total_MIN.append(explored_2[i]) #total_MINにexplored_2のi個目の値の座標を代入

            max = start[total_MIN[0][0]][total_MIN[0][1]]   #total_MINで取得した探索できる場所の１つ目の値をmaxに代入
            start_MAX.clear()   #start_MAXを初期化
            start_MAX.append(total_MIN[0])  #start_MAXにtotal_MINの１つ目の値の座標を代入

            #最小値が複数ある場合
            if len(total_MIN) > 1:
                for i in range(1, len(total_MIN)):
                    #i個目のstartの値がmaxと同じ場合
                    if start[total_MIN[i][0]][total_MIN[i][1]] == max:
                        start_MAX.append(total_MIN[i])  #start_MAXにtotal_MINのi個目の値の座標を代入

                    #i個目のstartの値がmaxより大きい場合
                    elif start[total_MIN[i][0]][total_MIN[i][1]] > max:
                        max = start[total_MIN[i][0]][total_MIN[i][1]]   #total_MINで取得した探索できる場所の１つ目の値をmaxに代入
                        start_MAX.clear()   #start_MAXを初期化
                        start_MAX.append(total_MIN[i])  #start_MAXにtotal_MINのi個目の値の座標を代入
            
            #totalが最小でstartが最大の要素の中からランダムで選び現在地とする
            i = randint(0, len(start_MAX) - 1)
            answer_y = start_MAX[i][0]
            answer_x = start_MAX[i][1]

        # # maze print
        # for i in range(maze_side): 
        #     for j in range(maze_side):
        #         print(maze[i][j], end = "  ")
        #     print()
        # print()

        # # explored print
        # for i in range(2, maze_side - 2):
        #     for j in range(2, maze_side - 2):
        #         print(explored[i][j], end = "  ")
        #     print()
        # print()

        # # total print
        # for i in range(2, maze_side - 2):
        #     for j in range(2, maze_side - 2):
        #         print(total[i][j], end = "  ")
        #     print()
        # print()

        # # start print
        # for i in range(2, maze_side - 2): 
        #     for j in range(2, maze_side - 2):
        #         print(start[i][j], end = "  ")
        #     print()
        # print()

        #迷路が終了した場合にループを停止する
        if maze_start == True:
            break
        
        #ゴール地点が探索済みの場合にループを停止する
        elif explored[maze_side - 3][maze_side - 3] == 3:
            #実際に正解の道が入れられる配列の初期化
            road_y.clear()
            road_x.clear()
            #ゴール地点の座標をリストに追加
            road_y.append(maze_side - 3)
            road_x.append(maze_side - 3)
            break

    if maze_start == False:

        while 1:
            #parent_x,parent_yの値を使い正解の道を逆算していく
            if (parent_y[road_y[-1]][road_x[-1]] == 2 and parent_x[road_y[-1]][road_x[-1]] == 2) or maze_start == True:
                break
            road_y.append(parent_y[road_y[-1]][road_x[-1]])
            road_x.append(parent_x[road_y[-2]][road_x[-1]])
        if maze_start == False:
            #ゴール地点からスタート地点の順番で配列に入っているので反転させる
            road_y.reverse()
            road_x.reverse()
            #追加したゴール地点の座標を削除
            road_y.pop()
            road_x.pop()
            answer_create = True
            s4.set("解答(i)")
            s6.set("{}回".format(len(road_y) + 1))
    
        # # total print
        # for i in range(2, maze_side - 2):
        #     for j in range(2, maze_side - 2):
        #         print(total[i][j], end = " ")
        #     print()
        # print()

        # # explored print
        # for i in range(2, maze_side - 2):
        #     for j in range(2, maze_side - 2):
        #         print(explored[i][j], end = "  ")
        #     print()
        # print()

def answer_print(): #解答表示

    global road_y, road_x, count, answer_state, answer_create

    #迷路の大きさ(maze_side)を200で割った値が1以上の時(迷路が大きいとき)
    if maze_side // 200 >= 1:
        #countが正解の要素数より少ないとき
        if count < len(road_y):
            #正解を表示
            canvas.create_rectangle(
                road_x[count] * block_side,
                road_y[count] * block_side,
                road_x[count] * block_side + block_side,
                road_y[count] * block_side + block_side,
                width = 0, fill = "palevioletred", tag = "answer_block")
            #現在地と重なった場合に現在地を前面にする
            if road_y[count] == location_y and road_x[count] == location_x:
                canvas.lift("oval")
            count += 1
            root.after(1, answer_print) #answer_printをもう一度繰り返す

        else:
            answer_create = False
            answer_state = False
            txt.config(state = tk.NORMAL)
            s3.set("スタート(Enter)")

    #迷路の大きさ(maze_side)を200で割った値が1以下の時(迷路が小さいとき)
    else:
        #countが正解の要素数より少ないとき
        if count < len(road_y):
            #正解を表示
            canvas.create_rectangle(
                road_x[count] * block_side,
                road_y[count] * block_side,
                road_x[count] * block_side + block_side,
                road_y[count] * block_side + block_side,
                width = 0, fill = "palevioletred", tag = "answer_block")
            #現在地と重なった場合に現在地を前面にする
            if road_y[count] == location_y and road_x[count] == location_x:
                canvas.lift("oval")
            count += 1
            root.after(2, answer_print) #answer_printをもう一度繰り返す

        else:
            answer_create = False
            answer_state = False
            txt.config(state = tk.NORMAL)
            s3.set("スタート(Enter)")

def key_event(c):   #キーイベント

    global location_y, location_x

    if maze_state == True:
        if print_state == False:
            #wまたは上矢印が押された場合
            if c.keysym == "Up" or c.keysym == "w":
                if maze[location_y - 1][location_x] == 1:
                    location_y -= 1
                    move()

            #aまたは左矢印が押された場合
            elif c.keysym == "Left" or c.keysym == "a":
                if maze[location_y][location_x - 1] == 1:
                    location_x -= 1
                    move()

            #sまたは下矢印が押された場合
            elif c.keysym == "Down" or c.keysym == "s":
                if maze[location_y + 1][location_x] == 1:
                    location_y += 1
                    move()

            #dまたは右矢印が押された場合
            elif c.keysym == "Right" or c.keysym == "d":
                if maze[location_y][location_x + 1] == 1:
                    location_x += 1
                    move()

    #iが押された場合
    if c.keysym == "i":
        button2_press()

    #エンターキーが押された場合
    if c.keysym == "Return":
        button1_press()

    #pが押された場合
    if c.keysym == "p":
        save()

    #oが押された場合
    if c.keysym == "o":
        fileopen()

    #escが押された場合
    if c.keysym == "Escape":
        root.destroy()

def move(): #プレイヤーの動き

    global maze_state, passed, maze_clear

    #もし1度も通ったことのない場所だった場合
    if passed[location_y][location_x] == 0:
        passed[location_y][location_x] = 1
        #通ったところに四角を表示
        canvas.create_rectangle(
            location_x * block_side,
            location_y * block_side,
            location_x * block_side + block_side,
            location_y * block_side + block_side,
            width = 0, fill = "tan1", tag = "passed")
        s5.set("{}回".format(int(s5.get().replace("回", "")) + 1))

    #現在地を削除して再表示
    canvas.delete("oval")
    canvas.create_oval(
        location_x * block_side,
        location_y * block_side,
        location_x * block_side + block_side,
        location_y * block_side + block_side,
        width = 0, fill = "springgreen", tag = "oval")

    #ゴール地点に到着した場合
    if location_y == maze_side - 3 and location_x == maze_side - 3:
        maze_state = False
        maze_clear = True
        #「CLEAR!!」の文字を影付きで表示
        canvas.create_text(canvas_size / 2 + 5, canvas_size / 2 + 5, text="CLEAR!!", font = ("游ゴシック", 100), fill = "black", tag = "text")
        canvas.create_text(canvas_size / 2, canvas_size / 2, text="CLEAR!!", font = ("游ゴシック", 100), fill = "yellow", tag = "text")
        s5.set("{}回".format(int(s5.get().replace("回", "")) + 1))
        txt.config(state =tk.NORMAL)    
        s3.set("スタート(Enter)")
        s4.set("現在利用できません")

def stopwatch():    #ストップウォッチ

    global timer

    if maze_state == True:

        #timerが3600以上(1時間以上)の場合
        if timer // 3600 >= 1:
            s2.set(f"{timer // 3600:.0f}時間 {timer % 3600 // 60:.0f}分 {timer % 3600 % 60:.1f}秒")
        
        #timerが60以上(1分以上)の場合
        elif timer // 60 >= 1:
            s2.set(f"{timer // 60:.0f}分 {timer % 60:.1f}秒")

        #timerが60未満(1分未満)の場合
        else:
            s2.set(f"{timer:.1f}秒")

        time.sleep(0.0984)  #ほかの処理によるラグを考慮してのタイミング調整
        timer += 0.1
        #threadingによる関数の再呼び出し
        thread_stopwatch = threading.Thread(target = stopwatch, daemon = True)
        thread_stopwatch.start()

def screenshot():   #画像作成(ネットを参考にしたため分からないところが多いため分かるところだけ注釈)

    global im, name, screenshot_state, img

    root.update()   #ウィンドウの更新

    name = datetime.now().strftime("%Y%m%d_%H%M%S_" + str(maze_side - 2) + "x" + str(maze_side - 2))    #今日の日付、迷路の大きさをnameに代入
    
    hwnd = win32gui.FindWindow(None, "自動生成迷路(ESCで終了)") #ウィンドウをウィンドウ名を使って取得

    #ウィンドウの大きさを取得し、そこからウィンドウの縦幅、横幅を計算
    left, top, right, bot = win32gui.GetWindowRect(hwnd)
    w = right - left
    h = bot - top

    hwndDC = win32gui.GetWindowDC(hwnd)
    mfcDC  = win32ui.CreateDCFromHandle(hwndDC)
    saveDC = mfcDC.CreateCompatibleDC()

    saveBitMap = win32ui.CreateBitmap()
    saveBitMap.CreateCompatibleBitmap(mfcDC, w, h)
    saveDC.SelectObject(saveBitMap)

    windll.user32.PrintWindow(hwnd, saveDC.GetSafeHdc(), 3) #よくわからないけどこれがないと迷路の描画がうまくいかない

    bmpinfo = saveBitMap.GetInfo()
    bmpstr = saveBitMap.GetBitmapBits(True)

    im = Image.frombuffer(
        "RGB",
        (bmpinfo["bmWidth"], bmpinfo["bmHeight"]),
        bmpstr, "raw", "BGRX", 0, 1)

    win32gui.DeleteObject(saveBitMap.GetHandle())
    saveDC.DeleteDC()
    mfcDC.DeleteDC()
    win32gui.ReleaseDC(hwnd, hwndDC)
    
    
    # im.save("test.png")
    im = im.crop((462, 2, 462 + canvas_size, 2 + canvas_size))  #画像のトリミング

    img = ImageTk.PhotoImage(image = im)    #ImageTkのPhotoImageに画像を変換

    #軽量化のために一度canvas上のすべてのオブジェクトを削除し代わりに作成した画像を表示する
    canvas.delete("maze_block", "start", "goal", "answer_block")
    canvas.create_image(2, 2, image = img, anchor = tk.NW, tag = "image")

    screenshot_state = True
    root.attributes("-toolwindow",False)

def save(): #画像保存

    if screenshot_state == True:
        file = filedialog.asksaveasfilename(initialfile = name, filetypes = [("PNG Image", ".png")], initialdir = "maze_image", defaultextension = "")  #画像を保存する場所を選択するウィンドウを表示
        if file:
            im.save(file)   #選択された場所に画像を保存

def fileopen(): #ファイルオープン
    subprocess.Popen(["explorer", r"maze_image"], shell=True)   #maze_imageをエクスプローラーで開く

def entry_limt(s):  #入力欄に入力された値が半角英数字かどうか判断する関数
    
    #入力欄に何も入力されてない状態になる場合(文字が消された場合)
    if s == "":
        return True
    
    #半角英数字以外が入力された場合
    elif not s.encode('utf-8').isdigit():
        return False
    
    return True

#穴掘り法の道筋
maze_x = [0]
maze_y = [0]

#解答の道筋
road_y = [0]
road_x = [0]

maze_state = False  #迷路が始まっているか
maze_ready = False  #迷路の準備ができているか
maze_clear = False  #迷路がクリアされているか

answer_state = False    #答えを表示したか
answer_create = False   #答えを生成したか

print_state = False #迷路を生成中かどうか

screenshot_state = False    #画像が作成されているかどうか

canvas_size = 1000  #迷路の大きさ

root = tk.Tk()
root.attributes("-toolwindow",False)
#高DPIに対応
try:
    windll.shcore.SetProcessDpiAwareness(True)
except:
    pass
root.resizable(width=False, height=False)   #ウィンドウのサイズ変更を不可能に
root.configure(bg = "gray80")   #背景色
root.title("自動生成迷路(ESCで終了)")  #タイトル
root.bind("<KeyPress>", key_event)

if not os.path.exists("maze_image"):
    os.makedirs("maze_image")

s1 = tk.StringVar() #入力欄情報表示ラベル
s1.set("辺の長さを入力してください。")

s2 = tk.StringVar() #経過時間表示ラベル
s2.set("0.0秒")

s3 = tk.StringVar() #start,stopボタン
s3.set("スタート(Enter)")

s4 = tk.StringVar() #解答ボタン
s4.set("現在利用できません。")

s5 = tk.StringVar() #移動回数表示ラベル
s5.set("0回")

s6 = tk.StringVar() #最小回数表示ラベル

s7 = tk.StringVar() #画像保存ボタン
s7.set("現在利用できません。")

label1 = tk.Label(  #「経過時間」ラベル
    text = "経過時間",
    width = 25,
    bg = "gray80",
    font = ("游ゴシック", 10)
)

label2 = tk.Label(  #経過時間表示ラベル
    textvariable = s2,
    width = 25,
    bg = "gray80",
    font = ("游ゴシック", 10)
)

label3 = tk.Label(  #入力欄情報表示ラベル
    textvariable = s1,
    width = 25,
    bg = "gray80",
    font = ("游ゴシック", 10)
)
label3.grid(row = 5, column = 0, pady = 10)

label4 = tk.Label(  #「移動回数」ラベル
    text = "移動回数",
    width = 25,
    bg = "gray80",
    font = ("游ゴシック", 10)
)

label5 = tk.Label(  #移動回数表示ラベル
    textvariable = s5,
    width = 25,
    bg = "gray80",
    font = ("游ゴシック", 10)
)

label6 = tk.Label(  #「最小回数」ラベル
    text = "最少回数",
    width = 25,
    bg = "gray80",
    font = ("游ゴシック", 10)
)

label7 = tk.Label(  #最小回数表示ラベル
    textvariable = s6,
    width = 25,
    bg = "gray80",
    font = ("游ゴシック", 10)
)

button1 = tk.Button(    #start,stopボタン
    textvariable = s3,
    width = 25,
    height = 2,
    font = ("游ゴシック", 10),
    command = button1_press
)
button1.grid(row = 4, column = 1, padx = 10, pady = 10)

button2 = tk.Button(    #解答ボタン
    textvariable = s4,
    width = 25,
    height = 2,
    font = ("游ゴシック", 10),
    command = button2_press
)

button3 = tk.Button(    #画像保存ボタン
    textvariable = s7,
    width = 25,
    height = 2,
    font = ("游ゴシック", 10),
    command = save
)

button4 = tk.Button(    #「フォルダーを開く」ボタン
    text = "フォルダーを開く(o)",
    width = 25,
    height = 2,
    font = ("游ゴシック", 10),
    command = fileopen
)

vc = root.register(entry_limt)  #入力欄のvcmdオプションで指定するコールバック関数を定義

txt = tk.Entry( #入力欄
    width=25,
    font = ("游ゴシック", 10),
    validate = "key",
    vcmd = (vc, "%P")
)
txt.grid(row = 5, column = 1, padx = 10, pady = 10)

canvas = tk.Canvas( #canvas作成
    width = canvas_size,
    height = canvas_size,
    background = "gray25"
)

root.mainloop()

最後に

僕がこのプログラムを作るときにネットで調べた資料がどれも難しくて理解しにくかったので、これからこのアルゴリズムに興味が湧いた人が少しでも理解しやすいようにまとめたつもりです。
また新しいプログラムを作成したときにはまとめてみようかなと思います。