Hola, descubrimos la solución a lo que necesitas, desplázate y la obtendrás aquí.
Solución:
He aquí una solución.
- 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.
- Convierta la imagen en binario estableciendo el umbral apropiado en Photoshop en Imagen -> Ajustes -> Umbral.
- 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.
- Agregue bordes artificiales en el laberinto para asegurarse de que el viajero virtual no camine alrededor de él 🙂
- 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:
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:
El laberinto completo:
#!/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:
Distancia de A-Star Manhattan:
Distancia euclidiana al cuadrado de una estrella:
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.