Python: 画像で与えられた迷路に対し2点間の最短経路を求める

迷路の描かれた画像に対して、ピクセルの座標で指定したスタート地点とゴール地点の最短経路を求めるプログラムをPython+PILで書いてみた。使用する画像は、デジカメで撮ったものでも、ウェブから拾ってきたものでも、ペイントソフトで自作したものでも構わない。 まずは使用例を見て欲しい。この画像は携帯カメラで撮った自作の簡単な迷路だ(画像上)。それに対して指定した2点間の最短経路を赤線で示してみた(画像下)。ピクセル単位で計測しているので赤線が若干ガタガタしていて完全な最短経路ではないがほぼ最短と考えていいだろう。迷路画像(画像上)をmaze01.jpgとし、スタート地点の座標が(240, 160)、ゴール地点の座標が(210, 400)の場合、コマンドラインで以下のように実行する。 maze_solver.py maze01.jpg -s 240 160 -g 210 400 これで最短経路を

[bluele]

ide

[hiroyuki1983]

アルゴリズム

[darwinia]

すげぇ

[mattn]

すげー

[tanakaBox]

よく考えれば、ドットの集まり。つまり、2階調化して2次元配列と考えれば解けるな。面白い。

[linden]

Pythonはわからないんだけど、すごいなこれ。

[hypersomnia]

maze_solver.py #!/usr/bin/env python # -*- coding: utf-8 -*- import sys, os, math, heapq, Image, ImageDraw # Connected Component Labeling - Label Equivalence method class CCL: def __init__(self, imagefile, threshold, area): im = Image.open(imagefile) im = im.convert("RGB") self.orig_size =

[yuiseki]

suge-