Код ниже - решатель лабиринта (взят из этого ответа ).Он использует позиции начала и цели, которые были введены вручную, и мне нужно менять эти координаты каждый раз, когда я изменяю изображение для решения.
Таким образом, я хочу найти способ автоматически генерировать эти позиции на основеimage (это двоичное изображение, 0 означает пустой квадрат, а 1 представляет стену).
Моя идея до сих пор состоит в том, чтобы прогуляться за стеной лабиринта, чтобы определить эти позиции.Алгоритм будет посещать каждый квадрат, и если он равен нулю, он будет рассматриваться как точка входа / выхода.
Поэтому мой вопрос таков: знает ли кто-нибудь способ посещения всех квадратов внешней стены, чтобы определитьвход и цель позиции?Или любая другая идея, которая поможет мне решить эту проблему?
import sys
import png
from PIL import Image
# using an A* Algorithm to solve the maze
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 []
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)
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) # the solution color path is red
path_img.save(sys.argv[2]) # or path_img.save('<outputfile>[.gif|.png|etc.]')
Вывод кода:
