Darstellen und Lösen eines Labyrinths mit einem gegebenen Bild

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

Was ist der beste Weg, ein Labyrinth mit einem Bild darzustellen und zu lösen?

The Titelbild von The Scope Issue 134

Was ist der beste Weg, ein gegebenes JPEG-Bild (wie oben zu sehen) einzulesen, es in eine Datenstruktur zu parsen und das Labyrinth zu lösen? Meine erste Der Instinkt besteht darin, das Bild Pixel für Pixel zu lesen und es in einer Liste (Array) von booleschen Werten zu speichern: True für ein weißes Pixel und False für ein nicht weißes Pixel (die Farben können verworfen werden).Das Problem bei dieser Methode ist, dass das Bild möglicherweise nicht "pixelperfekt" ist.Damit meine ich einfach, dass ein weißes Pixel irgendwo an einer Wand einen unbeabsichtigten Pfad erzeugen kann.

Eine andere Methode (die mir nach einigem Nachdenken eingefallen ist) besteht darin, das Bild in eine SVG-Datei umzuwandeln - das ist eine Liste von Pfaden, die auf eine Leinwand gezeichnet wurden.Auf diese Weise könnten die Pfade eingelesen werden die gleiche Art von Liste (boolesche Werte), wobei True einen Pfad oder eine Wand anzeigt, False zeigt einen befahrbaren Raum an. Ein Problem bei dieser Methode tritt auf, wenn die Konvertierung nicht 100 % genau ist und nicht alle Wände vollständig verbindet, wodurch Lücken entstehen.

Ein weiteres Problem bei der Konvertierung in SVG ist, dass die Linien nicht "perfekt" sind " gerade. Dies führt dazu, dass die Pfade kubische Bezierkurven sind. Mit einer Liste (Array) von booleschen Werten, die durch Ganzzahlen indiziert sind, würden die Kurven nicht einfach übertragen, und alle Punkte, die auf der Kurve liegen, müssten berechnet werden, stimmen aber nicht genau mit den Listenindizes überein.

Ich gehe davon aus, dass eine dieser Methoden zwar funktioniert (wenn auch wahrscheinlich nicht), dass sie angesichts eines so großen Bildes jedoch erschreckend ineffizient ist und dass es einen besseren Weg gibt. Wie ist dies am besten (am effizientesten und / oder mit der geringsten Komplexität?). ) fertig? Gibt es überhaupt einen besten Weg?

Dann kommt das Lösen des Labyrinths. Wenn ich eine der ersten beiden Methoden verwende, erhalte ich im Wesentlichen eine Matrix. Gemäß diese Antwort, eine gute Möglichkeit, ein Labyrinth darzustellen, ist die Verwendung eines Baums, und eine gute Möglichkeit, es zu lösen, ist die Verwendung von A*-Algorithmus. Wie würde man aus dem Bild einen Baum erstellen? Irgendwelche Ideen?

TL;DR
Der beste Weg zum Parsen? In was da eine Struktur? Wie würde diese Struktur beim Lösen helfen/hindern?

UPDATE
Ich habe versucht, das zu implementieren, was @Mikhail in Python geschrieben hat, indem ich numpy, wie von @Thomas empfohlen. Ich habe das Gefühl, dass der Algorithmus korrekt ist, aber er funktioniert nicht wie erhofft. (Code unten.) Die PNG-Bibliothek ist PyPNG.

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Gibt zurück, ob (x, y) ungefähr ein weißes Pixel ist.""" a = True for i in xrange(3): wenn nicht a: break a = image[coord[1]][coord[0] * 3 + i] > 240 gib a def bfs(s, e, i, visited) zurück: """ Führe eine Breitensuche durch. """ 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) und np nicht in besucht: frontier.put(np) visited.append(s) s = frontier.get() return visited def main(): r = png.Reader(filename = "thescope-134.png") rows, cols, pixels, meta = r.asDirect() assert meta["planes"] == 3 # sicherstellen, dass die Datei RGB ist image2d = numpy.vstack(itertools.imap(numpy.uint8, Pixel)) start, end = (402, 985), (398 , 27) print bfs(start, end, image2d, [])