Labyrinths are a common puzzle for people, but they are an interesting programming problem that we can solve using shortest path methods such as Dijkstra’s algorithm.

Recall Dijkstra’s algorithm


Dijkstra's algorithm is one of the most popular graph theory algorithms. It is used to find the shortest path between nodes on a directed graph. We will start with the source node and the known edge lengths between the nodes.

First, we assign the distance value from the source to all nodes. The node s gets the value 0 because it is the source; the rest get ∞ to get started.

imagebr>
Our node of interest is the raw node with the smallest value (shown in gray), i.e. s. First, we “weaken” each adjacent vertex to our node of interest, updating their values ​​to the minimum of their current value or the value of the node of interest plus the length of the connecting edge...

image

Node s is now complete (black), and its neighbors a and b have taken on new values. The new node of interest is b, so we repeat the process of “weakening” the neighboring nodes of b and finalizing the value of the shortest path for b.

image

After going through each node, we end up with a graph showing the shortest path length from the source to each node.

imagebr>
image

imagebr>
Our final diagram after the launch of the Dijkstra algorithm. The numbers at each node represent the shortest possible distance from the source node.

Conceptualization of the images of the maze


imagebr>
We can imagine the image as a matrix of pixels. Each pixel (for simplicity) has an RGB value of 0.0.0 (black) or 255,255,255 (white). Our goal is to create the shortest path that starts on white and does not go to black borders. To represent this goal, we can consider each pixel as a node and draw edges between adjacent pixels with edge lengths based on the difference in RGB values. We will use the Euclidean square distance formula and add 0.1 to guarantee the absence of a path length of 0 - (requirement for Dijkstra's algorithm):

image

This formula makes the intersection distance across the maze border excessively large. As we see, the shortest path from the source to the destination will clearly pass around the barrier, and not through it.

image

Implementation


We can use OpenCV, the popular Python vision library for Python, to extract pixel values ​​and display our maze images.Let's also determine the coordinates of our start and end locations by adding points to our maze

import cv2 import matplotlib.pyplot as plt import numpy as np img=cv2.imread('maze.png') # read an image from a file using cv2.circle(img,(5,220), 3, (255,0,0), -1) # add a circle at (5, 220) cv2.circle(img, (25,5), 3, (0,0,255), -1) # add a circle at (5,5) plt.figure(figsize=(7,7)) plt.imshow(img) # show the image plt.show() 

image

We are creating a Vertex class that will help us track coordinates. We also want to track the parent node so that we can restore all the way as soon as we find the distance values.

class Vertex: def __init__(self,x_coord,y_coord): self.x=x_coord self.y=y_coord self.d=float('inf') #current distance from source node self.parent_x=None self.parent_y=None self.processed=False self.index_in_queue=None 

We need to create a vertex matrix representing the two-dimensional arrangement of pixels in the image. This will be the basis for Dijkstra's algorithm. We also maintain a queue with a minimum heap of priorities for tracking raw nodes.

def find_shortest_path(img,src,dst): pq=[] #min-heap priority queue imagerows,imagecols=img.shape[0],img.shape[1] matrix=np.full((imagerows, imagecols), None) #access matrix elements by matrix[row][col] #fill matrix with vertices for r in range(imagerows): for c in range(imagecols): matrix[r][c]=Vertex(c,r) matrix[r][c].index_in_queue=len(pq) pq.append(matrix[r][c]) #set source distance value to 0 matrix[source_y][source_x].d=0 #maintain min-heap invariant (minimum d Vertex at list index 0) pq=bubble_up(pq, matrix[source_y][source_x].index_in_queue) 

We need some helper functions to help find the edges and the length of the edges between the vertices:

#Implement euclidean squared distance formula def get_distance(img,u,v): return 0.1 + (float(img[v][0])-float(img[u][0]))**2+(float(img[v][1])-float(img[u][1]))**2+(float(img[v][2])-float(img[u][2]))**2 #Return neighbor directly above, below, right, and left def get_neighbors(mat,r,c): shape=mat.shape neighbors=[] #ensure neighbors are within image boundaries if r > 0 and not mat[r-1][c].processed: neighbors.append(mat[r-1][c]) if r < shape[0] - 1 and not mat[r+1][c].processed: neighbors.append(mat[r+1][c]) if c > 0 and not mat[r][c-1].processed: neighbors.append(mat[r][c-1]) if c < shape[1] - 1 and not mat[r][c+1].processed: neighbors.append(mat[r][c+1]) return neighbors 

Now we can implement Dijkstra’s algorithm and assign distance values ​​(d) to all the vertices of the pixels in the maze image:

while len(pq) > 0: u=pq[0] #smallest-value unprocessed node #remove node of interest from the queue pq[0]=pq[-1] pq[0].index_in_queue=0 pq.pop() pq=bubble_down(pq,0) #min-heap function, see source code u.processed=True neighbors=get_neighbors(matrix,u.y,u.x) for v in neighbors: dist=get_distance(img,(u.y,u.x),(v.y,v.x)) if u.d + dist < v.d: v.d=u.d+dist v.parent_x=u.x #keep track of the shortest path v.parent_y=u.y idx=v.index_in_queue pq=bubble_down(pq,idx) pq=bubble_up(pq,idx) 

Now we can call the shortest path function and draw a solution in our maze:

img=cv2.imread('maze.png') # read an image from a file using opencv (cv2) library p=find_shortest_path(img, (25,5), (5,220)) drawPath(img,p) plt.figure(figsize=(7,7)) plt.imshow(img) # show the image on the screen plt.show() 

image

image

Let's try other mazes from all over the Internet.

image

image

imagebr>
imagebr>
The full source code is available on GitHub here .

Continued: Python tutorial: 40-line code interface (part 2)

image

Learn the details of how to get a sought-after profession from scratch or Level Up in skills and salary by completing SkillFactory paid online courses:



Read more


.

Source