Durchsuche das Labyrinth mit dem Python A * -Algorithmus

Was ist der A * -Algorithmus?

• Suchalgorithmus
• Es ist schnell, weil es keine vollständige Suche ist
• Als Voraussetzung müssen der Startpunkt und der Zielpunkt festgelegt sein (nicht bewegend)
• Berechnen Sie den vorhergesagten Wert vom Start bis zum Ziel (die Entfernung zwischen zwei Punkten anhand der euklidischen Entfernung oder der Manhattan-Entfernung).
• Der euklidische Abstand kann durch den Drei-Quadrat-Satz abgeleitet werden. Es gibt auch einen Teil des Quellcodes, der den Drei-Quadrat-Satz codiert.
• Für die obigen Details beziehen Sie sich bitte auf den Kommentar aus der Def-Heuristik (Selbst, Position, Zielkoordinaten).
• Durch Berechnung des vorhergesagten Werts suchen wir, während wir berechnen, welcher der Kandidatenpfade der kürzeste ist, um das Ziel zu erreichen.
• Der vorhergesagte Wert ist ein Bild des Kompasses zum Ziel.

qiita Algorithm.py

import heapq

class CalculationAStarAlgorithm():
    def __init__(self, dungeon, start_charactor, goal_charactor):
        self.dungeon = dungeon
        self.start_charactor_position = self.getCharacotorCoordinates(start_charactor)
        self.goal_charactor_position = self.getCharacotorCoordinates(goal_charactor)

    def getCharacotorCoordinates(self, search_criteria_charactor):
        for index_height, line in enumerate(self.dungeon):
            for index_wedth, charactor in enumerate(line):
                if charactor == search_criteria_charactor:
                    return (index_height, index_wedth)

    def heuristic(self, position):
        return ((position[0] - self.goal_charactor_position[0]) ** 2 + (position[1] - self.goal_charactor_position[1]) ** 2) ** 0.5

    def distance(self, path):
        return len(path)

    def nextCandidatePosition(self, last_passed_position):
        wall = "*"
        vertical_axis, horizontal_axis = last_passed_position
        for next_vertical, next_horizontal in zip((vertical_axis + 1, vertical_axis - 1, vertical_axis, vertical_axis), (horizontal_axis, horizontal_axis, horizontal_axis + 1, horizontal_axis - 1)):
            if self.dungeon[next_vertical][next_horizontal] != wall:
                yield (next_vertical, next_horizontal)

    def aStarAlgorithm(self):
        passed_list = [self.start_charactor_position]
        init_score = self.distance(passed_list) + self.heuristic(self.start_charactor_position)
        checked = {self.start_charactor_position: init_score}
        searching_heap = []
        heapq.heappush(searching_heap, (init_score, passed_list))

        while len(searching_heap) > 0:
            score, passed_list = heapq.heappop(searching_heap)
            last_passed_position = passed_list[-1]
            
            if last_passed_position == self.goal_charactor_position:
                return passed_list
            for position in self.nextCandidatePosition(last_passed_position):
                new_passed_list = passed_list + [position]
                position_score = self.distance(new_passed_list) + self.heuristic(position)
                if position in checked and checked[position] <= position_score:
                    continue
                checked[position] = position_score
                heapq.heappush(searching_heap, (position_score, new_passed_list))
        return []

    def renderPath(self, path):
        structure = [[dungeon_dot for dungeon_dot in element] for element in self.dungeon]
        for dot in path[1:-1]:
            structure[dot[0]][dot[1]] = "$"
        structure[path[0][0]][path[0][1]] = "S"
        structure[path[-1][0]][path[-1][1]] = "G"
        return ["".join(l) for l in structure]

if __name__ == '__main__': 

    dungeon = [
        '**************************',
        '*S* *                    *',
        '* * *  *  *************  *',
        '* *   *    ************  *',
        '*    *                   *',
        '************** ***********',
        '*                        *',
        '** ***********************',
        '*      *              G  *',
        '*  *      *********** *  *',
        '*    *        ******* *  *',
        '*       *                *',
        '**************************',
        ]

    calculation = CalculationAStarAlgorithm(dungeon, "S", "G")
    path = calculation.aStarAlgorithm()

    if len(path) > 0:
        print("\n".join(calculation.renderPath(path)))
    else:
        print('failed')

Referenz

https://qiita.com/masashi127/items/0c794e28f4b295ad82c6