# A* Algorithm Implementation

Posted on July 20th, 2014 by Paul

Code from: http://www.redblobgames.com/pathfinding/a-star/introduction.html

Here for personal reference.

def heuristic(a, b): # Manhattan distance on a square grid return abs(a.x - b.x) + abs(a.y - b.y) frontier = PriorityQueue() frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost + heuristic(goal, next) frontier.put(next, priority) came_from[next] = current |