Saltar al contenido

Representar y resolver un laberinto dada una imagen

Hola, descubrimos la solución a lo que necesitas, desplázate y la obtendrás aquí.

Solución:

He aquí una solución.

  1. Convierta la imagen a escala de grises (aún no binaria), ajustando los pesos de los colores para que la imagen final en escala de grises sea aproximadamente uniforme. Puede hacerlo simplemente controlando los controles deslizantes en Photoshop en Imagen -> Ajustes -> Blanco y negro.
  2. Convierta la imagen en binario estableciendo el umbral apropiado en Photoshop en Imagen -> Ajustes -> Umbral.
  3. Asegúrese de que el umbral esté seleccionado correctamente. Utilice la herramienta Varita mágica con tolerancia 0, muestra puntual, contigua, sin suavizado. Compruebe que los bordes en los que los saltos de selección no estén false bordes introducidos por umbral incorrecto. De hecho, todos los puntos interiores de este laberinto son accesibles desde el principio.
  4. Agregue bordes artificiales en el laberinto para asegurarse de que el viajero virtual no camine alrededor de él 🙂
  5. Implemente la búsqueda en amplitud (BFS) en su idioma favorito y ejecútela desde el principio. Prefiero MATLAB para esta tarea. Como ya mencionó @Thomas, no hay necesidad de meterse con la representación regular de los gráficos. Puede trabajar con imágenes binarizadas directamente.

Aquí está el código MATLAB para BFS:

function path = solve_maze(img_file)
  %% Init data
  img = imread(img_file);
  img = rgb2gray(img);
  maze = img > 0;
  start = [985 398];
  finish = [26 399];

  %% Init BFS
  n = numel(maze);
  Q = zeros(n, 2);
  M = zeros([size(maze) 2]);
  front = 0;
  back = 1;

  function push(p, d)
    q = p + d;
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
      front = front + 1;
      Q(front, :) = q;
      M(q(1), q(2), :) = reshape(p, [1 1 2]);
    end
  end

  push(start, [0 0]);

  d = [0 1; 0 -1; 1 0; -1 0];

  %% Run BFS
  while back <= front
    p = Q(back, :);
    back = back + 1;
    for i = 1:4
      push(p, d(i, :));
    end
  end

  %% Extracting path
  path = finish;
  while true
    q = path(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    path(end + 1, :) = p;
    if isequal(p, start) 
      break;
    end
  end
end

Es realmente muy simple y estándar, no debería haber dificultades para implementar esto en Python o lo que sea.

Y esta es la respuesta:

Ingrese la descripción de la imagen aquí

Esta solución está escrita en Python. Gracias Mikhail por los consejos sobre la preparación de la imagen.

Una búsqueda animada en amplitud:

Versión animada de BFS

El laberinto completo:

Laberinto completado

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

Nota: Marca un píxel blanco visitado en gris. Esto elimina la necesidad de una lista visitada, pero esto requiere una segunda carga del archivo de imagen desde el disco antes de dibujar una ruta (si no desea una imagen compuesta de la ruta final y TODAS las rutas tomadas).

Una versión en blanco del laberinto que usé.

Intenté implementar la búsqueda A-Star para este problema. Seguí de cerca la implementación por Joseph Kern para el marco y el pseudocódigo del algoritmo dado aquí:

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

Como A-Star es un algoritmo de búsqueda heurístico, debe crear una función que calcule el costo restante (aquí: distancia) hasta alcanzar la meta. A menos que se sienta cómodo con una solución subóptima, no debe sobrestimar el costo. Una opción conservadora sería aquí la distancia de Manhattan (o taxi), ya que representa la distancia en línea recta entre dos puntos en la cuadrícula para el vecindario de Von Neumann usado. (Lo cual, en este caso, nunca sobrestimaría el costo).

Sin embargo, esto subestimaría significativamente el costo real del laberinto en cuestión. Por lo tanto, agregué otras dos métricas de distancia al cuadrado de la distancia euclidiana y la distancia de Manhattan multiplicada por cuatro para comparar. Sin embargo, estos podrían sobrestimar el costo real y, por lo tanto, podrían producir resultados subóptimos.

Aquí está el código:

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

Aquí hay algunas imágenes para una visualización de los resultados (inspiradas en la publicada por Joseph Kern). Las animaciones muestran un nuevo fotograma cada una después de 10000 iteraciones del bucle while principal.

Búsqueda primero en amplitud:

Búsqueda primero en amplitud

Distancia de A-Star Manhattan:

Distancia de Manhattan A-Star

Distancia euclidiana al cuadrado de una estrella:

Distancia euclidiana al cuadrado de una estrella

Distancia de A-Star Manhattan multiplicada por cuatro:

Distancia de A-Star Manhattan multiplicada por cuatro

Los resultados muestran que las regiones exploradas del laberinto difieren considerablemente para las heurísticas que se utilizan. Como tal, la distancia euclidiana al cuadrado incluso produce una ruta diferente (subóptima) como las otras métricas.

Con respecto al rendimiento del algoritmo A-Star en términos del tiempo de ejecución hasta la terminación, tenga en cuenta que una gran cantidad de evaluaciones de las funciones de distancia y costo se suman en comparación con la búsqueda en amplitud primero (BFS), que solo necesita evaluar la "meta" de cada puesto de candidato. Si el costo de estas evaluaciones de funciones adicionales (A-Star) supera o no el costo de la mayor cantidad de nodos para verificar (BFS) y especialmente si el rendimiento es un problema para su aplicación, es una cuestión de percepción individual y, por supuesto, no se puede responder de forma generalizada.

Una cosa que pueden En general, se puede decir si un algoritmo de búsqueda informado (como A-Star) podría ser la mejor opción en comparación con una búsqueda exhaustiva (por ejemplo, BFS) es la siguiente. Con el número de dimensiones del laberinto, es decir, el factor de ramificación del árbol de búsqueda, la desventaja de una búsqueda exhaustiva (buscar exhaustivamente) crece exponencialmente. Con la creciente complejidad, se vuelve cada vez menos factible hacerlo y en algún momento estás bastante contento con alguna ruta de resultado, ya sea (aproximadamente) óptima o no.

Aquí puedes ver las reseñas y valoraciones de los lectores

Si estás contento con lo expuesto, tienes el poder dejar una división acerca de qué te ha parecido esta sección.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *