Representando e resolvendo um labirinto, dada uma imagem

271

Qual é a melhor maneira de representar e resolver um labirinto com uma imagem?

A imagem da capa do The Scope Issue 134

Dada uma imagem JPEG (como vista acima), qual é a melhor maneira de lê-la, analisá-la em alguma estrutura de dados e resolver o labirinto? Meu primeiro instinto é ler a imagem em pixel por pixel e armazená-la em uma lista (matriz) de valores booleanos: Truepara um pixel branco e Falsepara um pixel não branco (as cores podem ser descartadas). O problema com esse método é que a imagem pode não ser "pixel perfeita". Com isso, quero dizer simplesmente que, se houver um pixel branco em algum lugar na parede, ele poderá criar um caminho não intencional.

Outro método (que veio a mim depois de um pouco de reflexão) é converter a imagem em um arquivo SVG - que é uma lista de caminhos desenhados em uma tela. Dessa forma, os caminhos podem ser lidos no mesmo tipo de lista (valores booleanos) em que Trueindica um caminho ou parede, Falseindicando um espaço passível de deslocamento. Um problema com esse método surge se a conversão não for 100% precisa e não conectar totalmente todas as paredes, criando lacunas.

Também um problema com a conversão para SVG é que as linhas não são "perfeitamente" retas. Isso resulta nos caminhos sendo curvas cúbicas de bezier. Com uma lista (matriz) de valores booleanos indexados por números inteiros, as curvas não seriam transferidas facilmente e todos os pontos que alinham na curva precisariam ser calculados, mas não corresponderiam exatamente aos índices da lista.

Suponho que, embora um desses métodos possa funcionar (embora provavelmente não o seja), eles são lamentavelmente ineficientes, dada uma imagem tão grande e que existe uma maneira melhor. Como isso é feito (com mais eficiência e / ou com a menor complexidade)? Existe mesmo a melhor maneira?

Depois vem a resolução do labirinto. Se eu usar um dos dois primeiros métodos, acabarei essencialmente com uma matriz. De acordo com esta resposta , uma boa maneira de representar um labirinto é usar uma árvore, e uma boa maneira de resolvê-lo é usar o algoritmo A * . Como alguém criaria uma árvore a partir da imagem? Alguma ideia?

TL; DR
Melhor maneira de analisar? Em que estrutura de dados? Como essa estrutura ajudaria / dificultaria a solução?

ATUALIZAÇÃO
Tentei implementar o que o @Mikhail escreveu em Python, usando numpy, como o @Thomas recomendado. Eu sinto que o algoritmo está correto, mas não está funcionando como esperado. (Código abaixo.) A biblioteca PNG é 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, [])
Whymarrh
fonte
12
Eu converteria o labirinto em preto e branco e usaria um método de encontrar autômatos para resolvê-lo.
Dan D.
Você precisa lidar apenas com essa imagem ou com muitas imagens como essa? Ou seja, existe a opção de algum processamento manual específico para esta determinada imagem?
Mikhail
1
@ Whymarrh Eu não codigo python, mas tenho certeza que você deve mover visited.append(s)sob um for.ife substituí-lo por visited.append(np). Um vértice é visitado quando é adicionado à fila. De fato, essa matriz deve ser denominada "na fila". Você também pode encerrar o BFS quando chegar ao fim.
23412 Mikhail
2
@ Whymarrh E você também parece ter pulado a implementação do bloco de extração de caminho. Sem ele, você só pode descobrir se o acabamento é acessível ou não, mas não como.
Mikhail
1
Para descobrir se há é uma solução, uma UnionFind e uma varredura linear é o algoritmo mais rápido. Ele não fornece o caminho, mas fornece um conjunto de blocos que terão o caminho como um subconjunto.
24512 st0le

Respostas:

236

