Przedstawianie i rozwiązywanie labiryntu z obrazem

To rozwiązanie jest napisane w Pythonie. Dzięki Mikhail za wskazówki dotyczące przygotowania obrazu.

Animowana Szerokość - pierwsze wyszukiwanie:

Ukończony Labirynt:

#!/usr/bin/env python

import sys

from Queue import Queue
from PIL import Image

start = (400,984)
end = (398,25)

def iswhite(value):
    if value == (255,255,255):
        return True

def getadjacent(n):
    x,y = n
    return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]

def BFS(start, end, pixels):

    queue = Queue()
    queue.put([start]) # Wrapping the start tuple in a list

    while not queue.empty():

        path = queue.get() 
        pixel = path[-1]

        if pixel == end:
            return path

        for adjacent in getadjacent(pixel):
            x,y = adjacent
            if iswhite(pixels[x,y]):
                pixels[x,y] = (127,127,127) # see note
                new_path = list(path)
                new_path.append(adjacent)
                queue.put(new_path)

    print "Queue has been exhausted. No answer was found."


if __name__ == '__main__':

    # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]
    base_img = Image.open(sys.argv[1])
    base_pixels = base_img.load()

    path = BFS(start, end, base_pixels)

    path_img = Image.open(sys.argv[1])
    path_pixels = path_img.load()

    for position in path:
        x,y = position
        path_pixels[x,y] = (255,0,0) # red

    path_img.save(sys.argv[2])

Uwaga: oznacza biały piksel szary. Usuwa to potrzebę odwiedzanej listy, ale wymaga to drugiego załadowania pliku obrazu z dysku przed narysowaniem ścieżki (jeśli nie chcesz mieć obrazu kompozytowego ścieżki końcowej i wszystkich ścieżek taken).

Pusta wersja Labiryntu, którego użyłem.

Próbowałem sobie zaimplementować A-Star search dla tego problemu. Po implementacji przez Josepha Kerna dla frameworka i pseudokodu algorytmu podanego TUTAJ :

def AStar(start, goal, neighbor_nodes, distance, cost_estimate):
    def reconstruct_path(came_from, current_node):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = came_from[current_node]
        return list(reversed(path))

    g_score = {start: 0}
    f_score = {start: g_score[start] + cost_estimate(start, goal)}
    openset = {start}
    closedset = set()
    came_from = {start: None}

    while openset:
        current = min(openset, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, goal)
        openset.remove(current)
        closedset.add(current)
        for neighbor in neighbor_nodes(current):
            if neighbor in closedset:
                continue
            if neighbor not in openset:
                openset.add(neighbor)
            tentative_g_score = g_score[current] + distance(current, neighbor)
            if tentative_g_score >= g_score.get(neighbor, float('inf')):
                continue
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal)
    return []

Ponieważ gwiazda jest heurystycznym algorytmem wyszukiwania, musisz wymyślić funkcję, która oszacowuje pozostały koszt (tutaj: odległość), aż do osiągnięcia celu. Jeśli nie czujesz się komfortowo z nieoptymalnym rozwiązaniem, nie powinieneś przeceniać kosztów. Konserwatywnym wyborem byłoby odległość Manhattanu (lub taksówki) , ponieważ reprezentuje to odległość w linii prostej między dwoma punktami na siatce dla używanego sąsiedztwa Von Neumanna. (Co w tym przypadku nigdy nie przeceniałoby kosztów.)

Oto kod:

import sys
from PIL import Image

def is_blocked(p):
    x,y = p
    pixel = path_pixels[x,y]
    if any(c < 225 for c in pixel):
        return True
def von_neumann_neighbors(p):
    x, y = p
    neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
    return [p for p in neighbors if not is_blocked(p)]
