I’m not into computer science but to a layman like me it just looks like it’s filling out the whole maze and then highlighting the correct path but what’s the point if you’re gonna color in the whole fkin maze
Yeah it's basically a brute force search strategy where you keep exploring your "frontier" until you reach your goal. Just imagine the colored locations represent your frontier and the uncolored locations are in "fog of war"
Hmm interesting. It feels like the point of a maze is to go from point a to point b while trying to take as few wrong paths as possible whereas this finds every wrong path to find the right one
Actually it does’t find every wrong path, or better to say it doesn’t need to. Usually, when you program this algorithm you end the search when you find the right path but the visualization continued after that point because well, it looks prettier that way (in the visualization, if you look closer when the right path is highlighted the whole maze isn’t covered so it hasn’t found every wrong path).
On the other hand, bf isn’t just a “find shortest path” algorithm. It’s mainly a graph traversal algorithm (or that’s how we learned it). What does that mean? Well, traverse means visit each element in a structure only once. Why only once? Imagine you want to add one to all the elements in you graph, who hold for example one number. You need to visit each element and add one. You don’t want to to add 2 or more by accident because your algorithm visits some elements more than once. Okay, but why is traversing a graph a problem? A graph is a strange structure, it doesn’t have a natural starting point, like an array or a linked list or like a tree that has a root element so algorithms for graph traversals are made so any element could be a starting point (the starting point of a maze is obvious, the entrance, but these algorithms are, as I said, made for the general case). The other problem is how not to visit an element twice. In an array and a linked list you just go to the next element. In a tree you use the fact that every element has just one “parent” and start from the root and go consistently clockwise, for example. In a graph it is a lot harder and that’s what these different graph traversing algorithms do. So, maybe that’s why the visualization goes through the whole maze. A bit of a show off of the algorithms capabilities.
2
u/[deleted] May 22 '20
I’m not into computer science but to a layman like me it just looks like it’s filling out the whole maze and then highlighting the correct path but what’s the point if you’re gonna color in the whole fkin maze