Rappresentare e risolvere un labirinto data un’immagine

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

Qual è il modo migliore per rappresentare e risolvere un labirinto data un'immagine?

The immagine di copertina di The Scope Issue 134

Data un'immagine JPEG (come vista sopra), qual è il modo migliore per leggerla, analizzarla in una struttura dati e risolvere il labirinto? Il mio primo l'istinto è leggere l'immagine pixel per pixel e memorizzarla in un elenco (array) di valori booleani: True per un pixel bianco e False per un pixel non bianco pixel (i colori possono essere scartati).Il problema con questo metodo è che l'immagine potrebbe non essere "pixel perfetta".Con questo intendo semplicemente che se c'è un pixel bianco da qualche parte su un muro potrebbe creare un percorso non intenzionale.

Un altro metodo (che mi è venuto in mente dopo un po' di riflessione) è convertire l'immagine in un file SVG, che è un elenco di percorsi disegnati su una tela. In questo modo, i percorsi potrebbero essere letti in lo stesso tipo di elenco (valori booleani) dove True indica un percorso o un muro, False indicando uno spazio percorribile. Un problema con questo metodo sorge se la conversione non è accurata al 100% e non collega completamente tutti i muri, creando spazi vuoti.

Anche un problema con la conversione in SVG è che le linee non sono "perfettamente " dritto. Ciò fa sì che i percorsi siano curve di bezier cubiche. Con un elenco (array) di valori booleani indicizzati da numeri interi, le curve non verrebbero trasferite facilmente e tutti i punti della linea sulla curva dovrebbero essere calcolati, ma non corrisponderanno esattamente agli indici dell'elenco.

Presumo che mentre uno di questi metodi può funzionare (anche se probabilmente no) che siano tristemente inefficienti data un'immagine così grande e che esista un modo migliore.Come è questo il migliore (più efficiente e/o con la minor complessità ) fatto? C'è anche un modo migliore?

Poi arriva la risoluzione del labirinto. Se uso uno dei primi due metodi, essenzialmente finirò con una matrice. Secondo questa risposta, un buon modo per rappresentare un labirinto è usare un albero e un buon modo per risolverlo è usare Un algoritmo*. Come si crea un albero dall'immagine? Qualche idea?

TL;DR
Il modo migliore per analizzare? In quale da una struttura? In che modo detta struttura aiuterebbe/ostacolerebbe la risoluzione?

AGGIORNAMENTO
Ho provato a implementare ciò che @Mikhail ha scritto in Python, usando numpy, come consigliato da @Thomas. Sento che l'algoritmo è corretto, ma non funziona come sperato. (Codice sotto.) La libreria PNG è PyPNG.

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Restituisce se (x, y) è circa un pixel bianco.""" a = True for i in xrange(3): se non a: break a = image[coord[1]][coord[0] * 3 + i] > 240 return a def bfs(s, e, i, visiting): """ Esegue una ricerca in ampiezza. """ frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)]: np = tuple(map(operator.add, s, d)) if is_white(np, i) and np not in visiting: frontier.put(np) visiting.append(s) s = frontier.get() return visitato def main(): r = png.Reader(filename = "thescope-134.png") righe, colonne, pixel, meta = r.asDirect() assert meta["planes"] == 3 # assicurarsi che il file sia RGB image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels)) inizio, fine = (402, 985), (398 , 27) print bfs(inizio, fine, image2d, [])