Algorithm learned with Python 12th: Maze search

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. Maze search is dealt with as the twelfth bullet.

Definition of the maze

Here, we deal with the following two-dimensional maze. S and G indicate the start and goal, respectively. Also, the black paint is the wall, and only the white paint can pass through. Furthermore, since it is handled by the program, numbers are associated with the start, goal, wall, and road as follows. In addition, the number is overwritten with 2 for the road passed during the search.

This time, a sentinel is used to search the maze using two methods, breadth-first search and depth-first search.

What is a sentinel?

** The sentinel is the data to be added to the list as a termination condition **. The sentinel in this case is the existence of an outer wall not shown in the above figure. It is a 10x10 maze, but when it is expressed in a program, it becomes a 12x12 maze in consideration of the outer wall. This makes it possible to determine where the vehicle cannot proceed without distinguishing between the inner wall and the outer wall. It is the effect of the sentinel that can be ** simplified ** in this way.

Implementation

A maze search is performed based on the above conditions. The program shows the code and output in the order of breadth-first search and depth-first search.

Code (breadth-first search)

maze1.py

"""
2020/12/30
@Yuya Shimizu

Guard
Maze search 1 (breadth-first search)
"""

#Search function: When the goal is reached, the position / movement number at that time is returned.
def Maze(start):
    #Start position (x coordinate,y coordinate,Number of moves)
    pos = start

    while len(pos) > 0:#True if searchable
        x, y, depth = pos.pop(0) #Get the position to search from the list

        #Ends when you reach the goal
        if maze[x][y] == 1:
            return [(x, y), depth]

        #Set as searched
        maze[x][y] = 2

        #Search up, down, left and right of the current position: 〇<2 indicates something that is neither a wall nor explored
        if maze[x-1][y] < 2:#left
            pos.append([x-1, y, depth + 1])
        if maze[x+1][y] < 2:#right
            pos.append([x+1, y, depth + 1])
        if maze[x][y-1] < 2:#Up
            pos.append([x, y-1, depth + 1])
        if maze[x][y+1] < 2:#under
            pos.append([x, y+1, depth + 1])
            
    return False

