Search the maze with the python A * algorithm

What is an A * algorithm?

• Search algorithm
• It is fast because it is not a full search
• As a prerequisite, the start point and goal point must be fixed (not moving).
• Calculate the predicted value from the start to the goal (distance between two points using the Euclidean distance or Manhattan distance).
• The Euclidean distance can be derived by the three-square theorem. There is also a part of the source code that encodes the three-square theorem.
• For the above details, please refer to the commented out contents of def heuristic (self, position, goal_coordinates).
• By calculating the predicted value, we will search while calculating which of the candidate paths is the shortest to reach the goal.
• The predicted value is an image of the compass to the goal.

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

reference

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