Представление и решение лабиринта заданного изображения

это решение написано на Python. Спасибо Михаилу за указатели на подготовку изображения.

анимированная ширина-первый поиск:

Завершенный Лабиринт:

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

Примечание: отмечает Белый посещенный пиксель серого цвета. Это устраняет необходимость в посещенном списке, но для этого требуется вторая загрузка файла изображения с диска перед рисованием пути (если вы этого не сделаете требуется составное изображение конечного пути и всех принятых путей).

пустая версия лабиринта, который я использовал.

я попробовал сам реализовать A-Star search для этой проблемы. Внимательно следил за реализацией Жозеф Керн для фреймворка и алгоритма псевдокод дан здесь:

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

поскольку A-Star-это эвристический алгоритм поиска, вам нужно придумать функцию, которая оценивает оставшуюся стоимость (здесь: расстояние) до достижения цели. Если вы не согласны с неоптимальным решением, оно не должно переоценивать стоимость. Один консервативный выбор был бы здесь Манхэттен (или такси) расстояние поскольку это представляет собой прямолинейное расстояние между двумя точками на сетке для используемой окрестности фон Неймана. (Что, в данном случае, никогда не будет переоценивать стоимость.)

это, однако, значительно занижает фактическую стоимость для данного лабиринта под рукой. Поэтому я добавил две другие метрики квадратичное евклидово расстояние и расстояние Манхэттен умножить на четыре сравнение. Однако они могут завышать фактическую стоимость и, следовательно, давать неоптимальные результаты.

вот код:

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

вот несколько изображений для визуализации результатов (вдохновленных тем, что опубликовано Жозеф Керн). Анимации показывают новый кадр каждый после 10000 итераций основного цикла while.

Поиск В Ширину:

A-Star Манхэттен Расстояние:

A-Звезда В Квадрате Евклидово Расстояние:

звездное расстояние Манхэттена, умноженное на четыре:

результаты показывают, что исследуемые области лабиринта значительно отличаются для используемых эвристик. Таким образом, квадрат евклидова расстояния даже создает другой (неоптимальный) путь, как и другие метрики.

относительно производительности алгоритма A-Star что касается времени выполнения до завершения, обратите внимание, что многие оценки функций расстояния и стоимости складываются по сравнению с поиском по ширине (BFS), который должен только оценивать "целеустремленность" каждой позиции кандидата. Перевешивает ли стоимость этих дополнительных оценок функций (A-Star) стоимость большего числа узлов для проверки (BFS) и особенно является ли производительность проблемой для вашего приложения вообще, является вопросом индивидуального восприятия и может ли конечно, обычно не отвечают.

штука можете можно сказать в целом о том, может ли информированный алгоритм поиска (например, A-Star) быть лучшим выбором по сравнению с исчерпывающим поиском (например, BFS), заключается в следующем. С увеличением числа измерений лабиринта, т. е. коэффициента ветвления дерева поиска, недостаток исчерпывающего поиска (чтобы искать исчерпывающе) растет экспоненциально. С ростом сложности это становится все менее и менее осуществимым чтобы сделать это, и в какой-то момент Вы в значительной степени довольны любой путь к результату, будь то (приблизительно) Оптимальный или нет.

дерево поиска слишком много. Лабиринт по своей сути отделим вдоль пути (путей) решения.

(спасибо rainman002 от Reddit, чтобы указать мне на это.)

из-за этого вы можете быстро использовать подключенные компоненты определить Соединенные разделы стены лабиринта. Это повторяется над пикселями дважды.

Если вы хотите превратить это в красивую диаграмму пути решения, вы можете использовать двоичные операции с структурирование элементов для заполнения "тупиковых" путей для каждой подключенной области.

демо-код для MATLAB следует. Он может использовать настройку, чтобы лучше очистить результат, сделать его более обобщаемым и заставить его работать быстрее. (Когда это не 2:30 утра.)

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

использует очередь для порогового непрерывного заполнения. Толкает пиксель слева от входа в очередь, а затем запускает цикл. Если пиксель в очереди достаточно темный, он окрашен в светло-серый цвет (выше порога), и все соседи помещаются в очередь.

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

решение представляет собой коридор между серой стеной и цветной стеной. Обратите внимание, что этот лабиринт имеет несколько решений. Кроме того, это просто кажется, что работает.

вот так: maze-solver-python (GitHub)

Мне было весело играть с этим и продлен на Жозеф Керн'ы ответ. Чтобы не отвлекаться от этого; я просто сделал некоторые незначительные дополнения для тех, кто может быть заинтересован в игре с этим.

это решатель на основе python, который использует BFS для поиска кратчайшего пути. Мои основные дополнения, в то время, являются:

1. изображение очищается перед началом поиска (т. е. преобразовать в чистый черный и белый)
2. автоматически генерировать GIF.
3. автоматически генерировать AVI.

в его нынешнем виде начальные / конечные точки жестко закодированы для этого образца лабиринта, но я планирую расширить его таким образом, чтобы вы могли выбрать соответствующие пиксели.

Я бы пошел на вариант матрицы була. Если вы обнаружите, что стандартные списки Python слишком неэффективны для этого, вы можете использовать массив. Хранение для лабиринта 1000x1000 пикселей составляет тогда всего 1 МБ.

не беспокойтесь о создании каких-либо структур данных дерева или графика. Это просто способ думать об этом, но не обязательно хороший способ представить его в памяти; булева матрица легче кодировать и более эффективна.

затем используйте алгоритм A* для решить ее. Для эвристического расстояния используйте расстояние Манхэттена (distance_x + distance_y).

представляют узлы кортежем (row, column) координаты. Всякий раз, когда алгоритм (псевдокод Википедия) вызывает "соседей", это простой вопрос зацикливания на четырех возможных соседей (обратите внимание на края изображения!).

Если вы обнаружите, что он все еще слишком медленный, вы можете попробовать уменьшить масштаб изображения перед его загрузкой. Будьте осторожны, чтобы не потерять какие-либо узкие тропинки в процесс.

возможно, в Python также можно выполнить масштабирование 1:2, проверяя, что вы на самом деле не теряете никаких возможных путей. Интересный вариант, но над ним нужно еще немного подумать.

вот некоторые идеи.

(1. Обработка Изображений:)

1.1 загрузите изображение как RGB пиксель карте. В C# это тривиально с помощью system.drawing.bitmap. В языках без простой поддержки изображений, просто преобразуйте изображение в портативный формат pixmap (PPM) (текстовое представление Unix, создает большие файлы) или какой-то простой двоичный формат файла, который вы можете легко прочитать, например BMP или TGA. ImageMagick в Unix или IrfanView в Windows.

1.2 вы можете, как упоминалось ранее, упростить данные, взяв (R+G+B) / 3 для каждого пикселя в качестве индикатора серого тона, а затем пороговое значение для получения черно-белой таблицы. Что-то близкое к 200, предполагая, что 0=черный и 255=Белый будут вынимать артефакты JPEG.

(2. Решения:)

2.1 глубина-первый поиск: введите пустой стек с начальным местоположением, соберите доступные последующие шаги, выберите один наугад и нажмите на стек, продолжайте, пока не будет достигнут конец или тупик. На deadend backtrack, выталкивая стек, вам нужно отслеживать, какие позиции были посещены на карте, поэтому, когда вы собираете доступные ходы, вы никогда не занимаете один и тот же путь дважды. Очень интересно анимировать.

2.2 ширина-первый поиск: упоминалось ранее, как и выше, но только с использованием очередей. Также интересно анимировать. Это работает как наводнение-заполнить редактирования изображений программное обеспечение. Я думаю, что вы можете решить лабиринт в Photoshop, используя этот трюк.

2.3 последователь стены: геометрически говоря, лабиринт сложенная / свернутая трубка. Если вы держите руку на стене вы в конечном итоге найти выход ;) это не всегда работает. Есть определенные предположения re: идеальные лабиринты и т. д. например , некоторые лабиринты содержат острова. Посмотрите его; это увлекательно.

(3. Комментарии:)

это самое сложное. Это легко решите лабиринты, если они представлены в некотором простом массиве формально, причем каждый элемент является типом ячейки с северной, восточной, южной и Западной стенами и посещаемым полем флага. Однако, учитывая, что вы пытаетесь сделать это, учитывая рисованный эскиз, он становится грязным. Я честно думаю, что попытка рационализировать эскиз сведет вас с ума. Это сродни проблемам компьютерного зрения, которые довольно вовлечены. Возможно, переход непосредственно на карту изображения может быть проще, но более расточительным.

вот решение с помощью 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)

RGB в оттенках серого, см.: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")

вуаля!

это то, что происходит, если вы не заполняете некоторые пиксели границы (ха!)...

полное раскрытие: я спросил и ответил очень аналогичный вопрос меня, прежде чем я нашел это. Затем с помощью магии так, это как один из лучших "вопросов". Я решил использовать этот лабиринт в качестве дополнительного теста... Я был очень рад обнаружить, что мой ответ там также работает для этого приложения с очень небольшими изменениями.