週刊少年ジャンプのプレゼント企画パズルをなるべく自動で解く 〜迷路編〜

序

みなさん、ジャンプは読んでますか？
最近は『呪術廻戦』がアツいですね。
ちなみに私の一番好きなジャンプ漫画は『ダブルアーツ』です。

さて、2018年現在、『約束のネバーランド』という漫画が連載中です。
本記事で取り上げるのはこの漫画の本編ではなく、読者プレゼント企画コーナー『ミネルヴァ機密通信』に載っているパズルです。
こちらをプログラミングの力で解きたいと思います。

今回は、2018年36・37号（8月20日・27日合併特大号）に掲載されていた迷路を解いてみました。

著作権について

今手元には実際に迷路を解いた後の画像とプログラムがあるわけですが、これを公開するには超えなければいけない壁があります。

それは著作権問題です。

漫画本編ではなく企画ページに過ぎないとはいえ、雑誌として発行されている以上は全てのページにおそらく著作権があります。
それに、応募〆切は多分過ぎているのですが、やはりクイズの答えをバーン！と公開しちゃうのもアウトな気がします。

ということで、類題を自分で作って自分でもう一度解くことにしました。

今回用意した類題はこちら。

iPadでせっせと描きました。
この画像が雑誌に載っているというシチュエーションを想定して始めていきます。
なので、実際はこんな綺麗な電子データの画像はありません。
まずはスマホでこの迷路をパシャるところからスタートです。

ソースコード、画像データ等

以下に上げました。
https://github.com/ikngtty/solve_maze

本記事では、このコードを完成させるまでに学んだこととか思いついたこととかを残していきます。

選定技術

• OpenCV
  • 画像処理ライブラリ。
  • なんか基本っぽい。
  • 未経験（そもそも画像処理をしたことがない）。
• Python3
  • OpenCVを使える言語の中で一番モダンそうなやつ。
  • 未経験（Ruby使いなので）。
  • 適当な入門書とFluent Pythonをつまみ読みして勉強しました。

とまあ未経験づくしなので、マサカリたくさんお待ちしてます。

前処理

スマホで撮った画像はこのままだと扱いづらそうなので、解きやすいよう加工していきます。
まずは前提知識から。

OpenCVにおける画像の取り扱い

NumPyのndarray型で扱います。
要は多次元配列です。

白黒画像の場合、縦×横の2次元配列で、各項にグレーの濃さが0〜255の数値で入っています。0が黒、255が白です。
カラー画像の場合、各項にBGR値（RGB値ではないので注意）の配列が入るので、縦×横×3色で3次元配列です。

write_sample.py

import cv2 as cv
import numpy as np


# 白黒画像の書き込み
gray_img = np.array([[0, 0, 255],
                     [100, 150, 200]])
cv.imwrite("gray.png", gray_img)

# カラー画像の書き込み
color_img = np.array(
    [[[255, 0, 0], [0, 255, 0], [0, 0, 255]],
     [[0, 0, 0], [255, 255, 255], [150, 150, 150]]]
)
cv.imwrite("color.png", color_img)

read_sample.py

import cv2 as cv


# カラー画像の読み込み
gray_img = cv.imread("color.png", cv.IMREAD_COLOR)
print(gray_img)
# =>
# [[[255   0   0]
#   [  0 255   0]
#   [  0   0 255]]
#
#  [[  0   0   0]
#   [255 255 255]
#   [150 150 150]]]

# カラー画像を白黒画像として読み込み
color_img = cv.imread("color.png", cv.IMREAD_GRAYSCALE)
print(color_img)
# =>
# [[ 29 149  76]
#  [  0 255 150]]

Step0. 白黒化

というわけで、まずはカラーより情報量の少ない白黒画像として読み込むことにします。
読み込んだデータをそのまま書き込むとこんな感じです。

あんま代わり映えはしないですが、なんとなく赤みが減りました。

Step1. 二値化

配列の中には0〜255の濃さが入っていますが、必要なのは「黒（壁）か、白（通り道）か」の情報だけです。
どのぐらい濃いかの情報は不要です。
Pythonちゃんが「ここは妙に濃いから通れないかも...」と変なシミとかを意識しだしても困ります。

というわけで、適当に設定した閾値を基準に、配列の中の値を0か255かの二値に仕分けてしまいます。
これが二値化です。

今回は加えて、適応的閾値処理というものを行います。
これは、全体的に白っぽい区域は白に近い閾値で、黒っぽい区域は黒に近い閾値で、と閾値を細かく変えていく処理です。
用意した画像は真ん中が明るく、4隅は光の加減で暗めになっていますが、この処理によってその辺のばらつきも無くせそうです。

複雑そうですが、基本はOpenCVがよしなにやってくれます。
我々がやることは、読み込んだ画像の配列データをadaptiveThreshold関数に渡し、同時に渡すパラメータを適当に弄りまくって良さげな値を探すことだけです。
詳しくはソースとリンク先の公式ドキュメント参照。

変換処理後の配列が返されるので、画像ファイルとして書き出してみましょう。

先生の印刷したプリントって感じになりました。
適応的閾値処理により、濃淡の差がなくなったのがわかると思います。
しかし、通り道はゴミだらけです。

このゴミを無視していいのかPythonちゃんに判断させるのは大変です。
次はゴミ掃除をしましょう。

Step2. ノイズ除去

medianBlur関数を使用して、メディアンフィルター処理を行います。
ぼかし処理の一種です。
各ピクセルを周囲のピクセルの平均値に置き換える処理のようです。
1ピクセルだけ黒くても、周りが真っ白だと真っ白になるわけです。
同調圧力で子供の個性を失わせるような処理だと思ってください。

