# coding: utf-8
import heapq
import itertools
def astar(init_pos, goal):
#Routenliste zum Speichern der gesuchten Koordinaten
passed_list = [init_pos]
#Erste Punktzahl
init_score = distance(passed_list) + heuristic(init_pos)
#Speichert die gesuchten Koordinaten und die Punktzahl der Route, die diese Koordinaten erreicht hat
checked = {init_pos: init_score}
#Durchsuchen Sie den Heap, um die Routenliste und ihre Punktzahl zu speichern
searching_heap = []
#Routenliste im Suchhaufen speichern
heapq.heappush(searching_heap, (init_score, passed_list))
#Bis es unmöglich wird zu suchen
while len(searching_heap) > 0:
#Die Punktzahl ist die niedrigste unter den bisher gesuchten Routen
#Holen Sie sich die Punktzahl und Routenliste wann
score, passed_list = heapq.heappop(searching_heap)
#Zuletzt gesuchte Koordinaten
last_passed_pos = passed_list[-1]
#Gibt den Suchheap zurück, wenn die zuletzt gesuchte Koordinate das Ziel ist
if last_passed_pos == goal:
return passed_list
#Durchsuchen Sie alle Richtungen der zuletzt gesuchten Koordinaten
for pos in nexts(last_passed_pos):
#Erstellen Sie eine temporäre Liste, in der die gesuchten Koordinaten zur Routenliste hinzugefügt werden
new_passed_list = passed_list + [pos]
#Berechnen Sie die Punktzahl der temporären Liste
pos_score = distance(new_passed_list) + heuristic(pos)
#Überprüfen Sie, ob die gesuchten Koordinaten auf einer anderen Route gesucht wurden
#Wenn bereits gesucht, vergleichen Sie die vorherige Punktzahl mit der aktuellen Punktzahl
#Wenn die Punktzahl diesmal höher ist, suchen Sie nach Koordinaten in der nächsten Richtung
if pos in checked and checked[pos] <= pos_score:
continue
#Wenn die Punktzahl diesmal kleiner ist, speichern Sie sie in der Checkliste
#Speichern Sie die Punktzahl und die Routenliste im Suchhaufen
checked[pos] = pos_score
heapq.heappush(searching_heap, (pos_score, new_passed_list))
return []
if __name__ == "__main__":
dungeon = [
'OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO',
'OS O O O O O',
'O O O O O O OOOO GO',
'O O O O OOOO O O OOOO',
'OOOOOOOOOOOOOOOOOO O O O O',
'O O O O O',
'O OOO O O OOOOOOOOO O',
'O OO O OOOO O O OO O',
'O O O O O O O O',
'O OOO O O O O O',
'O O O O O',
'OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO',
]
def find_ch(ch):
for i, l in enumerate(dungeon):
for j, c in enumerate(l):
if c == ch:
return (i, j)
#Start
init = find_ch("S")
#Tor
goal = find_ch("G")
def nexts(pos):
'''Generator, der die Koordinaten in alle Richtungen aus den gesuchten Koordinaten berechnet'''
wall = "O"
for a, b in itertools.product([' + 1', ' - 1', ''], repeat=2):
if a or b:
if dungeon[eval('pos[0]' + a)][eval('pos[1]' + b)] != wall:
yield (eval('pos[0]' + a), eval('pos[1]' + b))
def heuristic(pos):
'''Ergebnis der kürzesten Entfernung von der gesuchten Koordinate zum Ziel'''
return ((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) ** 0.5
def distance(path):
'''Punktzahl der Entfernung vom Start zu den gesuchten Koordinaten'''
return len(path)
def render_path(path):
'''Ergebnisausgabe'''
buf = [[ch for ch in l] for l in dungeon]
for pos in path[1:-1]:
buf[pos[0]][pos[1]] = "*"
buf[path[0][0]][path[0][1]] = "s"
buf[path[-1][0]][path[-1][1]] = "g"
return ["".join(l) for l in buf]
path = astar(init, goal)
if len(path) > 0:
print("\n".join(render_path(path)))
else:
print('failed')
A * (A-Star) -Algorithmus in Python - Pashangos Blog Schreiben Sie dies selbst - A * mit Python - Rashiura
Recommended Posts