python A*アルゴリズム で迷路探索する

A*アルゴリズムとは？

• 探索アルゴリズムです
• 全探索ではないため早いです
• 前提として、スタート地点とゴール地点が固定的（動かない）である必要があります
• スタートからゴールまでの予測値（ユークリッド距離あるいはマンハッタン距離を使用して、２点間の距離）を計算します。
• ユークリッド距離は三平方の定理で導くことができます。ソースコードの中にも、三平方の定理をコード化している箇所があります。
• 上記詳細についてはdef heuristic(self, position, goal_coordinates)　のコメントアウトの内容をご参照ください。
• 予測値を計算することで、候補となる進路のうち、どれがゴールにたどり着くために最短なのかを計算しながら探索します。
• 予測値はゴールまでの羅針盤のイメージです。

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

参考