def find_path(self, start_tiles, goal_tiles):
"""
Given a list of starting locations and a list of ending locations,
find the shortest path between them. Uses a priority queue to
do Uniform Cost Search (think Breadth First Search, but with movement
cost included).
"""
open_q = [(0, tile) for tile in start_tiles]
heapq.heapify(open_q)
goals = {tile for tile in goal_tiles}
source = defaultdict(lambda: (None, 100000000))
for tile in start_tiles:
source[tile] = (tile, 0)
while open_q:
moves, working = heapq.heappop(open_q)
for neighbor in working.get_neighbors():
if neighbor in goals:
steps = [neighbor, working]
previous = working
while source[previous][0] != previous:
previous = source[previous][0]
steps.append(previous)
return list(reversed(steps))
if not pathable(neighbor):
continue
previous_tile, previous_distance = source[neighbor]
current_distance = moves + move_cost(working, neighbor)
if current_distance < previous_distance:
source[neighbor] = (working, current_distance)
heapq.heappush(open_q, (current_distance, neighbor))
return []
评论列表
文章目录
