Representar y resolver un laberinto dada una imagen

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

¿Cuál es la mejor forma de representar y resolver un laberinto dada una imagen?

La imagen de portada de The Scope Issue 134

Dada una imagen JPEG (como se ve arriba), ¿cuál es la mejor manera de leerla, analizarla en alguna estructura de datos y resolver el laberinto? Mi primera el instinto es leer la imagen píxel por píxel y almacenarla en una lista (matriz) de valores booleanos: True para un píxel blanco y False para un píxel no blanco píxel (los colores se pueden descartar). El problema con este método es que la imagen puede no ser "píxel perfecta". Con eso simplemente quiero decir que si hay un píxel blanco en algún lugar de una pared, puede crear una ruta no deseada.

Otro método (que se me ocurrió después de pensarlo un poco) es convertir la imagen en un archivo SVG, que es una lista de rutas dibujadas en un lienzo. De esta manera, las rutas se pueden leer en el mismo tipo de lista (valores booleanos) donde True indica un camino o pared, False indicando un espacio transitable. Surge un problema con este método si la conversión no es 100 % precisa y no conecta completamente todas las paredes, creando espacios.

También un problema con la conversión a SVG es que las líneas no son "perfectamente " derecho. Esto da como resultado que los caminos sean curvas de Bezier cúbicas. Con una lista (matriz) de valores booleanos indexados por números enteros, las curvas no se transferirían fácilmente y todos los puntos que se alinean en la curva tendrían que calcularse, pero no coincidirían exactamente con los índices de la lista.

Supongo que si bien uno de estos métodos puede funcionar (aunque probablemente no) son lamentablemente ineficientes dada una imagen tan grande, y que existe una mejor manera. ¿Cómo es esto mejor (más eficiente y/o con la menor complejidad) ) hecho? ¿Hay incluso una mejor manera?

Luego viene la resolución del laberinto. Si uso cualquiera de los dos primeros métodos, esencialmente terminaré con una matriz. De acuerdo con esta respuesta, una buena forma de representar un laberinto es usando un árbol, y una buena forma de resolverlo es usando Algoritmo A*. ¿Cómo se crearía un árbol a partir de la imagen? ¿Alguna idea?

TL;DR
¿La mejor manera de analizar? ¿En qué da una estructura? ¿Cómo ayudaría o dificultaría dicha estructura la solución?

ACTUALIZAR
He intentado implementar lo que @Mikhail ha escrito en Python, usando numpy, como recomendó @Thomas. Siento que el algoritmo es correcto, pero no funciona como se esperaba. (Código a continuación). La biblioteca PNG es PyPNG.

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Devuelve si (x, y) es aproximadamente un píxel blanco.""" a = Verdadero para i en xrange(3): si no a: romper a = imagen[coord[1]][coord[0] * 3 + i] > 240 devuelve un def bfs(s, e, i, visited): """ Realiza una búsqueda en anchura. """ frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)]: np = tuple(map(operator.add, s, d)) si is_white(np, i) y np no están visitados: frontier.put(np) visitó.append(s) s = frontier.get() return visited def main(): r = png.Reader(filename = "thescope-134.png") filas, columnas, píxeles, meta = r.asDirect() afirmar meta["planos"] == 3 # asegurarse de que el archivo sea RGB image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels)) start, end = (402, 985), (398) , 27) imprimir bfs(inicio, fin, imagen2d, [])