BFSで迷路攻略！（競プロで得た技術で遊ぼう～その１～）

#はじめに
子供のころ迷路を作って遊んだ人も多いと思います。中には見るのも嫌になるくらい細かくぎっしりと作られた迷路もあったかと思います。そんな迷路を瞬時に解けたらかっこいいですよね。それをプログラミングによって、実現しようというのが今回のテーマです。

つまり
Input: 迷路の画像
output: スタートからゴールまでのルートを示した画像
となります。

#方針
①pythonのOpenCVを用いて画像を読み込み、それを二値化し道と壁を分けます。
OpenCVの導入はこちら→https://qiita.com/fiftystorm36/items/1a285b5fbf99f8ac82eb
(スタート地点: S , 道： . , 壁: # , ゴール地点: G としました）
画像データを

S.##...
#..#.#.
#....#.
#.####.
#...##.
######G

と変換するような感じです。

②このように変換するとあとは競プロでよく出てくる幅優先探索でスタートからゴールまでの最短距離を求めることができます。
幅優先探索(BFS)→https://qiita.com/drken/items/996d80bcae64649a6580

③②で経路復元も同時に行い画像データに描画します。
経路復元の考え方→https://qiita.com/drken/items/0c7bab0384438f285f93
どこからやってきたかを記録し、ゴールから逆にたどっていけばよいです。

#補足
###道と壁の判別について
迷路の多くは道が白（薄い色）、壁が黒（濃い色）です。そこで画像をグレースケールに変換し、ある値を境に道と壁を分けるようにすればよいです。また、入口、出口が開いているものについてはあらかじめふさぐことで、迷路の外側をたどらないようにしました（ここはペイント等を用い手作業）。

###スタート地点とゴール地点の入力
スタート地点とゴール地点の入力はAI等で判断する方法もあるかもしれませんが人の目で判断した方が実装が楽なので、画像クリックで入力できるようにしました。

#コード

BFSmeiro.py

import collections
import copy
import cv2

class meiro():
    def __init__(self,filename):
        self.filename = filename
        self.lsNM = self.con_img_to_ls(self.filename)
        self.setst()
        self.setgl()
        self.solve()

    def con_img_to_ls(self,filename):
        img = cv2.imread(filename, 0) #グレースケールで読み込み
        self.N = len(img)             #横のピクセル長
        self.M = len(img[0])          #縦のピクセル長
        lsNM = [['.']*(self.M) for i in range(self.N)]
        cnt = 0
        for i in range(self.N):
            for j in range(self.M):
                if img[i][j] <= 180: #道を通れないor壁を突き抜ける場合は値を変える
                    lsNM[i][j] = '#' #壁を作る
                    cnt += 1
        return lsNM

    def setst(self):
        def printCoor(event,x,y,flags,param):
            if event == cv2.EVENT_LBUTTONDOWN:
                print('start =',y, x)
                self.st = (y,x)
        img = cv2.imread(self.filename)
        cv2.namedWindow('setstart',cv2.WINDOW_NORMAL)
        cv2.setMouseCallback('setstart',printCoor)
        cv2.moveWindow('setstart', 100, 200)
        while(1):
            cv2.imshow('setstart',img)
            #ESCキーでブレーク
            if cv2.waitKey(20) & 0xFF == 27:
                break
        cv2.destroyAllWindows()
        self.lsNM[self.st[0]][self.st[1]] = 'S'

    def setgl(self):
        def printCoor(event,x,y,flags,param):
            if event == cv2.EVENT_LBUTTONDOWN:
                print('goal =',y, x)
                self.gl = (y,x)
        img = cv2.imread(self.filename)
        cv2.namedWindow('setgoal',cv2.WINDOW_NORMAL)
        cv2.setMouseCallback('setgoal',printCoor)
        cv2.moveWindow('setgoal', 100, 200)
        while(1):
            cv2.imshow('setgoal',img)
            #ESCキーでブレーク
            if cv2.waitKey(20) & 0xFF == 27:
                break
        cv2.destroyAllWindows()
        self.lsNM[self.gl[0]][self.gl[1]] = 'G'

    def solve(self):  #BFSをやるところ
        d = collections.deque([self.st])
        dxy = [(1,0),(0,1),(-1,0),(0,-1)]
        used = [[False]*self.M for i in range(self.N)]
        lscost = [[float('INF')]*self.M for i in range(self.N)]
        lscost[self.st[0]][self.st[1]] = 0
        comefrom = [[-1]*self.M for i in range(self.N)]
        while d:
            x,y = d.popleft()
            if used[x][y]:
                continue
            used[x][y] = True
            for dx,dy in dxy:
                if 0 <= x+dx < self.N and 0 <= y+dy < self.M:
                    if used[x+dx][y+dy]:
                        continue
                    if self.lsNM[x+dx][y+dy] == '#':
                        continue
                    if lscost[x+dx][y+dy] > lscost[x][y] +1:
                        lscost[x+dx][y+dy] = lscost[x][y] +1
                        comefrom[x+dx][y+dy] = (x,y)
                        d.append((x+dx,y+dy))
        print('cost =',lscost[self.gl[0]][self.gl[1]])
        #たどり着けない場合
        if lscost[self.gl[0]][self.gl[1]] == float('INF'):
            print('No ans')
            exit()
        #経路復元
        self.lsNM2 = copy.deepcopy(self.lsNM)
        x,y = self.gl
        while True:
            x,y = comefrom[x][y]
            if self.lsNM2[x][y] == 'S':
                break
            self.lsNM2[x][y] = 'o'

    def output(self,outputname): #画像の作成と出力
        lsimg = cv2.imread(self.filename)
        for i in range(self.N):
            for j in range(self.M):
                if self.lsNM2[i][j] == 'o':
                    lsimg[i][j][1] = 0
        cv2.imwrite(outputname, lsimg)

if __name__ == "__main__":
    filename = input('filename = ')
    meiroA = meiro(filename)
    meiroA.output('ans2.jpg')

実行すると

filename = 

と出てくるので、解きたい迷路画像のファイル名を入れます。
するとsetstartというウィンドウが出てくるのでスタート地点をクリックしEscを押します。
ゴール地点の入力も同様です。
計算が終わると、スタート地点からゴール地点までに通ったピクセル数と最短経路を示した画像が出力されます。

###実行例
画像 https://www.ac-illust.com/main/search_result.php?word=%E8%BF%B7%E8%B7%AF より

答え

画像 http://brainstraining.blog7.fc2.com/blog-category-42.html より

答え

最短ルートを求めている関係で壁に沿った動きになっているのはご愛嬌。
富士急にある迷路も同様に解くことができます（https://twitter.com/fujikyunow/status/1324181236173082624?lang=cs )
皆さん各自で試してみてください。

#おわりに
私は情報系の出身ではないので幅優先探索BFSを競プロをやる中で初めて知りました。このような形で得た技術を生かして遊べることに楽しさを感じつつ、競プロでもさらに上を目指していこうと思いました。
次回はbitDPで首都圏の主要駅を回る最短ルートを求める記事を書こうと思います。

#参考記事一覧
https://qiita.com/fiftystorm36/items/1a285b5fbf99f8ac82eb opencvの導入
https://qiita.com/drken/items/996d80bcae64649a6580 BFSについて
https://qiita.com/drken/items/0c7bab0384438f285f93 経路復元について
https://www.omoshiro-suugaku.com/entry/mouse-position opencvの画像においてクリックで座標を取得するやり方について
以下迷路画像のリンク
https://www.ac-illust.com/main/search_result.php?word=%E8%BF%B7%E8%B7%AF
http://brainstraining.blog7.fc2.com/blog-category-42.html
https://twitter.com/fujikyunow/status/1324181236173082624?lang=cs