Mettre en œuvre la recherche de chemin le plus court pour le labyrinthe
Cet article est l'article du 20e jour du Calendrier de l'Avent Tomowarkar Alone 2019.
introduction
La recherche de priorité de largeur et la recherche de priorité de profondeur semblent être difficiles, donc je n'y ai pas beaucoup parlé, mais j'étais motivé d'une manière ou d'une autre, alors j'ai écrit la recherche d'itinéraire la plus courte pour le labyrinthe.
Le contenu lui-même est quelque chose qui apparaît souvent, et je n'ai rien fait d'inhabituel. Je vais l'écrire sous forme de mémoire et de résultat.
Livrables
code
def printMaze(maze):
"""Dessine un labyrinthe"""
for i in range(maze["height"]):
row = maze["data"][i * maze["width"] : (i + 1) * maze["width"]]
print(" ".join(row))
def at(x, y, maze):
"""Du labyrinthe(x, y)Renvoie un objet de coordonnées"""
return maze["data"][y * maze["width"] + x]
def setChar(x, y, char, maze):
"""Du labyrinthe(x, y)Définir l'objet de coordonnées"""
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"]
#La position de départ(0, 1)Faire la queue
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0
while len(queue) > 0:
#Obtenir la position de la file d'attente
p, queue = queue[0], queue[1:]
visited[p[1] * maze["width"] + p[0]] = True
#Vérifiez en haut, en bas, à gauche et à droite
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
#Suivez les coûts de l'objectif pour trouver l'itinéraire le plus court
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)
Commentaire
Les informations du labyrinthe sont définies comme un type de dictionnaire.
" # " Est-ce que le mur "" "est le passage," S ", " G "est respectivement le départ et le but. En même temps, les coordonnées(x, y)` du départ et de l'objectif sont également entrées manuellement.
maze = {
"width": 43,
"height": 35,
"data": "###########################################S # # # ## ### ########### # ################# ### ## # # # # # # # #### ########### # # ##### ##### ### ### # ## # # # # # # # # # # ## ####### ### # ####### ### ### # ##### # ## # # # # # ###### ### ##### ### ##### ### ##### ##### ## # # # # # # # # # # # ## # # # # ### # # ### ### # ### ### # ### ## # # # # # # # # # # # # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # # # # # # # # # # ## # # # ##### ### ### ####### ### ### # # ## # # # # # # # # # # # ## # # ##### ### ### ########### ### ### # ## # # # # # # # # # ## # ##### ### # ### ### ##### # # # ### # ## # # # # # # # # # # # # # ## ##### ### # ### ##### ### ### # ### # # ## # # # # # # # #### # # ### ### ######### ### ### ### ### ## # # # # # # # # # # ## ### ### ### ##### # ### ### ####### ### ## # # # # # # # # ## ### ####### ### ### # ##### ### ### # #### # # # # # # # # # # ## # # # ### ### # ##### ##### ##### # ### ## # # # # # # # # # # # ## # # # # ### ### # # ####### ##### ### # ## # # # # # # # # # # # ## # ##### # ####### # ######### ### # ### ## # # # # # G###########################################",
}
start = [0, 1]
goal = [42, 33]
Préparation
Définissez «file d'attente» et «visité» utilisés pour la recherche, et «coûts» utilisés pour guider l'itinéraire le plus court.
Le labyrinthe est sorti sous la forme d'un tableau bidimensionnel, mais tout le traitement des données est effectué avec un tableau unidimensionnel, il est donc nécessaire d'effectuer une conversion appropriée.
visited = [False] * maze["width"] * maze["height"]
costs = [999999] * maze["width"] * maze["height"]
#La position de départ(0, 1)Faire la queue
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0
Recherche processus principal
Puisqu'il s'agit d'une recherche de priorité de largeur, nous la retirerons de la tête de la file d'attente et la vérifierons. Si l'état haut, bas, gauche et droite est un passage, il sera de plus en plus ajouté à la file d'attente. La mise à jour des coûts peut être utilisée pour dériver l'itinéraire le plus court en ajoutant toujours +1 au coût du point de référence.
while len(queue) > 0:
#Obtenir la position de la file d'attente
p, queue = queue[0], queue[1:]
visited[p[1] * maze["width"] + p[0]] = True
#Vérifiez en haut, en bas, à gauche et à droite
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
Dérivation de l'itinéraire le plus court
Puisque le «coût» est le même que la distance prise depuis le départ, l'itinéraire le plus court peut être dérivé en retournant à 0 à partir du coût de la position cible.
#Suivez les coûts de l'objectif pour trouver l'itinéraire le plus court
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)
résultat
en conclusion
Je ferai de mon mieux demain! !! Tomowarkar Alone Advent Calendar Advent Calendar 2019
référence
https://qiita.com/nati-ueno/items/a789095aff0aec10d5d0 https://vigne-cla.com/18-2/
Recommended Posts