Solving mazes with programming

Everyone knows what mazes/labyrinths are! And plenty of us find it amusing to try and solve one! Take the image above as an example... Can you find a path from the top left opening to the bottom right opening? There exists at least one!

I wrote a program in Python (making use of pygame and Pillow) to solve any maze given. I did this project several years ago, after learning about Dijkstra's algorithm. I read about the algorithm and decided to implement it, to get a feel for it. I realized that I could apply it to a maze in a picture, if I took each pixel of the image to be a vertex in the graph where I'd apply the method.

I wanted to make my program fairly general, in terms of the mazes that could be given, and so I dwelled with a problem: how to tell if two adjacent pixels should be connected in the graph or not. I knew I only wanted to connect pixels that referred to the path, and not to the walls, so my idea was simple: I supposed that a picture of a maze would have mainly two colours, one for the walls and another for the paths. I leveraged on that to preprocess the image and turn it to a black and white picture, where each pixel would be either perfectly white or perfectly black (I did this by finding the average luminosity of a pixel in the image and used that as a threshold; a pixel with luminosity below the average becomes black, otherwise it becomes white). After processing, ask the user for the two points we want to connect; if they have the same colour (say it was white) then it must have been because the paths have been changed into white and thus I need only to consider white pixels.

After we know where to start, where to end, and which colour we care about (either black or white) I apply the Dijkstra on the graph of the vertices of that colour, where two vertices are connected if the two corresponding pixels are adjacent. Of course I didn't have to explicitly build the graph, as it was given by the pixels in the picture. After a path is found, a red line is drawn. The first version of the script would draw the absolute shortest path, and so it would mainly be adjacent to walls and I found it aesthetically unpleasing. To try and counter that I added a slight element of randomness when drawing the red path. Using my script to solve the maze above we get

which looks like a line I could draw with my pencil, if I managed to not overlap my line with the walls of the maze by accident. The code can be found in here and a downloadable executable can be found here. In both places you have a folder 'bin' with a couple of maze examples.

[Pt] Os labirintos sempre foram uma panca minha, desde novo, e um dia li sobre um algoritmo bastante famoso, o algoritmo de Dijkstra, e percebi que o podia aplicar para resolver labirintos! Mas antes, tentem resolver o labirinto do início do post, que tem solução.

O processo subjacente à resolução de um labirinto é simples: especifico uma imagem com um labirinto e processo-a para a converter numa imagem a preto e branco, sem tons de cinza. Cada pixel da imagem processada ou é 100% branco ou 100% preto (para fazer isto, calculo a luminosidade média da imagem e uso-a como bitola: se um pixel tiver luminosidade abaixo da média, fica preto; se não, fica branco). De seguida o utilizador escolhe as posições de partida e de chegada, e o programa verifica se, na nova imagem, essas posições têm a mesma cor. A ideia é que, após o processamento, as paredes do labirinto ficaram todas da mesma cor e que os caminhos do labirinto ficaram todos da cor oposta. Não há garantias de que isto acontece, mas é uma suposição bastante razoável.

Se é o caso que as duas posições têm a mesma cor, então usamos o algoritmo de Dijkstra para encontrar o caminho mais curto entre as duas posições. Claro que não é necessário construir o grafo explícito, podemos usar os pixéis como vértices do grafo implícito. Quando o caminho é encontrado, o script desenha-o a vermelho. No início, o script desenhava o caminho absolutamente mais curto, o que se traduzia num caminho sempre rente às paredes e na altura achei que isso era esteticamente desagradável. Para tentar contrariar isso um pouco, incluí um pequeno elemento aleatório na parte que desenha o caminho.

Um exemplo de aplicação do script pode ver-se na segunda imagem. O código pode ser encontrado aqui e um executável aqui. Nos dois sítios há também uma pasta chamada 'bin' onde estão alguns exemplos de labirintos para usar.

Let me know what you think!

-RGS