Rechercher le labyrinthe avec l'algorithme python A *

Qu'est-ce que l'algorithme A *?

• Algorithme de recherche
• C'est rapide car ce n'est pas une recherche complète
• Comme prémisse, le point de départ et le point de but doivent être fixes (ne bougent pas)
• Calculez la valeur prévue du début à l'objectif (la distance entre deux points en utilisant la distance euclidienne ou la distance de Manhattan).
• La distance euclidienne peut être dérivée par le théorème des trois carrés. Il existe également une partie du code source qui encode le théorème des trois carrés.
• Pour les détails ci-dessus, veuillez vous référer au commentaire de def heuristic (self, position, goal_coordinates).
• En calculant la valeur prédite, nous rechercherons tout en calculant lequel des chemins candidats est le plus court pour atteindre l'objectif.
• La valeur prédite est une image de la boussole vers l'objectif.

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')

référence

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