Aqui está uma solução.

  1. Converta a imagem em escala de cinza (ainda não binária), ajustando os pesos das cores para que a imagem final da escala de cinza fique aproximadamente uniforme. Você pode fazer isso simplesmente controlando os controles deslizantes do Photoshop em Imagem -> Ajustes -> Preto e branco.
  2. Converta a imagem em binário, definindo o limite apropriado no Photoshop em Imagem -> Ajustes -> Limiar.
  3. Verifique se o limite está selecionado corretamente. Use a Magic Wand Tool com tolerância 0, amostra pontual, contígua, sem suavização de serrilhado. Verifique se as arestas nas quais as quebras de seleção não são arestas falsas introduzidas pelo limite errado. De fato, todos os pontos interiores deste labirinto são acessíveis desde o início.
  4. Adicione bordas artificiais no labirinto para garantir que o viajante virtual não o rodeie :)
  5. Implemente a pesquisa por largura (BFS) no seu idioma favorito e execute-a desde o início. Eu prefiro o MATLAB para esta tarefa. Como o @Thomas já mencionou, não há necessidade de mexer com a representação regular de gráficos. Você pode trabalhar diretamente com a imagem binarizada.

Aqui está o 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

É realmente muito simples e padrão, não deve haver dificuldades em implementar isso em Python ou o que seja.

E aqui está a resposta:

Digite a descrição da imagem aqui

Mikhail
fonte
1
@ Whymarrh Bem, para "Apenas esta imagem", agora você realmente tem uma resposta. Você tem alguma pergunta específica? Os itens 1 a 4 da minha lista são o processamento manual sobre o qual eu estava perguntando. O item 5 é um BFS - o algoritmo muito básico para gráficos, mas pode ser aplicado diretamente à imagem, sem converter pixels em vértices e vizinhos em arestas.
21412 Mikhail
Eu sinto que você cobriu tudo. Estou tentando implementar o que você disse em Python (usando o DFS no lugar do BFS, apenas porque codifiquei isso uma vez antes). Voltarei para atualizar a pergunta / aceitar as respostas daqui a pouco.
Whymarrh
2
O @Whymarrh DFS não encontrará o caminho mais curto, enquanto o BFS o encontrará. Eles são inerentemente iguais, a única diferença é a estrutura subjacente. Pilha (FILO) para DFS e fila (FIFO) para BFS.
Mikhail
3
O BFS é a escolha certa aqui, porque produz um caminho mais curto, o que fornece um caminho "sensível", mesmo quando os corredores são muito maiores que 1 pixel. OTOH DFS tenderá a explorar corredores e regiões de labirinto pouco promissoras com um padrão de "inundação".
Jrandom_hacker 24/10/12
1
@JosephKern Path não se sobrepõe a nenhuma parede. Basta remover todos os pixels vermelhos e aqui está.
30612 Mikhail
160

Esta solução está escrita em Python. Obrigado Mikhail pelas dicas sobre a preparação da imagem.

Uma pesquisa de largura em primeiro lugar animada:

Versão animada do BFS

O labirinto completo:

Labirinto concluído

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

Nota: Marca um pixel visitado branco em cinza. Isso elimina a necessidade de uma lista visitada, mas requer uma segunda carga do arquivo de imagem do disco antes de desenhar um caminho (se você não quiser uma imagem composta do caminho final e TODOS os caminhos).

Uma versão em branco do labirinto que eu usei.

Joseph Kern
fonte
13
Como você foi incrível o suficiente para voltar e me votar de novo, mesmo depois que sua pergunta foi respondida, criei um gif animado do BFS, para ajudar a visualizar melhor o processo.
Joseph Kern
1
Agradável, obrigado. Para outros que desejam brincar com isso, como eu, gostaria de compartilhar minhas dicas com base nas dificuldades que enfrentei. 1) Converta a imagem em preto e branco puro ou modifique sua função 'isWhite ()' para aceitar quase branco | preto. Eu escrevi um método 'cleanImage' que pré-processou todos os pixels, convertendo-os em branco ou preto puro, caso contrário, o algoritmo não consegue encontrar um caminho. 2) Leia a imagem explicitamente como RGB [base_img = Image.open (img_in); base_img = base_img.convert ('RGB')]. Para obter um gif, imprima várias imagens e execute 'convert -delay 5 -loop 1 * .jpg bfs.gif'.
stefano
1
recuo ausente na linha 13
sloewen 01/01
81

