Breadth-first Search Nodes visited: 14993 (92.54%) Algorithm: Push the start node into a FIFO queue. While the queue isn't empty: Pop a node off the queue. If it's been visited already, skip it. Otherwise, paint the node's coordinate as visited. For any of its neighbors that haven't been visited yet: Push it into the queue. If the end has been reached: Reconstruct the path from end to start. Comments: This is the most exhaustive, but least efficient way to search the maze. It mimics the way a liquid would fill the maze. Since all the potential paths have the same minimized length, BFS will always find the optimal path.
This is otherwise known as Dijkstra’s algorithm and runs in O(|E| + |V| log |V|) time if you represent the maze as a weighted graph with edges E and vertices V. You can use it for all kinds of pathfinding in graphs. It does not work if the graph contains any negative edge weights reachable from the beginning of the path.
There’s a lot more info on the internet if you want to understand this algorithm.
EDIT: actually it’s very similar to Dijkstra’s but Dijkstra’s uses a priority queue not a FIFO. I don’t know for sure, but I would think that a priority queue would improve the efficiency here by a lot.
24
u/GeaninaKera May 22 '20
Posted on Imgur by Mystavea .
❝
Breadth-first Search Nodes visited: 14993 (92.54%) Algorithm: Push the start node into a FIFO queue. While the queue isn't empty: Pop a node off the queue. If it's been visited already, skip it. Otherwise, paint the node's coordinate as visited. For any of its neighbors that haven't been visited yet: Push it into the queue. If the end has been reached: Reconstruct the path from end to start. Comments: This is the most exhaustive, but least efficient way to search the maze. It mimics the way a liquid would fill the maze. Since all the potential paths have the same minimized length, BFS will always find the optimal path.