Représenter et résoudre un labyrinthe donné une image

cette solution est écrite en Python. Merci Mikhail pour les conseils sur la préparation d'image.

une largeur animée-première recherche:

Le Labyrinthe Complété:

#!/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])

Note: marque un pixel blanc visité gris. Cela supprime le besoin d'une liste visitée, mais cela nécessite une seconde charge du fichier image du disque avant de dessiner un chemin (si vous ne voulez pas une image composite du chemin final et de tous les chemins pris).

Une version vierge du labyrinthe que j'ai utilisé.

j'ai essayé moi-même d'implémenter A-Star search pour ce problème. Suivi de près la mise en œuvre de Joseph Kern pour le cadre et le pseudo-code algorithme donné ici :

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 []

Comme l'Une des Étoiles est une heuristique de l'algorithme de recherche que vous devez venir avec une fonction qui estime le coût restant (ici: la distance) jusqu'à ce que l'objectif est atteint. À moins que vous ne soyez à l'aise avec une solution sous-optimale il devrait ne pas surestimer le coût. Un choix conservateur serait ici le manhattan (ou taxicab) distance car cela représente la ligne droite entre deux points sur la grille pour le quartier Von Neumann utilisé. (Qui, dans ce cas, ne jamais surestimer le coût.)

cela sous-estimerait cependant de manière significative le coût réel pour le labyrinthe donné en main. Par conséquent, j'ai ajouté deux autres mesures de distance au carré de la distance euclidienne et la distance de manhattan multipliée par quatre pour la comparaison. Toutefois, il se peut que ceux-ci surestiment le coût réel et donnent des résultats sous-optimaux.

voici le code:

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])

voici quelques images pour une visualisation des résultats (inspiré par celui posté par Joseph Kern ). Les animations montrent un nouveau cadre après 10000 itérations de la boucle while principale.

Largeur-Première Recherche:

Une Étoile Distance Manhattan:

Une Étoile Au Carré De La Distance Euclidienne:

Une Étoile Distance Manhattan multiplié par quatre:

les résultats montrent que Les régions explorées de l' labyrinthe diffèrent considérablement pour les heuristiques utilisées. En tant que telle, la distance euclidienne au carré produit même un chemin (sous-optimal) différent que les autres paramètres.

en ce qui concerne la performance de l'algorithme A-Star en termes d'exécution jusqu'à la fin, noter que beaucoup d'évaluation des fonctions de distance et de coût s'additionnent par rapport à la largeur-première recherche (BFS) qui n'a besoin d'évaluer que le "caractère objectif" de chaque poste candidat. Si oui ou non le coût de ces les évaluations de fonction supplémentaires (A-Star) l'emporte sur le coût pour le plus grand nombre de noeuds à vérifier (BFS) et surtout si oui ou non la performance est un problème pour votre application à tous, est une question de perception individuelle et ne peut bien sûr pas être généralement répondu.

une chose que peut peut être dit en général sur la question de savoir si oui ou non un algorithme de recherche informé (comme une étoile) pourrait être le meilleur choix par rapport à une recherche exhaustive (par exemple, BFS) est la suivante. Avec le nombre de dimensions du labyrinthe, c'est-à-dire le facteur de ramification de l'arbre de recherche, l'inconvénient d'une recherche exhaustive (pour une recherche exhaustive) croît exponentiellement. Avec la complexité croissante, il devient de moins en moins faisable de le faire et à un moment donné vous êtes assez heureux avec n'importe quel chemin de résultat, que ce soit (approximativement) optimal ou non.

la recherche D'arbres est trop. Le labyrinthe est intrinsèquement séparable le long du(DES) chemin (s) de solution.

