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.
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.
0
0
Average Rating