Skip to content

Instantly share code, notes, and snippets.

@TylerGlaiel
Created March 17, 2023 00:59
Show Gist options
  • Save TylerGlaiel/dda9c1ba073681a2add0a38aaee34ae7 to your computer and use it in GitHub Desktop.
Save TylerGlaiel/dda9c1ba073681a2add0a38aaee34ae7 to your computer and use it in GitHub Desktop.
def a_star_search(grid, start, goal, max_movement):
frontier = []
heapq.heappush(frontier, (0, start))
came_from = {start: None}
cost_so_far = {start: 0}
while frontier:
current = heapq.heappop(frontier)[1]
if current == goal:
break
for neighbor in get_neighbors(current, grid):
new_cost = cost_so_far[current] + neighbor.cost() + (1000 if neighbor.is_fire() else 0)
if new_cost - (1000 if neighbor.is_fire() else 0) <= max_movement and (neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]):
cost_so_far[neighbor] = new_cost
priority = new_cost + heuristic(goal, neighbor)
heapq.heappush(frontier, (priority, neighbor))
came_from[neighbor] = current
return came_from, cost_so_far
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment