A* Algorithm implementation in Python3.

astar.py

"""
   A* Algorithm implementation in Python.
   Written by: James Sigurðarson (jamiees2)
   Source: https://gist.github.com/jamiees2/5531924

   Modified by Rick Henderson
   May 5, 2016: Began updating to Python 3.x. Also improved spacing and comments.
     Converted xrange() to range(). Converted raw_input() to input().
"""

# Enter your code here. Read input from STDIN. Print output to STDOUT
class Node:
    def __init__(self,value,point):
        self.value = value
        self.point = point
        self.parent = None
        self.H = 0
        self.G = 0
    def move_cost(self,other):
        return 0 if self.value == '.' else 1
        
def children(point,grid):
    x,y = point.point
    links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
    return [link for link in links if link.value != '%']

def manhattan(point,point2):
    return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])

def aStar(start, goal, grid):
    #The open and closed sets
    openset = set()
    closedset = set()

    #Current point is the starting point
    current = start

    #Add the starting point to the open set
    openset.add(current)

    #While the open set is not empty
    while openset:
        #Find the item in the open set with the lowest G + H score
        current = min(openset, key=lambda o:o.G + o.H)

        #If it is the item we want, retrace the path and return it
        if current == goal:
            path = []
            while current.parent:
                path.append(current)
                current = current.parent
            path.append(current)
            return path[::-1]

        #Remove the item from the open set
        openset.remove(current)

        #Add it to the closed set
        closedset.add(current)

        #Loop through the node's children/siblings
        for node in children(current,grid):
            #If it is already in the closed set, skip it
            if node in closedset:
                continue

            #Otherwise if it is already in the open set
            if node in openset:
                #Check if we beat the G score 
                new_g = current.G + current.move_cost(node)
                if node.G > new_g:
                    #If so, update the node to have a new parent
                    node.G = new_g
                    node.parent = current
            else:
                #If it isn't in the open set, calculate the G and H score for the node
                node.G = current.G + current.move_cost(node)
                node.H = manhattan(node, goal)

                #Set the parent to our current item
                node.parent = current

                #Add it to the set
                openset.add(node)

    #Throw an exception if there is no path
    raise ValueError('No Path Found')

def next_move(pacman,food,grid):
    #Convert all the points to instances of Node
    for x in range(len(grid)):
        for y in range(len(grid[x])):
            grid[x][y] = Node(grid[x][y],(x,y))

    #Get the path
    path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)

    #Output the path
    print(len(path) - 1)
    for node in path:
        x, y = node.point
        print(x, y)        

def test_algo():
    # pacman_x and pacman_y are the x,y cooridnates for the agent
    # food_x, food_y is a grid of food locations
    # grid is a list containing the entire map / environment / gameboard
    # Input should be space seperated x y coords.
    pacman_x, pacman_y = [ int(i) for i in input().strip().split() ]
    food_x, food_y = [ int(i) for i in input().strip().split() ]
    x,y = [ int(i) for i in input().strip().split() ]
 
    grid = []
    for i in range(0, x):
        grid.append(list(input().strip()))
 
    next_move((pacman_x, pacman_y),(food_x, food_y), grid)


if __name__ == '__main__':
    test_algo()

Runs under Python3 and waits for input but I'm not sure how the input should be formatted.

Hi rick,
do you have the input values you used to test your code?
Thx

@rickhenderson https://gist.github.com/rickhenderson/7d3daf9c90e3e0582b3f8e9fa4fc25d6#file-astar-py-L28
shouldn't this be return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[1]) ? Pointed in the original gist as well in comments.

Hi rick,
do you have the input values you used to test your code?
Thx

same question!!

Sorry gang, I have no idea. I don’t write Python anymore and this isn’t my code. It’s a fork remember?