if __name__ == '__main__':
    #Maze creation
    maze = [
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
                [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
                [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 0, 9],
                [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
                [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
                [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
                [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
                [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
                [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
                ]
    start = [[1, 1, 0]]     #Start position
    
    result = Maze(start)  #search

    print(result)

output

[(6, 10), 28]

The output is the (x, y) coordinates and the number of moves.

Next, the code that outputs the state of the search is shown. Since the output will be very long, only a part is shown.

Code (visualization)

maze1_1.py

"""
2020/12/30
@Yuya Shimizu

Guard
Maze search 1 (breadth-first search)
"""
from time import sleep

#Function that tracks the state of search (outputs maze updates)
def track(maze, start, depth):
    draw = f"{depth}Hands\n"
    for x in range(len(maze)):
        for y in range(len(maze[x])):
            if x == start[0][0] and y == start[0][1]:
                draw += "S  "   #Start position
            elif maze[x][y] > 2:
                draw += "■ "    #wall
            elif maze[x][y] == 2:
                draw += "*  "    #The road that has been explored
            elif maze[x][y] == 1:
                draw += "G  "   #Goal position
            else:
                draw += "　 "    #Unexplored road
                
        draw += "\n"
    print(draw)
                
#Search function: When the goal is reached, the position / movement number at that time is returned.
def Maze(start):
    #Start position (x coordinate,y coordinate,Number of moves)
    pos = start.copy()

    while len(pos) > 0:#True if searchable
        x, y, depth = pos.pop(0) #Get the position to search from the list
        #Ends when you reach the goal
        if maze[x][y] == 1:
            return [(x, y), depth]

        #Set as searched
        maze[x][y] = 2
        #Figure update every second
        sleep(1)
        track(maze, start, depth)

        #Search up, down, left and right of the current position: 〇<2 indicates something that is neither a wall nor explored
        if maze[x-1][y] < 2:#left
            pos.append([x-1, y, depth + 1])
        if maze[x+1][y] < 2:#right
            pos.append([x+1, y, depth + 1])
        if maze[x][y-1] < 2:#Up
            pos.append([x, y-1, depth + 1])
        if maze[x][y+1] < 2:#under
            pos.append([x, y+1, depth + 1])
            
    return False


if __name__ == '__main__':
    #Maze creation
    maze = [
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
                [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
                [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 0, 9],
                [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
                [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
                [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
                [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
                [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
                [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
                ]
    start = [[1, 1, 0]]     #Start position
    
    result = Maze(start)  #search

    print(result)

output

12th move
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■ S * * ■ * * * * * * ■
■ * ■ * * * ■ ■ * ■   ■
■ * ■ ■ * ■     * ■   ■
■ * * * ■     ■ ■   ■ ■
■ ■ ■ * * ■   ■       ■
■ * * * ■ * ■     ■ G ■
■ * ■ * * * * ■     ■ ■
■ * * ■ * ■ *   ■     ■
■ * ■   ■   ■     ■   ■
■             ■       ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ 

Due to differences in the environment and line breaks, it looks a little vertically long, but when the program is actually executed, it looks a little better. For reference, the screenshot at that time is shown below.

Code (depth-first search)

maze2.py

"""
2020/12/30
@Yuya Shimizu

Guard
Maze search 2 (simple depth-first search)
"""

#Search function: When the goal is reached, the position / movement number at that time is returned.
def Maze(x, y, depth):
    #Ends when you reach the goal
    if maze[x][y] == 1:
        print([(x, y), depth])
    
    #Set as searched
    maze[x][y] = 2
        
    #Search up, down, left and right of the current position: 〇<2 indicates something that is neither a wall nor explored
    if maze[x-1][y] < 2:#left
        Maze(x-1, y, depth + 1)
    if maze[x+1][y] < 2:#right
        Maze(x+1, y, depth + 1)
    if maze[x][y-1] < 2:#Up
        Maze(x, y-1, depth + 1)
    if maze[x][y+1] < 2:#under
        Maze(x, y+1, depth + 1)

    #Return to before exploration
    maze[x][y] = 0

if __name__ == '__main__':
    #Maze creation
    maze = [
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
                [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
                [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 0, 9],
                [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
                [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
                [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
                [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
                [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
                [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
                ]

    result = Maze(1, 1, 0)  #search

output

[(6, 10), 28]

The output is the (x, y) coordinates and the number of moves.

Next, the code that outputs the state of the search is shown. Since the output will be very long, only a part is shown.

Code (visualization)

maze2_1.py

"""
2020/12/30
@Yuya Shimizu

Guard
Maze search 2 (simple depth-first search)
"""
from time import sleep

#Function that tracks the state of search (outputs maze updates)
def track(maze, depth):
    draw = f"{depth}Hands\n"
    for x in range(len(maze)):
        for y in range(len(maze[x])):
            if maze[x][y] > 2:
                draw += "■ "    #wall
            elif maze[x][y] == 2:
                draw += "*  "    #The road that has been explored
            elif maze[x][y] == 1:
                draw += "G  "   #Goal position
            else:
                draw += "　 "    #Unexplored road

        draw += "\n"
    print(draw)
    
#Search function: When the goal is reached, the position / movement number at that time is returned.
def Maze(x, y, depth):
    #Ends when you reach the goal
    if maze[x][y] == 1:
        print([(x, y), depth])
        exit()
    
    #Set as searched
    maze[x][y] = 2
    #Figure update every second
    sleep(1)
    track(maze, depth)
        
    #Search up, down, left and right of the current position: 〇<2 indicates something that is neither a wall nor explored
    if maze[x-1][y] < 2:#left
        Maze(x-1, y, depth + 1)
    if maze[x+1][y] < 2:#right
        Maze(x+1, y, depth + 1)
    if maze[x][y-1] < 2:#Up
        Maze(x, y-1, depth + 1)
    if maze[x][y+1] < 2:#under
        Maze(x, y+1, depth + 1)

    #Return to before exploration
    maze[x][y] = 0

if __name__ == '__main__':
    #Maze creation
    maze = [
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
                [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
                [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 0, 9],
                [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
                [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
                [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
                [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
                [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
                [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
                [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
                [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
                ]

    result = Maze(1, 1, 0)  #search

output

27th move
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ 
■ *     ■             ■ 
■ * ■       ■ ■   ■   ■ 
■ * ■ ■   ■       ■   ■ 
■ * * * ■     ■ ■   ■ ■ 
■ ■ ■ *   ■   ■ * * * ■ 
■     * ■   ■   * ■ G ■ 
■   ■ * * * * ■ * * ■ ■ 
■     ■   ■ * * ■ * * ■ 
■   ■   ■   ■ * * ■ * ■ 
■             ■ * * * ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ 

[(6, 10), 28]

Similarly, due to differences in the environment and line breaks, it looks a little vertically long, but when the program is actually executed, it looks a little better. For reference, the screenshot at that time is shown below.

Impressions

I learned maze exploration. I thought this when I was studying that there was something that could lead to searching in mobile robots. This book also describes the right method. I did not describe the right method this time, but I could understand it. Also, since it is one of the previous examples of tree structures, I think that a deeper understanding was gained through the application of the tree structure search. We will touch on some more examples of search. This time was the first one.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha