Reprezentowanie i rozwiązywanie labiryntu na podstawie obrazu

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

Jaki jest najlepszy sposób na przedstawienie i rozwiązanie labiryntu na podstawie obrazu?

The obraz okładki The Scope Issue 134

Biorąc pod uwagę obraz JPEG (jak widać powyżej), w jaki sposób najlepiej go odczytać, przeanalizować w jakąś strukturę danych i rozwiązać labirynt? Mój pierwszy instynkt polega na odczytywaniu obrazu piksel po pikselu i przechowywaniu go na liście (tablicy) wartości logicznych: True dla białego piksela i False dla niebiałego piksel (kolory można odrzucić).Problem związany z tą metodą polega na tym, że obraz może nie być „pikselowy doskonały”. Rozumiem przez to po prostu, że jeśli gdzieś na ścianie znajduje się biały piksel, może on utworzyć niezamierzoną ścieżkę.

Inną metodą (która przyszła mi do głowy po krótkim namyśle) jest przekonwertowanie obrazu do pliku SVG – czyli listy ścieżek narysowanych na płótnie. ten sam rodzaj listy (wartości logiczne), gdzie True wskazuje ścieżkę lub ścianę, False wskazując przestrzeń zdolną do podróżowania. Problem z tą metodą pojawia się, jeśli konwersja nie jest w 100% dokładna i nie łączy w pełni wszystkich ścian, tworząc luki.

Również problem z konwersją do SVG polega na tym, że linie nie są „doskonale” " proste. Powoduje to, że ścieżki są sześciennymi krzywymi Beziera. Z listą (tablicą) wartości logicznych indeksowanych liczbami całkowitymi, krzywe nie byłyby łatwo przenoszone, a wszystkie punkty tej linii na krzywej musiałyby zostać obliczone, ale nie będą dokładnie pasować do indeksów listy.

Zakładam, że chociaż jedna z tych metod może działać (choć prawdopodobnie nie), to są one żałośnie nieefektywne przy tak dużym obrazie i że istnieje lepszy sposób. ) zrobione? Czy jest w ogóle najlepszy sposób?

Wtedy przychodzi rozwiązanie labiryntu. Jeśli użyję jednej z dwóch pierwszych metod, zasadniczo otrzymam macierz. Według ta odpowiedź, dobrym sposobem na przedstawienie labiryntu jest użycie drzewa, a dobrym sposobem na jego rozwiązanie jest użycie Algorytm A*. Jak utworzyć drzewo z obrazu? Jakieś pomysły?

TL;DR
Najlepszy sposób na parsowanie? ta struktura? Jak wspomniana struktura pomoże/utrudni rozwiązywanie problemów?

AKTUALIZACJA
Próbowałem swoich sił we wdrażaniu tego, co @Mikhail napisał w Pythonie, używając numpy, zgodnie z zaleceniami @Thomas.Czuję, że algorytm jest poprawny, ale nie działa zgodnie z oczekiwaniami. (Kod poniżej.) Biblioteka PNG to PyPNG.

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Zwraca, czy (x, y) to w przybliżeniu biały piksel.""" a = True for i in xrange(3): jeśli nie a: przerwa a = image[coord[1]][coord[0] * 3 + i] > 240 zwraca def bfs(s, e, i, odwiedzone): """ Wykonaj wyszukiwanie wszerz. """ frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)]: np = krotka(map(operator.add, s, d)) if is_white(np, i) i np not in visit: frontier.put(np) odwiedzono.append(s) s = frontier.get() return odwiedzono def main(): r = png.Reader(nazwa pliku = "thescope-134.png") wiersze, kolumny, piksele, meta = r.asDirect() attach meta["planes"] == 3 # upewnij się, że plik to RGB image2d = numpy.vstack(itertools.imap(numpy.uint8, piksele)) start, end = (402, 985), (398 , 27) print bfs(start, end, image2d, [])