def manhattan(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def squared_euclidean(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2

start = (400, 984)
goal = (398, 25)

# invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]

path_img = Image.open(sys.argv[1])
path_pixels = path_img.load()

distance = manhattan
heuristic = manhattan

path = AStar(start, goal, von_neumann_neighbors, distance, heuristic)

for position in path:
    x,y = position
    path_pixels[x,y] = (255,0,0) # red

path_img.save(sys.argv[2])

Oto kilka zdjęć do wizualizacji wyników (zainspirowanych tym opublikowanym przez Josepha Kerna ). Animacje pokazują nową klatkę po 10000 iteracji głównej pętli while.

Szerokość-Pierwsze Wyszukiwanie:

A-Gwiazdka Odległość:

A-Gwiazda Kwadratowa Odległości Euklidesowej:

Wyniki pokazują, że badane regiony labiryntu różnią się znacznie pod względem heurystyki. Jako taka kwadratowa odległość euklidesowa tworzy nawet inną (nieoptymalną) ścieżkę, jak inne metryki.

Jeśli chodzi o wydajność algorytmu A-Star pod względem czasu trwania do zakończenia, zauważ, że wiele funkcji oceny odległości i kosztów sumuje się w porównaniu z wyszukiwaniem Szerokościowym (BFS), które wymaga tylko aby ocenić "celowość" każdego stanowiska kandydata. To, czy koszt tych dodatkowych ocen funkcji (a-Star) przewyższa koszt większej liczby węzłów do sprawdzenia (BFS), a zwłaszcza to, czy wydajność jest problemem dla Twojej aplikacji, jest kwestią indywidualnego postrzegania i oczywiście nie można ogólnie odpowiedzieć.

Rzecz, którą można powiedzieć ogólnie o tym, czy świadomy algorytm wyszukiwania (taki jak A-Star) może być lepszy wybór w porównaniu do wyczerpującego wyszukiwania (NP BFS) jest następujący. Wraz z liczbą wymiarów labiryntu, tj. czynnikiem rozgałęzienia drzewa wyszukiwania, wada wyczerpującego wyszukiwania (wyszukiwania wyczerpującego) rośnie wykładniczo. Wraz z rosnącą złożonością staje się to coraz mniej wykonalne i w pewnym momencie jesteś prawie zadowolony z dowolnej ścieżki wyniku, czy to (w przybliżeniu) optymalnej, czy nie.

/ Align = "left" / Labirynt jest z natury rozdzielny wzdłuż ścieżki (ścieżek) rozwiązania.

(podziękowania dla rainman002 od Reddita za wskazanie mi tego.)

Dzięki temu możesz szybko użyć połączonych komponentów do identyfikacji połączonych odcinków ściany labiryntu. To iteruje na pikselach dwa razy.

Jeśli chcesz przekształcić to w ładny diagram ścieżki (ścieżek) rozwiązania, możesz użyć operacji binarnych z elementami strukturyzującymi do wypełnienia "ślepy zaułek" ścieżki dla każdego połączonego regionu.

Kod Demo dla MATLAB następuje. Może użyć ulepszenia, aby lepiej wyczyścić wynik, uczynić go bardziej uogólnialnym i przyspieszyć jego działanie. (Czasami, gdy nie jest 2: 30 rano.)

% read in and invert the image
im = 255 - imread('maze.jpg');

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count < 500
        result(result==i) = 0;
    end
end

% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
    k = zeros(1002,800);
    k(result==i) = 1; k = imclose(k,strel('square',8));
    closed(k==1) = i;
end

% do output
out = 255 - im;
for x = 1:1002
    for y = 1:800
        if closed(x,y) == 0
            out(x,y,:) = 0;
        end
    end
end
imshow(out);

Używa kolejki do ciągłego wypełnienia progu. Przesuwa piksel po lewej stronie wejścia na kolejkę, a następnie uruchamia pętlę. Jeśli piksel w kolejce jest wystarczająco ciemny, ma kolor jasnoszary (powyżej progu), a wszyscy sąsiedzi są popychani do kolejki.

from PIL import Image
img = Image.open("/tmp/in.jpg")
(w,h) = img.size
scan = [(394,23)]
while(len(scan) > 0):
    (i,j) = scan.pop()
    (r,g,b) = img.getpixel((i,j))
    if(r*g*b < 9000000):
        img.putpixel((i,j),(210,210,210))
        for x in [i-1,i,i+1]:
            for y in [j-1,j,j+1]:
                scan.append((x,y))
img.save("/tmp/out.png")

Rozwiązaniem jest korytarz pomiędzy szarą ścianą a kolorową ścianą. Uwaga ten labirynt ma wiele rozwiązań. Ponadto, to tylko wydaje się działać.

Proszę bardzo: maze-solver-python (GitHub)

Bawiłem się tym i rozszerzałem naodpowiedź Josepha Kerna . Nie umniejszając tego; zrobiłem tylko kilka drobnych dodatków dla każdego, kto może być zainteresowany pobawieniem się tym.

Jest to rozwiązywacz Pythona, który używa BFS, aby znaleźć najkrótszą ścieżkę. Moje główne dodatki, w tym czasie, to:

1. obraz jest czyszczony przed wyszukiwaniem (np. Konwertuj na czystą czerń & biały)
2. automatycznie generuje GIF.
3. automatycznie generuje AVI.

W obecnym stanie punkty początkowe/końcowe są mocno zakodowane dla tego przykładowego labiryntu, ale planuję go rozszerzyć tak, aby można było wybrać odpowiednie piksele.

Wybrałbym opcję matrix-of-bools. Jeśli okaże się, że standardowe listy Pythona są na to zbyt nieefektywne, możesz użyć tablicy numpy.bool. Miejsce na labirynt 1000x1000 pikseli to wtedy tylko 1 MB.

Nie trudź się tworzeniem żadnych struktur danych drzewa lub wykresu. To tylko sposób myślenia o tym, ale niekoniecznie dobry sposób na reprezentowanie go w pamięci; macierz logiczna jest zarówno łatwiejsza w kodowaniu, jak i bardziej wydajna.

Następnie użyj algorytmu a*, aby go rozwiązać. Na heurystyka odległości, użyj odległości Manhattanu (distance_x + distance_y).

Reprezentuj węzły przez krotkę współrzędnych (row, column). Ilekroć algorytm (Pseudokod Wikipedii ) wzywa do "sąsiadów", jest to prosta sprawa zapętlenia czterech możliwych sąsiadów (uwaga na krawędzie obrazu!).

Jeśli okaże się, że nadal jest zbyt wolny, Możesz spróbować zmniejszyć skalowanie obrazu przed załadowaniem go. Uważaj, aby nie stracić żadnych wąskich ścieżek w procesie.

Może da się zrobić 1: 2 downscaling w Pythonie, jak również, sprawdzanie, czy nie rzeczywiście stracić żadnych możliwych ścieżek. Ciekawa opcja, ale wymaga trochę więcej przemyśleń.

Oto kilka pomysłów.

(1. Obróbka Zdjęć:)

1.1 Załaduj obraz jako RGB Mapa pikseli. W C # jest trywialne użycie system.drawing.bitmap. W językach bez prostego wsparcia dla obrazowania, wystarczy przekonwertować obraz do portable pixmap format (PPM) (Unix tekst reprezentacji, tworzy duże pliki) lub jakiś prosty binarny format pliku można łatwo odczytać, takie jak BMP lub TGA. ImageMagick in Unix or IrfanView in Okna.

1.2 Możesz, jak wspomniano wcześniej, uprościć dane, przyjmując (R + G + B) / 3 dla każdego piksela jako wskaźnik odcienia szarości, a następnie próg wartości, aby utworzyć czarno-białą tabelę. Coś blisko 200 zakładając, że 0 = czarny i 255=biały usunie artefakty JPEG.

(2. Rozwiązania:)

2.1 głębia - pierwsze wyszukiwanie: Init pusty stos z miejscem startu, Zbierz dostępne kolejne ruchy, wybierz jeden losowo i wciśnij na stos, Kontynuuj do końca / align = "left" / W deadend backtrack klikając stos, musisz śledzić, które pozycje były odwiedzane na mapie, więc kiedy zbierasz dostępne ruchy, nigdy nie obierasz tej samej ścieżki dwa razy. Bardzo interesujące animować.

2.2 Szerokość - pierwsze wyszukiwanie: wspomniane wcześniej, podobne jak wyżej, ale tylko za pomocą kolejek. Również interesujące do animacji. Działa to jak flood-fill w oprogramowaniu do edycji obrazów. Myślę, że możesz być w stanie rozwiązać labirynt w Photoshopie za pomocą tej sztuczki.

2.3 Wall Follower: geometrycznie rzecz biorąc, labirynt jest złożoną / zwiniętą rurą. Jeśli trzymasz rękę na ścianie, w końcu znajdziesz wyjście ;) to nie zawsze działa. Istnieją pewne założenia re: labirynty doskonałe, itp. na przykład niektóre labirynty zawierają Wyspy. To fascynujące.

(3. Komentarze:)

Oto rozwiązanie za pomocą R.

### download the image, read it into R, converting to something we can play with...
library(jpeg)
url <- "https://i.stack.imgur.com/TqKCM.jpg"
download.file(url, "./maze.jpg", mode = "wb")
jpg <- readJPEG("./maze.jpg")

### reshape array into data.frame
library(reshape2)
img3 <- melt(jpg, varnames = c("y","x","rgb"))
img3$rgb <- as.character(factor(img3$rgb, levels = c(1,2,3), labels=c("r","g","b")))

## split out rgb values into separate columns
img3 <- dcast(img3, x + y ~ rgb)

RGB do skali szarości, patrz: https://stackoverflow.com/a/27491947/2371031

# convert rgb to greyscale (0, 1)
img3$v <- img3$r*.21 + img3$g*.72 + img3$b*.07
# v: values closer to 1 are white, closer to 0 are black

## strategically fill in some border pixels so the solver doesn't "go around":
img3$v2 <- img3$v
img3[(img3$x == 300 | img3$x == 500) & (img3$y %in% c(0:23,988:1002)),"v2"]  = 0

# define some start/end point coordinates
pts_df <- data.frame(x = c(398, 399),
                     y = c(985, 26))

# set a reference value as the mean of the start and end point greyscale "v"s
ref_val <- mean(c(subset(img3, x==pts_df[1,1] & y==pts_df[1,2])$v,
                  subset(img3, x==pts_df[2,1] & y==pts_df[2,2])$v))

library(sp)
library(gdistance)
spdf3 <- SpatialPixelsDataFrame(points = img3[c("x","y")], data = img3["v2"])
r3 <- rasterFromXYZ(spdf3)

# transition layer defines a "conductance" function between any two points, and the number of connections (4 = Manhatten distances)
# x in the function represents the greyscale values ("v2") of two adjacent points (pixels), i.e., = (x1$v2, x2$v2)
# make function(x) encourages transitions between cells with small changes in greyscale compared to the reference values, such that: 
# when v2 is closer to 0 (black) = poor conductance
# when v2 is closer to 1 (white) = good conductance
tl3 <- transition(r3, function(x) (1/max( abs( (x/ref_val)-1 ) )^2)-1, 4) 

## get the shortest path between start, end points
sPath3 <- shortestPath(tl3, as.numeric(pts_df[1,]), as.numeric(pts_df[2,]), output = "SpatialLines")

## fortify for ggplot
sldf3 <- fortify(SpatialLinesDataFrame(sPath3, data = data.frame(ID = 1)))

# plot the image greyscale with start/end points (red) and shortest path (green)
ggplot(img3) +
  geom_raster(aes(x, y, fill=v2)) +
  scale_fill_continuous(high="white", low="black") +
  scale_y_reverse() +
  geom_point(data=pts_df, aes(x, y), color="red") +
  geom_path(data=sldf3, aes(x=long, y=lat), color="green")

Tak się dzieje, jeśli nie wypełnisz niektórych pikseli ramek (Ha!)...

Pełne ujawnienie: zadałem i odpowiedziałem na bardzo {23]} podobne pytanie sam, zanim znalazłem to. Następnie dzięki magii tak, znalazłem ten jako jeden z najlepszych "powiązanych pytań". Pomyślałem, że wykorzystam ten labirynt jako dodatkowy test... Byłem bardzo zadowolony, że moja odpowiedź działa również w tej aplikacji z bardzo małą modyfikacją.