Представление и решение лабиринта по изображению

| | | | | | | | | | | | | | | | | | | | | | | | |

Как лучше всего представлять и решать лабиринт по изображению?

The обложка The Scope Issue 134

Как лучше всего прочитать изображение в формате JPEG (как показано выше), разобрать его в какую-либо структуру данных и решить лабиринт? Мой первый Интуиция состоит в том, чтобы считывать изображение попиксельно и сохранять его в списке (массиве) логических значений: True для белого пикселя и False для небелого. пиксель (цвета можно отбросить). Проблема с этим методом заключается в том, что изображение может не быть «идеальным по пикселям». Под этим я просто подразумеваю, что если где-то на стене есть белый пиксель, он может создать непреднамеренный путь.

Еще один метод (который пришел ко мне после некоторых размышлений) заключается в преобразовании изображения в файл SVG, представляющий собой список путей, нарисованных на холсте. Таким образом, пути можно было прочитать в тот же список (логические значения), где True указывает путь или стену, False указывает на доступное для путешествий место. Проблема с этим методом возникает, если преобразование не является точным на 100% и не полностью соединяет все стены, создавая зазоры.

Также проблема с преобразованием в SVG заключается в том, что линии не «идеально " прямой. Это приводит к тому, что пути представляют собой кубические кривые Безье. Со списком (массивом) логических значений, проиндексированных целыми числами, кривые не будут легко переноситься, и все точки этой линии на кривой должны быть вычислены, но не будут точно соответствовать индексам списка.

Я предполагаю, что, хотя один из этих методов может работать (хотя, вероятно, и нет), они ужасно неэффективны для такого большого изображения и что существует лучший способ. Как это лучше всего (наиболее эффективно и/или с наименьшей сложностью ) готово? Есть ли лучший способ?

Затем следует решение лабиринта. Если я воспользуюсь одним из первых двух методов, то, по сути, получу матрицу. Согласно этот ответ, хороший способ представить лабиринт - использовать дерево, а хороший способ решить его - использовать Алгоритм A*. Как создать дерево из изображения? Есть идеи?

TL;DR
Лучший способ анализа? та структура? Как указанная структура может помочь/помешать решению?

ОБНОВЛЕНИЕ
Я попробовал свои силы в реализации того, что @Mikhail написал на Python, используя numpy, как рекомендовал @Thomas. Я чувствую, что алгоритм правильный, но он не работает так, как хотелось бы. (Код ниже.) Библиотека PNG: PyPNG.

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Возвращает, является ли (x, y) приблизительно белым пикселем.""" a = True для i в xrange(3): если не a: break a = image[coord[1]][coord[0] * 3 + i] > 240 возвращает определение bfs(s, e, i, посещено): """ Выполнить поиск в ширину. """ frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)]: np = tuple(map(operator.add, s, d)) если is_white(np, i) и np не в посещении: frontier.put(np) посетили.append(s) s = frontier.get() return посетили def main(): r = png.Reader(filename = "thescope-134.png") строки, столбцы, пиксели, мета = r.asDirect() assert meta["planes"] == 3 # убедитесь, что файл RGB image2d = numpy.vstack(itertools.imap(numpy.uint8, пикселей)) start, end = (402, 985), (398 , 27) напечатать bfs(start, end, image2d, [])