A * algorithm (Python edition)

background

-[CheckIO](https://www.google.co.jp/url?sa=t&rct=j&q=1esrc=s&source=web&cd=1&cad=rja&uact=8&sqi=2&ved=0CCcQFjAA&url=http%3A%2F%2Fwww.checkio .org% 2F & ei = 7tBQU53sBI7f8AXrvYDoDQ & usg = AFQjCNGXsrpQkb4DEb4j2GPoN8yXZBOSYA & bvm = bv.65058239, d.dGc) I studied because there are many problems of route search.

code

# coding: utf-8
import heapq
import itertools


def astar(init_pos, goal):
    #Route list that stores the searched coordinates
    passed_list = [init_pos]
    #Initial score
    init_score = distance(passed_list) + heuristic(init_pos)
    #Stores the searched coordinates and the score of the route that reached those coordinates
    checked = {init_pos: init_score}
    #Search heap to store route list and its score
    searching_heap = []
    #Store route list in search heap
    heapq.heappush(searching_heap, (init_score, passed_list))
    #Until it becomes impossible to search
    while len(searching_heap) > 0:
        #The score is the lowest among the routes searched so far
        #Get the score and route list when
        score, passed_list = heapq.heappop(searching_heap)
        #Last searched coordinates
        last_passed_pos = passed_list[-1]
        #Returns the search heap if the last searched coordinate is the destination
        if last_passed_pos == goal:
            return passed_list
        #Search all directions of the last searched coordinates
        for pos in nexts(last_passed_pos):
            #Create a temporary list with the coordinates being searched for added to the route list
            new_passed_list = passed_list + [pos]
            #Calculate the score of the temporary list
            pos_score = distance(new_passed_list) + heuristic(pos)
            #Check if the coordinates being searched have been searched by another route
            #If already searched, compare the previous score with the current score
            #If the score this time is higher, go to the search for coordinates in the next direction.
            if pos in checked and checked[pos] <= pos_score:
                continue
            #If the score this time is smaller, store it in the checked list
            #Store score and route list in search heap
            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")
    #goal
    goal = find_ch("G")

    def nexts(pos):
        '''Generator that calculates the coordinates of all directions from the coordinates being searched'''
        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):
        '''Score of the shortest distance from the coordinates being searched to the goal'''
        return ((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) ** 0.5

    def distance(path):
        '''Score of the distance from the start to the coordinates being searched'''
        return len(path)

    def render_path(path):
        '''Result output'''
        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')

reference

A * (A-Star) algorithm in Python --Pashango ’s Blog Write this for yourself --A * in python --Rashiura