Solving the Maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference-

Overview

This is a series of reading books, re-studying various things, and writing what you are interested in. This time, [Algorithm Quick Reference](http://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82% BA% E3% 83% A0% E3% 82% AF% E3% 82% A4% E3% 83% 83% E3% 82% AF% E3% 83% AA% E3% 83% 95% E3% 82% A1% E3% 83% AC% E3% 83% B3% E3% 82% B9-George-T-Heineman / dp / 4873114284) The theme is "Graph Algorithm" in Chapter 6. Specifically, it's a chapter on solving mazes in Python. How did this happen.

How to solve the maze

Before

It explains how to convert a graph with a branch point as a node and solve it. That's true, but when it comes to "how to reduce a given maze to a graph," only the way humans do it was talked about. So, let's think about making a graph by inputting the following figure (character string) that copied the maze as much as possible.

maze_input.txt

$$$$$$$$$$$$$$$$$
$   $   $       $
$ $ $ $ $ $$$$$ $
$ $ $ $ $ $   $ $
$ $ $ $$$ $ $ $ $
$ $ $   $ $ $   $
$ $ $ $ $ $ $$$$$
$ $ $ $ $t$   $ $
$ $$$ $ $$$ $ $ $
$     $     $ $ $
$ $$$ $ $$$ $ $ $
$ $   $ $   $   $
$$$ $$$$$ $$$ $ $
$   $         $ $
$ $$$ $$$$$$$$$ $
$    s          $
$$$$$$$$$$$$$$$$$

It's very confusing, but there are s and t, which correspond to the start and target points. The method of creating the lower character string from the upper figure is to ** extend and connect the squares, thinking that the squares are actually hidden between each square in the maze diagram **. In other words

--The 2nd and 2j columns in the character string below correspond to the i and j columns in the above figure. --Other positions in the string below (for example, the $ symbol in 3 rows and 3 columns) are the black line in the above figure or the "passage" hidden between the squares if there is no wall. Corresponds to

You can add such a response. In other words, when there are grid-like squares, you can think of two types of placement: how to place the stones on the board and how to place the pieces on the shogi board. By combining these, I decided to think of either (1) the center of the square, (2) the midpoint of the side, or the intersection of (3) the side as "a place where stones and pieces can be placed". If there is a black line in this "place where stones and pieces can be placed", it can be obtained by making the correspondence "$", otherwise "".

Make a graph

Well, the introduction has become long, but I will write a program in Python that gets a graph from this maze.

CreateGraph.py

#Graph the maze: Depth-first search in essence
import itertools as it

def isWall(s):
    return 1 if s == '$' else 0

def getWalls(arr, i, j):
    return isWall(arr[i+1][j]) + isWall(arr[i-1][j]) + isWall(arr[i][j+1]) + isWall(arr[i][j-1])

def getEdge(arr, i, j, edges, v, c):
    for (a,b) in zip([1,-1,0,0], [0,0,1,-1]):
        if isWall(arr[i+a][j+b]) == 0:
            arr[i+a][j+b] = '$'
            if arr[i+2*a][j+2*b] == 0:
                vn = v
                cn = c + 1
            else:
                vn = arr[i+2*a][j+2*b]
                edges.append((v, vn, c))
                cn = 1
            getEdge(arr, i+2*a, j+2*b, edges, vn, cn)

vs = 0
edges = list()
arr = list()
for line in open('maze_input.txt', 'r'):
    arr.append(list(line))
height = len(arr)
width = len(arr[height - 1])
cellidi = range(1,width,2)
cellidj = range(1,height,2)
for i,j in it.product(cellidi, cellidj):
    if getWalls(arr, i, j) == 2:
        arr[i][j] = 0
    elif arr[i][j] == ' ':
        vs += 1
        arr[i][j] = vs

#Settings for this data
getEdge(arr, 3, 7, edges, 1, 1)

A function called getEdge is essentially a depth-first search, and simply recursively processes the cells adjacent to it. Whether or not the square has already been processed is written as it is in the list arr that contains the board. In addition, when doing this process, I also decided to calculate "side length" = "the number of squares until the next intersection or dead end".

Visualization of maze graph

Since it's a big deal, let's visualize this.

Visualize.py

#Visualization
import networkx as nx
import matplotlib.pyplot as plt
import math

G = nx.Graph()
srcs, dests = zip(* [(fr, to) for (fr, to, d) in edges])
G.add_nodes_from(srcs + dests)

for (s,r,d) in edges:
    G.add_edge(s, r, weight=20/math.sqrt(d))

pos = nx.spring_layout(G)

edge_labels=dict([((u,v,),d)
             for u,v,d in edges])

plt.figure(1)
nx.draw_networkx(G, pos, with_labels=True)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)