(merci à rainman002 de la part de Reddit pour m'avoir fait remarquer cela.)

pour cette raison, vous pouvez rapidement utiliser composants connectés pour identifier les sections connectées du mur de labyrinthe. Cela itère sur les pixels deux fois.

Si vous voulez transformer en un joli diagramme de la solution path(s), vous pouvez ensuite utiliser des opérations binaires avec des éléments structurants pour remplir les chemins "sans issue" pour chaque région connectée.

code de démonstration pour MATLAB suit. Il pourrait utiliser ajustements pour nettoyer le meilleur résultat, le rendre plus généralisable, et le faire tourner plus vite. (Parfois quand il n'est pas 2h30 du matin.)

% 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);

Utilise une file d'attente pour un seuil de remplissage continu. Pousse le pixel gauche de l'entrée sur la file d'attente et commence la boucle. Si un pixel en file d'attente est assez sombre, il est gris clair (au-dessus du seuil), et tous les voisins sont poussés sur la file d'attente.

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")

Solution est le couloir entre le mur gris et le mur coloré. Remarque ce labyrinthe a plusieurs solutions. En outre, cela semble simplement fonctionner.

Ici, vous allez: labyrinthe-solveur-python (GitHub)

j'ai eu du plaisir à jouer avec CE et étendu sur Joseph Kern 'S réponse. Sans vouloir vous en détourner, je viens de faire quelques ajouts mineurs pour tous ceux qui pourraient être intéressés à jouer avec cela.

c'est un solveur basé sur python qui utilise BFS pour trouver le chemin le plus court. Mon principal les ajouts, à l'époque, sont:

1. l'image est nettoyée avant la recherche (c.-à-d. convertir en noir et blanc pur)
2. génère automatiquement un GIF.
3. génère automatiquement un AVI.

en l'état, les points de départ et d'arrivée sont codés en dur pour ce labyrinthe d'échantillon, mais je prévois de l'étendre pour que vous puissiez choisir les pixels appropriés.

j'opterais pour l'option matrix-of-bools. Si vous trouvez que les listes Python standard sont trop inefficaces pour cela, vous pouvez utiliser un tableau numpy.bool à la place. Le stockage pour un labyrinthe de 1000x1000 Pixels est alors seulement 1 Mo.

ne vous donnez pas la peine de créer des structures de données arborescentes ou graphiques. C'est juste une façon de penser, mais pas nécessairement une bonne façon de le représenter dans la mémoire; une matrice booléenne est à la fois plus facile à coder et plus efficace.

Alors utilisez l'algorithme A* pour le résoudre. Pour la distance heuristique, utilisez la distance de Manhattan ( distance_x + distance_y ).

représente les noeuds par un tuple de (row, column) coordonnées. Chaque fois que l'algorithme ( Wikipedia pseudocode ) appelle des "voisins", c'est une simple question de boucler au-dessus des quatre voisins possibles (attention aux bords de l'image!).

si vous trouvez qu'il est encore trop lent, vous pouvez essayer de réduire l'échelle de l'image avant vous le chargez. Attention à ne pas perdre les chemins étroits dans le processus.

peut-être qu'il est possible de faire une réduction d'échelle de 1:2 en Python aussi, en vérifiant que vous ne perdez pas de chemins possibles. Une option intéressante, mais qui nécessite un peu plus de réflexion.

Voici quelques idées.

(1. Traitement D'Image:)

1.1 charger l'image comme RGB carte de pixel. Dans C# il est trivial à l'aide de system.drawing.bitmap . Dans les langages sans support simple pour l'imagerie, il suffit de convertir l'image en format portable pixmap (PPM) (une représentation de texte Unix, produit de grands fichiers) ou un format de fichier binaire simple que vous pouvez facilement lire, tels que BMP ou TGA . ImageMagick en Unix ou IrfanView dans Windows.

1.2 vous pouvez, comme mentionné plus haut, simplifier les données en prenant le (R+G+B)/3 pour chaque pixel comme indicateur de tonalité grise, puis le seuil de la valeur pour produire un tableau noir et blanc. Quelque chose proche de 200 en supposant que 0 = Noir et 255 = blanc éliminera les artéfacts JPEG.

(2. Solutions:)

2.1 profondeur-première recherche: Init une pile vide avec l'emplacement de départ, recueillir des mouvements de suivi disponibles, en choisir un au hasard et pousser sur la pile, procéder jusqu'à ce que la fin est atteinte ou un point mort. Sur deadend backtrack en sautant la pile, vous devez garder une trace des positions qui ont été visitées sur la carte afin que lorsque vous recueillez des mouvements disponibles vous ne prenez jamais le même chemin deux fois. Très intéressant à animer.

2.2 Largeur-Première Recherche: Mentionné avant, comme ci-dessus mais en utilisant uniquement les files d'attente. Aussi intéressant à animer. Cela fonctionne comme le flood-fill dans le logiciel d'édition d'image. Je pense que vous pourriez être en mesure de résoudre un labyrinthe dans Photoshop en utilisant ce truc.

2.3 suiveur de paroi: géométriquement parlant, un labyrinthe est un tube plié/convoluté. Si vous gardez votre main sur le mur, vous finirez par trouver la sortie ;) Cela ne fonctionne pas toujours. Il y a certaines suppositions re: labyrinthe parfait, etc. par exemple, certains labyrinthes contiennent des îles. Faire le chercher; c'est fascinant.

(3. Commentaires:)

c'est le plus délicat. Il est facile de résoudre des labyrinthes s'ils sont représentés dans un tableau simple formel avec chaque élément étant un type de cellule avec des murs Nord, Est, Sud et ouest et un champ de drapeau visité. Cependant, étant donné que vous essayez de le faire étant donné un dessin dessiné à la main il devient désordre. Honnêtement, je pense qu'essayer de rationaliser l'esquisse vous conduira fou. Ceci est similaire à la problèmes de vision par ordinateur qui sont assez impliqués. Peut-être que le fait d'aller directement sur la carte d'image peut être plus facile mais plus coûteux.

Voici une solution en utilisant 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)

RVB en niveaux de gris, voir: 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")

voilà!

C'est ce qui arrive si vous ne remplissez pas quelques pixels de bordure (Ha!)...

divulgation complète: j'ai demandé et répondu à une très question similaire moi-même avant de trouver celui-ci. Puis, grâce à la magie de SO, trouvé celui-ci comme l'un des principaux "questions connexes". Je pensais utiliser ce labyrinthe comme un test supplémentaire... J'ai été très heureux de constater que ma réponse fonctionne également pour cette application avec très peu de modifications.