Eu tentei implementar a pesquisa A-Star para esse problema. Seguiu de perto a implementação por Joseph Kern para o framework e o pseudocódigo do algoritmo fornecido aqui :

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 o A-Star é um algoritmo de pesquisa heurística, é necessário criar uma função que calcule o custo restante (aqui: distância) até que a meta seja alcançada. A menos que você esteja confortável com uma solução abaixo do ideal, ela não deve superestimar o custo. Uma escolha conservadora seria aqui a distância de manhattan (ou táxi), pois isso representa a distância em linha reta entre dois pontos na grade do bairro de Von Neumann usado. (Que, nesse caso, nunca superestimaria o custo.)

No entanto, isso subestimaria significativamente o custo real do labirinto em questão. Portanto, adicionamos outras duas métricas de distância ao quadrado da distância euclidiana e a distância de manhattan multiplicada por quatro para comparação. No entanto, esses fatores podem superestimar o custo real e, portanto, produzir resultados abaixo do ideal.

Aqui está o 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 <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])

Aqui estão algumas imagens para uma visualização dos resultados (inspirada na postada por Joseph Kern ). As animações mostram um novo quadro após 10.000 iterações do loop while principal.

Primeira pesquisa de largura:

Primeira pesquisa de largura

Distância A-Star Manhattan:

Distância A-Star Manhattan

Distância Euclidiana Quadrada A-Star:

Distância Euclidiana Quadrada A-Star

Distância A-Star Manhattan multiplicada por quatro:

Distância A-Star Manhattan multiplicada por quatro

Os resultados mostram que as regiões exploradas do labirinto diferem consideravelmente para as heurísticas utilizadas. Como tal, a distância euclidiana quadrada produz um caminho (subótimo) diferente das outras métricas.

No que diz respeito ao desempenho do algoritmo A-Star em termos de tempo de execução até o término, observe que muitas funções de distância e custo são adicionadas em comparação com a pesquisa de largura da primeira pesquisa (BFS), que precisa apenas avaliar a "objetividade" de cada posição de candidato. Se o custo dessas avaliações de funções adicionais (A-Star) supera ou não o custo do maior número de nós a verificar (BFS) e, principalmente, se o desempenho é ou não um problema para a sua aplicação, é uma questão de percepção individual e, é claro, geralmente não pode ser respondido.

Uma coisa que pode ser dito em geral sobre se um algoritmo de pesquisa informado (como o A-Star) pode ser a melhor escolha em comparação com uma pesquisa exaustiva (por exemplo, BFS) é a seguinte. Com o número de dimensões do labirinto, ou seja, o fator de ramificação da árvore de pesquisa, a desvantagem de uma pesquisa exaustiva (pesquisar exaustivamente) aumenta exponencialmente. Com a crescente complexidade, torna-se cada vez menos viável fazê-lo e, em algum momento, você fica muito feliz com qualquer caminho de resultado, seja (aproximadamente) ideal ou não.

moooeeeep
fonte
1
"Distância A-Star Manhattan multiplicada por quatro"? A-Star não é A-Star se a heurística puder superestimar a distância. (E, portanto, também não garante encontrar o caminho mais curto)
exemplo
@exemplo Obviamente, se alguém aplicar uma função heurística não admissível, o algoritmo poderá falhar em encontrar a solução ideal (como apontei na minha resposta). Mas eu não chegaria ao ponto de renomear o algoritmo básico por esse motivo.
22414 moooeeeep
38

A pesquisa em árvore é demais. O labirinto é inerentemente separável ao longo do (s) caminho (s) da solução.

(Obrigado a rainman002 do Reddit por apontar isso para mim.)

