1 2 4 6 8 9
Session 4: Navigational Algorithms
:material-circle-edit-outline: 约 174 个字 :fontawesome-solid-code: 31 行代码 :material-clock-time-two-outline: 预计阅读时间 1 分钟
The World is a Graph
Graph = Set(V) + Set(E)
Navigation: Finding a path from one vertex (Vstart) to another (Vend)
Path: Set of edges (E0, E1, ..., En)
Sum(E0.cost, E1.cost, ... En.cost) is minimized
breadth first search BFS
frontier is a FIFO queue
frontier = [ start ]
visited = {}
visited[start] = True
while not frontier.empty():
current = frontier.pop(0)
for neighbor in current.neighbors():
if not visited[neighbor]:
frontier.append(neighbor)
visited[neighbor] = True
The point of BFS is to discover if you can reach some destination cell
pathfinding with BFS
BFS gives a True/False result about whether a destination cell is reachable from the starting cell
To get the path, need to save a bit more data
[!NOTE]
we want the shortest path
frontier = [ start ]
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.pop(0)
for neighbor in current.neighbors():
if neighbor not in came_from:
frontier.append(neighbor)
came_from[neighbor] = current
def get_path(start, destination, came_from):
current = destination
path = []
while current != start:
path.insert(0, current)
current = came_from[current]
path.insert(0, start) #optional
return path
The came_from dictionary can be used to find a path from ANY cell, not just the target cell
early exit
我们可以在目的地址找到后就退出，而不是等所有点都遍历完