[PYTHON] Implement the shortest path search for the maze
This article is the 20th day article of tomowarkar alone Advent Calendar 2019.
Introduction
I haven't touched on breadth-first search or depth-first search so far, but I was motivated somehow, so I wrote the shortest path search for the maze.
The content itself is something that often appears, and I haven't done anything unusual. I will write it as a memorandum and output.
Deliverables
code
def printMaze(maze):
"""Draw a maze"""
for i in range(maze["height"]):
row = maze["data"][i * maze["width"] : (i + 1) * maze["width"]]
print(" ".join(row))
def at(x, y, maze):
"""Of the maze(x, y)Returns an object of coordinates"""
return maze["data"][y * maze["width"] + x]
def setChar(x, y, char, maze):
"""Of the maze(x, y)Set the coordinate object"""
arr = list(maze["data"])
arr[y * maze["width"] + x] = char
maze["data"] = "".join(arr)
if __name__ == "__main__":
maze = {
"width": 43,
"height": 35,
"data": "###########################################S # # # ## ### ########### # ################# ### ## # # # # # # # #### ########### # # ##### ##### ### ### # ## # # # # # # # # # # ## ####### ### # ####### ### ### # ##### # ## # # # # # ###### ### ##### ### ##### ### ##### ##### ## # # # # # # # # # # # ## # # # # ### # # ### ### # ### ### # ### ## # # # # # # # # # # # # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # # # # # # # # # # ## # # # ##### ### ### ####### ### ### # # ## # # # # # # # # # # # ## # # ##### ### ### ########### ### ### # ## # # # # # # # # # ## # ##### ### # ### ### ##### # # # ### # ## # # # # # # # # # # # # # ## ##### ### # ### ##### ### ### # ### # # ## # # # # # # # #### # # ### ### ######### ### ### ### ### ## # # # # # # # # # # ## ### ### ### ##### # ### ### ####### ### ## # # # # # # # # ## ### ####### ### ### # ##### ### ### # #### # # # # # # # # # # ## # # # ### ### # ##### ##### ##### # ### ## # # # # # # # # # # # ## # # # # ### ### # # ####### ##### ### # ## # # # # # # # # # # # ## # ##### # ####### # ######### ### # ### ## # # # # # G###########################################",
}
start = [0, 1]
goal = [42, 33]
visited = [False] * maze["width"] * maze["height"]
costs = [999999] * maze["width"] * maze["height"]
#Start position(0, 1)In the queue
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0
while len(queue) > 0:
#Get a position from the queue
p, queue = queue[0], queue[1:]
visited[p[1] * maze["width"] + p[0]] = True
#Verify up, down, left and right
for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = p[0] + i[0], p[1] + i[1]
if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
continue
if at(x, y, maze) == " " and visited[y * maze["width"] + x] == False:
queue.append([x, y])
costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
if at(x, y, maze) == "G":
queue = []
costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
break
#Follow costs from the goal to find the shortest path
point = goal
cost = costs[point[1] * maze["width"] + point[0]]
while cost != 1:
for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = point[0] + i[0], point[1] + i[1]
if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
continue
if costs[y * maze["width"] + x] == cost - 1:
cost = costs[y * maze["width"] + x]
point = [x, y]
setChar(x, y, ".", maze)
break
printMaze(maze)
Commentary
Defines the maze information in a dictionary type.
" # " Is the wall " " is the passage, " S ", " G " is the start and goal respectively.
At the same time, the (x, y) coordinates of the start and goal are also entered manually.
maze = {
"width": 43,
"height": 35,
"data": "###########################################S # # # ## ### ########### # ################# ### ## # # # # # # # #### ########### # # ##### ##### ### ### # ## # # # # # # # # # # ## ####### ### # ####### ### ### # ##### # ## # # # # # ###### ### ##### ### ##### ### ##### ##### ## # # # # # # # # # # # ## # # # # ### # # ### ### # ### ### # ### ## # # # # # # # # # # # # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # # # # # # # # # # ## # # # ##### ### ### ####### ### ### # # ## # # # # # # # # # # # ## # # ##### ### ### ########### ### ### # ## # # # # # # # # # ## # ##### ### # ### ### ##### # # # ### # ## # # # # # # # # # # # # # ## ##### ### # ### ##### ### ### # ### # # ## # # # # # # # #### # # ### ### ######### ### ### ### ### ## # # # # # # # # # # ## ### ### ### ##### # ### ### ####### ### ## # # # # # # # # ## ### ####### ### ### # ##### ### ### # #### # # # # # # # # # # ## # # # ### ### # ##### ##### ##### # ### ## # # # # # # # # # # # ## # # # # ### ### # # ####### ##### ### # ## # # # # # # # # # # # ## # ##### # ####### # ######### ### # ### ## # # # # # G###########################################",
}
start = [0, 1]
goal = [42, 33]
Preparation
Define the queue and visited used for the search, and the costs used to guide the shortest path.
The maze is output as a two-dimensional array, but since all data processing is performed with a one-dimensional array, it is necessary to perform appropriate conversion.
visited = [False] * maze["width"] * maze["height"]
costs = [999999] * maze["width"] * maze["height"]
#Start position(0, 1)In the queue
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0
Search main process
Since it is a breadth-first search, we will take it out from the head of the queue and verify it. If the top, bottom, left, and right states are passages, we will add more and more to the queue. The cost update can be used to derive the shortest path by always adding +1 to the cost of the reference point.
while len(queue) > 0:
#Get a position from the queue
p, queue = queue[0], queue[1:]
visited[p[1] * maze["width"] + p[0]] = True
#Verify up, down, left and right
for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = p[0] + i[0], p[1] + i[1]
if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
continue
if at(x, y, maze) == " " and visited[y * maze["width"] + x] == False:
queue.append([x, y])
costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
if at(x, y, maze) == "G":
queue = []
costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
break
Shortest path derivation
Since cost is the same as the distance taken from the start, the shortest path can be derived by going back to 0 from the cost of the goal position.
#Follow costs from the goal to find the shortest path
point = goal
cost = costs[point[1] * maze["width"] + point[0]]
while cost != 1:
for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = point[0] + i[0], point[1] + i[1]
if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
continue
if costs[y * maze["width"] + x] == cost - 1:
cost = costs[y * maze["width"] + x]
point = [x, y]
setChar(x, y, ".", maze)
break
printMaze(maze)
result
in conclusion
I will do my best tomorrow! !! tomowarkar Alone Advent Calendar Advent Calendar 2019
reference
https://qiita.com/nati-ueno/items/a789095aff0aec10d5d0 https://vigne-cla.com/18-2/
Recommended Posts