[Python] Représenter et résoudre un labyrinthe donné par une image


Answers

Cette solution est écrite en Python. Merci Mikhail pour les conseils sur la préparation de l'image.

Une recherche animée-première:

Le labyrinthe terminé:

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

Remarque: Marque un pixel visité blanc gris. Cela supprime le besoin d'une liste visitée, mais cela nécessite un deuxième chargement du fichier image à partir du disque avant de dessiner un chemin (si vous ne voulez pas une image composite du chemin final et TOUS les chemins empruntés).

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

Question

Quelle est la meilleure façon de représenter et de résoudre un labyrinthe donné par une image?

Étant donné une image JPEG (comme vu ci-dessus), quelle est la meilleure façon de le lire, l'analyser dans une structure de données et de résoudre le labyrinthe? Mon premier instinct est de lire l'image pixel par pixel et de la stocker dans une liste de valeurs booléennes: True pour un pixel blanc et False pour un pixel non blanc (les couleurs peuvent être ignorées). Le problème avec cette méthode, c'est que l'image ne peut pas être "pixel parfait". Par là, je veux simplement dire que s'il y a un pixel blanc quelque part sur un mur, cela peut créer un chemin involontaire.

Une autre méthode (qui m'est venue après un peu de réflexion) est de convertir l'image en un fichier SVG - qui est une liste de chemins dessinés sur une toile. De cette façon, les chemins pourraient être lus dans le même type de liste (valeurs booléennes) où True indique un chemin ou un mur, False indiquant un espace pouvant être parcouru. Un problème avec cette méthode se pose si la conversion n'est pas précise à 100% et ne connecte pas complètement tous les murs, créant ainsi des lacunes.

Un problème avec la conversion en SVG est que les lignes ne sont pas "parfaitement" droites. Il en résulte que les chemins sont des courbes bezier cubiques. Avec une liste (tableau) de valeurs booléennes indexées par des entiers, les courbes ne seraient pas facilement transférées, et tous les points de la courbe devraient être calculés, mais ne correspondraient pas exactement aux indices de la liste.

Je suppose que, bien que l'une de ces méthodes puisse fonctionner (mais probablement pas), elles sont terriblement inefficaces étant donné une image aussi grande, et qu'il existe une meilleure façon de procéder. Comment cela se passe-t-il le mieux (le plus efficacement et / ou avec le moins de complexité)? Y a-t-il même un meilleur moyen?

Puis vient la résolution du labyrinthe. Si j'utilise l'une des deux premières méthodes, je finirai essentiellement par une matrice. Selon cette réponse , un bon moyen de représenter un labyrinthe est d'utiliser un arbre, et un bon moyen de le résoudre est d'utiliser l' algorithme A * . Comment créer un arbre à partir de l'image? Des idées?

TL; DR
La meilleure façon d'analyser? Dans quelle structure de données? Comment cette structure pourrait-elle aider / empêcher la résolution?

METTRE À JOUR
J'ai essayé de mettre en œuvre ce que @Mikhail a écrit en Python, en utilisant numpy , comme recommandé par @Thomas. Je pense que l'algorithme est correct, mais ça ne fonctionne pas comme espéré. (Code ci-dessous.) La bibliothèque PNG est PyPNG .

import png, numpy, Queue, operator, itertools

def is_white(coord, image):
  """ Returns whether (x, y) is approx. a white pixel."""
  a = True
  for i in xrange(3):
    if not a: break
    a = image[coord[1]][coord[0] * 3 + i] > 240
  return a

def bfs(s, e, i, visited):
  """ Perform a breadth-first search. """
  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 visited:
        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 # ensure the file is RGB
  image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
  start, end = (402, 985), (398, 27)
  print bfs(start, end, image2d, [])



Voici quelques idées.

(1. Traitement d'image :)

1.1 Charger l'image en tant que carte de pixel RGB . En C# il est trivial d'utiliser system.drawing.bitmap . Dans les langues sans support simple pour l'imagerie, il suffit de convertir l'image en format portable pixmap (PPM) (une représentation de texte Unix, produit des fichiers volumineux) ou un format de fichier binaire simple, comme BMP ou TGA . ImageMagick dans Unix ou IrfanView dans Windows.

1.2 Vous pouvez, comme mentionné précédemment, simplifier les données en prenant le (R + G + B) / 3 pour chaque pixel comme un indicateur de tonalité de gris et ensuite de définir la valeur pour produire une table en noir et blanc. Quelque chose près de 200 en supposant que 0 = noir et 255 = blanc supprimera les artefacts JPEG.

(2. Solutions :)

2.1 Depth-First Search: Init une pile vide avec l'emplacement de départ, collecter les mouvements de suivi disponibles, en choisir un au hasard et pousser sur la pile, continuer jusqu'à la fin ou un deadend. Sur backtrack deadend en faisant sauter la pile, vous devez garder une trace des positions qui ont été visitées sur la carte de sorte que lorsque vous collectez des mouvements disponibles, vous ne prenez jamais le même chemin deux fois. Très intéressant à animer.

2.2 Breadth-First Search: Mentionné avant, semblable à ci-dessus mais utilisant uniquement des files d'attente. Aussi intéressant à animer. Cela fonctionne comme une inondation dans un logiciel de retouche d'image. Je pense que vous pourriez être capable de résoudre un labyrinthe dans Photoshop en utilisant cette astuce.

2.3 Suiveur de mur: 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 hypothèses sur des labyrinthes parfaits, etc., par exemple, certains labyrinthes contiennent des îles. Regardez-le. c'est fascinant.

(3. Commentaires :)

C'est le délicat. Il est facile de résoudre des labyrinthes si 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 croquis dessiné à la main, il devient salissant. Je pense sincèrement qu'essayer de rationaliser le croquis vous rendra fou. Cela ressemble à des problèmes de vision par ordinateur qui sont assez impliqués. Peut-être aller directement sur la carte d'image peut-être plus facile encore plus de gaspillage.




Vous voilà: maze-solver-python (GitHub)

Je me suis amusé à jouer avec ça et je me suis étendu sur la réponse de Joseph Kern . Ne pas en porter atteinte; Je viens de faire quelques ajouts mineurs pour tous ceux qui pourraient être intéressés à jouer avec ça.

C'est un solveur basé sur python qui utilise BFS pour trouver le chemin le plus court. Mes principaux ajouts, à l'époque, sont:

  1. L'image est nettoyée avant la recherche (conversion en noir et blanc pur)
  2. Génère automatiquement un GIF.
  3. Générer automatiquement un AVI.

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




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

(Merci à rainman002 de Reddit pour rainman002 signalé cela.)

Pour cette raison, vous pouvez utiliser rapidement les composants connectés pour identifier les sections connectées de la paroi du labyrinthe. Cela se répète deux fois sur les pixels.

Si vous souhaitez transformer cela en un diagramme symétrique du ou des chemins de la solution, 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.

Le code démo pour MATLAB suit. Il pourrait être utile de peaufiner le résultat, de le rendre plus généralisable et de le faire fonctionner plus rapidement. (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);




Links