ノイズは言い換えれば周囲から浮いた子供みたいなものなので、この処理によって除去できます。

先程と同様に変換後の配列データを画像ファイルとして書き出してみましょう。

"ゴミ"が綺麗に掃除されました。
下の文字が読めなくなりましたが、気にしないことにします。

Step3. 画質縮小

十分解けそうな感じになりましたが、もっと画素を減らして計算量を減らすことができそうです。
resize関数を使用します。

画質を下げすぎると壁が崩壊して穴ができ始めるので、ギリギリを探ってみたところ今回は1/25倍まで縮小できました。

かなりのギリギリ感ですね。
下の文字が最早「.............」になっています。

Step4. 二値化、再び

画質の縮小により、排除したはずの中途半端な灰色が再び出てきてしまいます。

もう一度二値化を行いますが、今回は適応的閾値処理は不要そうなので、通常のthreshold関数を使用します。


すっきりしました。
なんか遠回りをしてそうな気もするんですが、とりあえず前処理は以上です。

迷路を解く

スタート地点、ゴール地点の座標特定

さて、いよいよ迷路を解いていきますが、それにはまずスタート地点とゴール地点がどこにあるかをPythonが認識できないといけません。

ですが、迷路中のSマーク、GマークをPythonに検出させるのは骨が折れそうです。
今回は手を抜いて、人力でスタート地点とゴール地点の場所を特定することにします。

具体的には以下のコードを用います。

main.py

import numpy as np
import typing


def check_point(input,
                point: typing.Tuple):
    """
    渡された座標を左上の頂点とする灰色の四角形を、渡された白黒画像配列に描画して返す。
    """
    square = [(point[0] + dy, point[1] + dx)
              for dy in range(7)
              for dx in range(7)]
    output = np.ndarray.copy(input)
    for p in square:
        output[p] = 150  # 適当な灰色
    return output

main.py

start_point = (15, 80)
check_point(input, start_point)

うーん、もうちょっと左下ですね。

main.py

start_point = (22, 70)
check_point(input, start_point)

お、ちょうど良い感じ。

とまあこんな風です。

Sマークの円の中からスタートすると迷宮入りするので、この辺が良さげです。
ゴール地点の座標も同様に特定します。

A*（A-star）アルゴリズムの適用

さて、いよいよ迷路を解く段階ですが、実はここが一番書くことが無いです。
というのも、"Aアルゴリズム"でググると分かりやすい説明記事が既にいっぱいあるからです。
ここを期待してた人ごめんなさい。**Aアルゴリズムって言葉だけ覚えて帰ってください。**

例えば私は以下の記事を参考にしました。
よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき)

実際のソースコードはGitHub参照ですが、独自に変えてみた点や、上記記事では触れていないポイントだけまとめます。

• OpenしたNodeは、座標をキーにしたdictにキャッシュとして保存
• Nodeに比較演算子（>,=等）を適用した際、スコアで比較するように定義
• より正確には、「スコアが同じ場合に実コストを比較する」ため、(スコア, 実コスト, 座標)のタプルを比較（実コストも等しい場合には座標で仮の大小関係を決める）
• OpenしたNodeはヒープキューにpushし、次の基準Nodeはヒープキューからpopすることで、最小スコアのNodeを見つける計算量をなるべく削減（上記で比較演算子を定義したのはこのため）
• Nodeクラスのステータス属性を排除（ヒープキューに入っていればOpen、キャッシュがあればNone以外と判断でき、それで十分であるため）
• Nodeクラスの__slots__属性を設定（パフォーマンスが良さそう）
• 4方向のみ移動にした（ななめに進む時も経路を太めにしたかった）
• 推定コストは物理距離にした（色々調べた中でなんとなく良さそうな感じがした）

経路の描画

main.py

import numpy as np
import typing


def draw_path(input,
              path: typing.Iterable[typing.Tuple]):
    """
    渡された座標リストを元に、白黒画像配列に経路を灰色に描画して返す。
    """
    # 周辺ピクセルも雑に描画対象に加え、線を太くする
    delta_square = [(y, x)
                    for y in range(3)
                    for x in range(3)]
    spread_path = [tuple(p[i] + d[i] for i in range(2))
                   for p in path
                   for d in delta_square]
    output = np.ndarray.copy(input)
    for p in spread_path:
        output[p] = 150
    return output

綺麗に解けていますね！！

もう少し見やすくします。

main.py

import numpy as np


def paint_path(input):
    """白黒画像配列をカラー画像配列に変換して返す。灰色の経路部分は茶色に着色。"""
    output = np.ndarray(shape=input.shape + (3,))
    for iy, row in enumerate(input):
        for ix, grayscale in enumerate(row):
            if grayscale > 200:
                output[iy, ix] = [255, 255, 255]  # 白 → 白(BGR)
            elif grayscale < 50:
                output[iy, ix] = [0, 0, 0]        # 黒 → 黒(BGR)
            else:
                output[iy, ix] = [40, 70, 110]    # 灰 → 茶(BGR)
    return output

**なんとなく茶色くしました。**

完成です！！

結

さて、何の動物が浮かび上がってきたでしょうか。

私の用意した迷路が稚拙すぎて、ちょっと分かりづらかったかもしれません。
補助線を加えて分かりやすくしてみます。

答えは、綺麗にとぐろを巻いたヘビでした！！！

※ジャンプの迷路はもっと複雑な絵柄が出てきます。

余裕があったら他のパズルにもそのうち挑戦したいと思います。
おしまい。