Pathfinding with BFS

little hard :/, but just a little:)

Paths

  • Path: A sequence of nodes with each adjacent pair of nodes connected by an edge
  • The length of a path is the number of edges it contains (number of nodes - 1)
  • [LINCOLN, MIT, UTAH, SDC, RAND, UCSB, SRI] <– Path of length 6

Distance

  • Distance between two nodes: The lenght of the shortest path between the nodes
  • Distance between LINCOLN and SRI == 3 [See the video]
  • Distance between RAND and BBN == 1 [See the video]

Use BFS to find the diatance between nodes

Track the shortest path for pathfinding

There’s Levels to This

  • Let’s run through BFS again
    • Instead of just finding the connected component, let’s track the paths taken to explore each node

  • Let’s start at CARNEGIE this time [Se the video]
  • Keep track of all edges used to explore new nodes
  • Redraw the graph with only these edges
  • Explore all neighbors of the starting node
  • Explore al neighbors of the nodes explored in the last step
  • Repeat
  • Choose edge to use for MIT arbitrarily
  • Each step we explore all nodes that can be reached from the nodes added in the previous step
  • We have a new graph with a few edges removed
  • This graph is a tree (no cycles)
  • And it has levels!

  • Number the levels starting with 0
  • The levle number == the distance from the starting node to any node in that level

BFS and Distacne

  • But how do we track the levels?
  • Track levels in a data structure

  • But don’t we want to find the shortest path for the Maze HW?
    • Not just the length of the shortest path

  • Instead of tracking the distacne, track the node that discovered each node
  • Now each node remembers how it was reached
  • Repeat at each step
  • At the end of the algotrithm you’ll know how each node was discovered
  • Work backwards to buld the shortest path
  • Find path from CARNEFIE to STANFORD

But we have to find path in a maze

how do graph help with this?

Pathfinding on a Grid

  • Convert the maze to a graph
  • Run BFS starting at the tile containing the maze runner
  • Backtrack from the goal tile to build the path

Lecture Question

Task:
Find the distance between two nodes in a graph

  • In the week9.Graph class link to example repo
    • Write a method named distance that takes two node indices (Ints) and returns the distance between the two nodes
    • You may assume the two input nodes are connected

Testing:
In a package named “tests” create a class named “TestDistance” as a test suite that tests the functionality listed above