plt.axis('equal')
plt.show()

Compared to the original maze, it seems that the positional relationship is slightly rotated, but if you grasp it based on the positional relationship of s and t, you can see that it is a graph that is a transcription of the original maze. .. Naturally, it is the same type as the illustration in the book. (Except for the names of the vertices!)

Breadth-first search in this graph

Now that we have a graph, let's ignore the weighting (actual distance) of this graph and calculate the depth based only on the number of nodes.

BreadthFirst.py

#Breadth-first search
import copy

#Definition of neighborhood and used flags (generation)
verts = range(1,vs + 1)
verts.append('s')
verts.append('t')
neighbor = {}
used = {}
used['t'] = 0
for v in verts:
    neighbor[v] = {}
    used[v] = 0
used['s'] = 1
for (s, t, d) in edges:    
    neighbor[s][t] = d
    neighbor[t][s] = d

queue = list()
queue.append('s')
while len(queue) > 0:
    t = queue.pop(0)
    for n in neighbor[t]:
        if used[n] == 0:
            used[n] = used[t] + 1
            queue.append(n)

used

You will get output similar to the following: (Omit line breaks)

result

{1: 4, 2: 3, 3: 4, 4: 4, 5: 3, 6: 3, 7: 2, 8: 4, 9: 3, 10: 4, 
 11: 5, 12: 3, 13: 2, 14: 2, 's': 1, 't': 5}

Now you can see the "generation" of each node = intersection when s is the first generation. It's a value that can be used as an index to say, "How many times should I get lost before I get there?"

Search for the shortest path in this graph (naive Dijkstra's algorithm)

In the original book, we calculate with directed graphs, but if you think of undirected graphs as graphs with edges in both directions, you can apply Dijkstra's algorithm in exactly the same way. Here we want to calculate the shortest distance from s to t with a naive Dijkstra algorithm that is easy to implement.

Dijkstra.py

#Calculated by Dijkstra's algorithm for the shortest cost route
costs = {}
# costs[v] = (cost, prev, used)Pair of
for v in verts:
    costs[v] = (float("inf"),0,0)
costs['s'] = (0,-1,0)

queue = list()
queue.append('s')
while len(queue) > 0:
    t = queue.pop(0)
    costs[t] = (costs[t][0], costs[t][1], 1)
    for n in neighbor[t]:
        if costs[n][2] == 0 and costs[n][0] > neighbor[t][n] + costs[t][0]:
            costs[n] = (neighbor[t][n] + costs[t][0], t, 0)
    #It will be faster if you devise a way to put it in the queue, but here I will only put one lowest value in the queue
    mincost = float("inf")
    minv = 's'
    for v in verts:
        if mincost > costs[v][0] and costs[v][2] == 0:
            mincost = costs[v][0] 
            minv = v
    if minv != 's':
        queue.append(minv)

result

{1: (13, 2, 1),
 2: (9, 7, 1),
 3: (17, 6, 1),
 4: (7, 9, 1),
 5: (9, 13, 1),
 6: (9, 7, 1),
 7: (7, 's', 1),
 8: (8, 9, 1),
 9: (6, 14, 1),
 10: (10, 6, 1),
 11: (9, 8, 1),
 12: (6, 14, 1),
 13: (7, 's', 1),
 14: (3, 's', 1),
 's': (0, -1, 1),
 't': (20, 4, 1)}

A fairly good implementation around the queue, but it returns the correct result as it appends only one vertex with the lowest cost each time it is processed. The output result is, for example, (20, 4, 1) when you look at the't' line, but the distance (steps) to the goal is 20, and the previous intersection is "4". It means that it is the place represented by. By following this, you can see not only the distance but also the shortest path itself. I'm happy.

By the way, when I wrote this article for the first time, I seriously tried using Python and thought about the following.

――It's quite easy to use tuples --It's very rough to access tuples with [0] or [2](it doesn't mean that Python is bad).

I wondered if it should be properly defined as something structural when it is used like a proper structure instead of a combination with for.

The end

Other algorithms will be omitted for the time being. You can apply the Floyd-Warshall method or the Prim method for this graph, but I thought it would be better to spend some time on chapters 7 and 8 and then think about it if you can afford it. It was.

By the way, there are other articles in this series as follows. Bucket sort and n log n wall-Supplement to Chapter 4 of Algorithm Quick Reference- * Ruby Division of search and calculation-Supplement to Chapter 5 of Algorithm Quick Reference- * Python [This article →] Solving the maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference- * Python Ford-Fulkerson method and its application --Supplement to Chapter 8 of Algorithm Quick Reference- * Python