Por esse motivo, você pode usar rapidamente os componentes conectados para identificar as seções conectadas da parede do labirinto. Isso itera sobre os pixels duas vezes.

Se você quiser transformar isso em um bom diagrama do (s) caminho (s) da solução, poderá usar operações binárias com elementos estruturantes para preencher os caminhos "sem saída" para cada região conectada.

Segue o código de demonstração do MATLAB. Poderia usar ajustes para limpar melhor o resultado, torná-lo mais generalizável e executá-lo mais rapidamente. (Às vezes não são 2:30 da manhã.)

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

resultado do código atual

Jim Gray
fonte
24

Usa uma fila para um preenchimento contínuo de limite. Empurra o pixel esquerdo da entrada para a fila e inicia o loop. Se um pixel na fila é escuro o suficiente, fica cinza claro (acima do limite) e todos os vizinhos são empurrados para a fila.

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

Solução é o corredor entre a parede cinza e a parede colorida. Observe que este labirinto tem várias soluções. Além disso, isso apenas parece funcionar.

Solução

kylefinn
fonte
1
Resolução ingênua interessante, baseada no método de mão na parede. Na verdade, não é o melhor, mas eu gosto.
Zessx
23

Aqui está: maze-solver-python (GitHub)

insira a descrição da imagem aqui

Eu me diverti brincando com isso e estendi Joseph Kern resposta de . Não a depreciar; Acabei de fazer algumas pequenas adições para quem mais estiver interessado em brincar com isso.

É um solucionador baseado em python que usa o BFS para encontrar o caminho mais curto. Minhas principais adições, na época, são:

  1. A imagem é limpa antes da pesquisa (por exemplo, converter para preto e branco puro)
  2. Gere automaticamente um GIF.
  3. Gere automaticamente um AVI.

Tal como está, os pontos de partida / chegada são codificados para este labirinto de amostras, mas pretendo estendê-lo para que você possa escolher os pixels apropriados.

Stefano
fonte
1
Ótimo, obrigado, ele não rodava no BSD / Darwin / Mac, algumas dependências e o script do shell precisavam de pequenas alterações, para quem deseja experimentar o Mac: [maze-solver-python]: github.com/holg/maze- Solver-python
HolgT 10/03
@ HolgT: Que bom que você achou útil. Congratulo-me com todos os pedidos pull para isso. :)
stefano
5

Eu iria para a opção matriz de bools. Se você achar que as listas Python padrão são muito ineficientes para isso, use uma numpy.boolmatriz. O armazenamento para um labirinto de 1000x1000 pixels é de apenas 1 MB.

Não se preocupe em criar estruturas de dados em árvore ou gráfico. Essa é apenas uma maneira de pensar sobre isso, mas não necessariamente uma boa maneira de representá-lo na memória; uma matriz booleana é mais fácil de codificar e mais eficiente.

Em seguida, use o algoritmo A * para resolvê-lo. Para a heurística da distância, use a distância de Manhattan ( distance_x + distance_y).

Represente nós por uma tupla de (row, column)coordenadas. Sempre que o algoritmo ( pseudocódigo da Wikipedia ) pede "vizinhos", é uma simples questão de percorrer os quatro vizinhos possíveis (lembre-se das bordas da imagem!).

Se você achar que ainda está muito lento, tente reduzir a imagem antes de carregá-la. Cuidado para não perder nenhum caminho estreito no processo.

Talvez seja possível fazer um downscaling 1: 2 no Python também, verificando se você realmente não perde nenhum caminho possível. Uma opção interessante, mas precisa de um pouco mais de reflexão.

Thomas
fonte
Este excelente post no blog mostra como resolver um labirinto no mathematica. Traduzindo o método para python não deve ser um problema
Boris Gorelik
Eu atualizei a pergunta. Se eu optar por usar triplos RGB em vez de booleanvalores, o armazenamento ainda será comparado? A matriz é então 2400 * 1200. E A * sobre BFS teria um impacto significativo no tempo de execução real?
Whymarrh
@Whymarrh, a profundidade do bit pode diminuir para compensar. 2 bits por pixel deve ser suficiente para qualquer pessoa.
Brian Cain
5

Aqui estão algumas idéias.

(1. Processamento de imagem :)

1.1 Carregue a imagem como mapa de pixels RGB . Em C # é trivial usando system.drawing.bitmap. Em idiomas sem suporte simples para geração de imagens, basta converter a imagem em formato pixmap portátil (PPM) (uma representação de texto Unix, produz arquivos grandes) ou em algum formato de arquivo binário simples que você pode ler facilmente, como BMP ou TGA . ImageMagick no Unix ou IrfanView no Windows.

1.2 Você pode, como mencionado anteriormente, simplificar os dados, tomando o (R + G + B) / 3 para cada pixel como um indicador de tom de cinza e, em seguida, limiar o valor para produzir uma tabela em preto e branco. Algo próximo de 200 assumindo 0 = preto e 255 = branco removerá os artefatos JPEG.

(2. Soluções :)

2.1 Busca pela profundidade: inicie uma pilha vazia com o local inicial, colete os movimentos de acompanhamento disponíveis, escolha uma aleatoriamente e empurre para a pilha, prossiga até o fim ser atingido ou um beco sem saída. No back-track sem saída, popeando a pilha, você precisa acompanhar quais posições foram visitadas no mapa; assim, quando você coletar movimentos disponíveis, nunca seguirá o mesmo caminho duas vezes. Muito interessante para animar.

2.2 Pesquisa pela primeira vez: mencionada anteriormente, semelhante à anterior, mas usando apenas filas. Também interessante para animar. Isso funciona como um software de edição de imagem para preenchimento automático. Eu acho que você pode resolver um labirinto no Photoshop usando esse truque.

2.3 Seguidor de Parede: Geometricamente falando, um labirinto é um tubo dobrado / complicado. Se você mantiver a mão na parede, encontrará a saída;) Isso nem sempre funciona. Existem certas suposições sobre labirintos perfeitos, etc., por exemplo, certos labirintos contêm ilhas. Procure; é fascinante.

(3. Comentários :)

Este é o mais complicado. É fácil resolver labirintos se representado em alguma matriz simples formal, com cada elemento sendo um tipo de célula com paredes norte, leste, sul e oeste e um campo de bandeira visitado. No entanto, dado que você está tentando fazer isso, com um esboço desenhado à mão, ele fica confuso. Sinceramente, acho que tentar racionalizar o esboço o deixará louco. Isso é semelhante a problemas de visão computacional bastante envolvidos. Talvez ir diretamente para o mapa da imagem seja mais fácil e mais esbanjador.

lino
fonte
2

Aqui está uma solução usando 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 para escala de cinza, consulte: 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")

Voila!

solução que encontra corretamente o caminho mais curto

É o que acontece se você não preencher alguns pixels de borda (Ha!) ...

versão da solução em que o solucionador percorre o labirinto

Divulgação completa: fiz e respondi uma pergunta muito semelhante antes de encontrar essa. Então, através da magia do SO, encontrei este como uma das principais "perguntas relacionadas". Eu pensei em usar esse labirinto como um caso de teste adicional ... Fiquei muito satisfeito ao descobrir que minha resposta lá também funciona para esse aplicativo com poucas modificações.

Brian D
fonte
0

a boa solução seria que, em vez de encontrar os vizinhos por pixel, fosse feito por célula, porque um corredor pode ter 15px; portanto, no mesmo corredor, ele pode executar ações como esquerda ou direita, enquanto se fosse feito como se o deslocamento era um cubo, seria uma ação simples como CIMA, BAIXO, ESQUERDA OU DIREITA

black_john
fonte
Você pode adicionar o gráfico e o algoritmo da solução como o restante da resposta para validar seu argumento? Será melhor se você puder adicioná-las para adicionar mais peso à sua resposta, para que outras pessoas possam entender melhor sua resposta.
Himanshu Bansal