この記事はtomowarkar ひとりAdvent Calendar 2019の20日目の記事です。

はじめに

幅優先探索とか、深さ優先探索とかなんか難しそうで今まであまり触れてこなかったんですが、なんとなくやる気になったので迷路の最短経路探索を書いてみました。

内容自体はよく出てくるような内容で、特段変なことはしてないのですが
備忘録兼アウトプットとして書いていきます。

成果物

コード

def printMaze(maze):
    """迷路を描画"""
    for i in range(maze["height"]):
        row = maze["data"][i * maze["width"] : (i + 1) * maze["width"]]
        print(" ".join(row))


def at(x, y, maze):
    """迷路の(x, y)座標のオブジェクトを返す"""
    return maze["data"][y * maze["width"] + x]


def setChar(x, y, char, maze):
    """迷路の(x, y)座標のオブジェクトを設定する"""
    arr = list(maze["data"])
    arr[y * maze["width"] + x] = char
    maze["data"] = "".join(arr)


if __name__ == "__main__":
    maze = {
        "width": 43,
        "height": 35,
        "data": "###########################################S #   #           #                       ## ### ########### # ################# ### ##   #           # # #               # # # #### ########### # # ##### ##### ### ### # ## #         # # #       # #   # # #     # ## ####### ### # ####### ### ### # ##### # ##         #       #         #     #     # ###### ### ##### ### ##### ### ##### ##### ##   # # # #   # #   # #   #   #     #     ## # # # # ### # # ### ### # ### ### # ### ## # # # #   # # # #     # # #   # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # #       #       #     # #   # # # # ## # # # ##### ### ### ####### ### ### # # ## # # #   # #   # # #           #     # # ## # # ##### ### ### ########### ### ### # ## # #         #             # # # # #   # ## # ##### ### # ### ### ##### # # # ### # ## #     # # # # # #   # #       # #   # # ## ##### ### # ### ##### ### ### # ### # # ##     #     #               # # #   # #   #### # # ### ### ######### ### ### ### ### ## # # # # # #   #       # #             # ## ### ### ### ##### # ### ### ####### ### ##             #   # # #     # #   #   #   ## ### ####### ### ### # ##### ### ### # #### # # # #       #     # #       #   # #   ## # # # ### ### # ##### ##### ##### # ### ## # # # #   # # # #         #       #   # ## # # # # ### ### # # ####### ##### ### # ## # #   # #       # # #       #   # #   # ## # ##### # ####### # ######### ### # ### ## #       #         #               # #   G###########################################",
    }
    start = [0, 1]
    goal = [42, 33]

    visited = [False] * maze["width"] * maze["height"]
    costs = [999999] * maze["width"] * maze["height"]

    # スタート位置(0, 1)をqueueに入れる
    queue = [start]
    costs[start[1] * maze["width"] + start[0]] = 0

    while len(queue) > 0:
        # queueから位置を取り出す
        p, queue = queue[0], queue[1:]
        visited[p[1] * maze["width"] + p[0]] = True

        # 上下左右を検証
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = p[0] + i[0], p[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue

            if at(x, y, maze) == " " and visited[y * maze["width"] + x] == False:
                queue.append([x, y])
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
            if at(x, y, maze) == "G":
                queue = []
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
                break
    # costsをゴールから辿り、最短経路を求める
    point = goal
    cost = costs[point[1] * maze["width"] + point[0]]
    while cost != 1:
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = point[0] + i[0], point[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue
            if costs[y * maze["width"] + x] == cost - 1:
                cost = costs[y * maze["width"] + x]
                point = [x, y]
                setChar(x, y, ".", maze)
                break

    printMaze(maze)

解説

迷路情報を辞書型で定義します。
"#"が壁" "が通路, "S", "G"がそれぞれスタートとゴールという形です。
同時にスタートとゴールの(x, y)座標も手入力で入れてしまいます。

maze = {
    "width": 43,
    "height": 35,
    "data": "###########################################S #   #           #                       ## ### ########### # ################# ### ##   #           # # #               # # # #### ########### # # ##### ##### ### ### # ## #         # # #       # #   # # #     # ## ####### ### # ####### ### ### # ##### # ##         #       #         #     #     # ###### ### ##### ### ##### ### ##### ##### ##   # # # #   # #   # #   #   #     #     ## # # # # ### # # ### ### # ### ### # ### ## # # # #   # # # #     # # #   # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # #       #       #     # #   # # # # ## # # # ##### ### ### ####### ### ### # # ## # # #   # #   # # #           #     # # ## # # ##### ### ### ########### ### ### # ## # #         #             # # # # #   # ## # ##### ### # ### ### ##### # # # ### # ## #     # # # # # #   # #       # #   # # ## ##### ### # ### ##### ### ### # ### # # ##     #     #               # # #   # #   #### # # ### ### ######### ### ### ### ### ## # # # # # #   #       # #             # ## ### ### ### ##### # ### ### ####### ### ##             #   # # #     # #   #   #   ## ### ####### ### ### # ##### ### ### # #### # # # #       #     # #       #   # #   ## # # # ### ### # ##### ##### ##### # ### ## # # # #   # # # #         #       #   # ## # # # # ### ### # # ####### ##### ### # ## # #   # #       # # #       #   # #   # ## # ##### # ####### # ######### ### # ### ## #       #         #               # #   G###########################################",
}
start = [0, 1]
goal = [42, 33]

下準備

探索に用いるqueueとvisited, 最短経路を導く際に用いるcostsを定義します。

迷路は二次元配列で出力しますが、データ加工は全て一次元配列でおこなうので、適宜変換を行う必要があります。


visited = [False] * maze["width"] * maze["height"]
costs = [999999] * maze["width"] * maze["height"]

# スタート位置(0, 1)をqueueに入れる
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0

探索メイン処理

幅優先探索なので、キューの頭から取り出して検証していきます。
上下左右の状態が通路であればどんどんキューに追加していきます。
コストの更新は常に基準点のコストから+1していくことで、最短経路を導出する際に使用することができます。

    while len(queue) > 0:
        # queueから位置を取り出す
        p, queue = queue[0], queue[1:]
        visited[p[1] * maze["width"] + p[0]] = True

        # 上下左右を検証
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = p[0] + i[0], p[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue

            if at(x, y, maze) == " " and visited[y * maze["width"] + x] == False:
                queue.append([x, y])
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
            if at(x, y, maze) == "G":
                queue = []
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
                break

最短経路導出

costはスタートからかかる距離と同意であるため、ゴール位置のコストから０まで遡っていくことで最短経路が導出できます。

    # costsをゴールから辿り、最短経路を求める
    point = goal
    cost = costs[point[1] * maze["width"] + point[0]]
    while cost != 1:
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = point[0] + i[0], point[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue
            if costs[y * maze["width"] + x] == cost - 1:
                cost = costs[y * maze["width"] + x]
                point = [x, y]
                setChar(x, y, ".", maze)
                break

    printMaze(maze)

結果

おわりに

以上明日も頑張ります！！
tomowarkar ひとりAdvent Calendar Advent Calendar 2019

参考

https://qiita.com/nati-ueno/items/a789095aff0aec10d5d0
https://vigne-cla.com/18-2/