Breadth-first search on Ancient Brain - "Six Degrees of Kevin Bacon"

• The "Six Degrees of Kevin Bacon" idea is the idea that most of Hollywood has either been in a movie with Kevin Bacon or in a movie with someone who was in a movie with Kevin Bacon, and so on.
• This is a JS program on the Ancient Brain platform which illustrates Breadth-first search.
• It uses some movie data to show how an algorithm would search through a search tree, looking for a path to the goal (here, a path to Kevin Bacon).

Click to run World: Breadth-first search (Kevin Bacon) at Ancient Brain.

• This is a modified port of P2_six_degrees_kevin_bacon from AI course by Daniel Shiffman.
• See his videos parts one and two.

• It uses this movie data (JSON format). Note Kevin Bacon is in the first 3 movies but not in the last 2.

• View console to see what is happening.

Code

• As with all Worlds on Ancient Brain, you can see the source code and "clone" it and edit your own version.
• In the source code you can see it starts with the start node, searches all neighbours, before those 2 steps away, before those 3 steps away, and so on. When it exits with goal node, it will have found a (joint) shortest route.
• The FIFO queue is done with a JS array and push and shift.