Breadth First Pathfinding

Read Time:1 Minute, 11 Second

First Attempt

Ok, so I already know the wave algorithm for shortest path, so I plugged it in prior to watching the video. Let’s see how it compares:

This particular algorithm starts at the end point and sets the neighbors. It requires hitting all elements in the dictionary for each exploration value until all waypoints have an exploration value set.


Ben’s Algorithm

Here’s what I think Ben is about to do in video 136:
How did I know? The next lesson is about Queues.

From the looks of it, the path will ultimately be built backwards from the destination looking for the grid position with the least exploration value.

So this is a recursive method that takes as its first input the end point. The waypoint is inserted into the front of the path List. My waypoints have an exploration value attached and the shortest path is found by looking for the adjacent waypoint equal to the next smallest value.

Output from the breadth first algorithm.

You can see that I added a second label to the cubes. The cubes labeled -1 were never explored because the algorithm was cut off at 3, though you’ll note that the value to the left of 3,2 is a 4. I did set all neighbors of the end point that were not already set so that I could use the less than operator to build the path.

Happy
Happy
0 %
Sad
Sad
0 %
Excited
Excited
0 %
Sleppy
Sleppy
0 %
Angry
Angry
0 %
Surprise
Surprise
0 %

Average Rating

5 Star
0%
4 Star
0%
3 Star
0%
2 Star
0%
1 Star
0%

Leave a Reply

Your email address will not be published. Required fields are marked *