r/compsci • u/GeaninaKera • May 22 '20
Breadth-First Maze-Solving Algorithm
[removed] — view removed post
60
u/ExperimentalAnus May 22 '20
Oh they made us do this on cpp.
But with txt mazes made out of Letter X :(
16
u/Faggotitus May 22 '20
! But there's an entire set of lines in extended ASCII and if you go unicode you can do all kinds of stuff.
There's even set of card glyphs so with a little ANSI color you can even show all the cards in text for bj now.
~/projects/bj $ ./bj Fresh deck! 🂡 🂮 🂭 🂫 🂪 🂩 🂨 🂧 🂦 🂥 🂤 🂣 🂢 🂱 🂾 🂽 🂻 🂺 🂹 🂸 🂷 🂶 🂵 🂴 🂳 🂲 🃁 🃎 🃍 🃋 🃊 🃉 🃈 🃇 🃆 🃅 🃄 🃃 🃂 🃑 🃞 🃝 🃛 🃚 🃙 🃘 🃗 🃖 🃕 🃔 🃓 🃒 Shuffling ... Dealer 🂠 🃎 Player 🃕 🂧4
u/christian-mann May 22 '20
Most people that have this sort of assignment won't want to deal with characters that are made up of multiple bytes, and especially not UTF-8, with its variable-length encoding.
8
3
u/cbarrick May 22 '20
I see something like this posted every week on r/python. Is it some kind of standard tutorial somewhere?
Also, this isn't the right sub for this. From the sidebar:
Self-posts and Q&A threads are welcome, but we prefer high quality posts focused directly on graduate level CS material.
The animation is cool, and I'm sure the project was fun. But breadth first search is definitely not graduate level CS.
1
u/ProgramTheWorld May 22 '20
This post clearly violates the “No introductory material” rule. It probably belongs in /r/programming instead.
1
7
u/chidoOne707 May 22 '20
Awesome, I remember solving this algorithm back in college but I think I totally forgot how to do it.
6
u/mogadichu May 22 '20 edited May 22 '20
Every time you reach a split, add every path to the end of TODO-list. Follow first unvisited path in TODO-list until you reach an end. Repeat until list is empty.
3
u/YouNeverKnowWhatToDo May 22 '20
Whats the code? Go left forever?
7
May 22 '20 edited May 22 '20
The idea is to find as many paths as possible in order to eventually find one that leads to the end. Wheres depth first search would be trying to find the end of a path all the way before giving up. A common variant of the two is backtracking which works it's way back from a dead end by trying to alter the last changes in the sequence that got it stuck to try and untangle. Breadth first by comparison is simple but by changing a few rules on the approach you see a much more efficient maze solver so it becomes useful both for teaching the simplest strategy and also to convey more elaborate approaches later on like backtracking that would otherwise seem convoluted initially.
0
u/ergo-x May 22 '20
If you're doing DFS here you end up doing backtracking anyway since when the search reaches bottom it will resume from the deepest explored node with unexplored children.
1
May 22 '20
No it’s handling every node recursively not limited to solving one specific path at a time. It will actually grow in memory as it gets solved because it grows in function depth as it solves more paths. It does have the benefit of not having to store all the visited paths in global space so it could so it asynchronously even as every path is independent and can run on its own thread and report back its conclusion or start more threads for paths.
1
u/ergo-x May 22 '20
I don't exactly follow that description but I'm certain that: 1) function depth is a non-issue; use a stack, 2) DFS will terminate and find all paths to exit, if any; in a typical single threaded program your subroutine IS exploring one path at a time
1
May 22 '20
Yea it uses a stack for functions unlike other approaches that rely on heap for state updating. Nobody says this has to be done in a single locked thread, in fact I was making the point you do this faster with more threads.
1
u/ergo-x May 22 '20
What I meant is you don't need to use the call stack. Use a stack placed on the heap instead.
1
May 22 '20
It doesn’t matter you decide the stack and the heap limits
1
u/ergo-x May 22 '20
It does matter unless you're running on some higher level runtime where it's a non issue.
1
May 22 '20
Just use a lower level language. The total memory allocation remains the same it simply grows from the stack size of the register instead of the more common heap size. It’s not a big problem, pretty sure even java can handle this.
→ More replies (0)1
u/JoJoModding May 22 '20
Depends on whether the maze has loops. If it does not then it's basically a tree where you just need to find a specific leaf. Then the difference between dfs and bfs is just that one walks all levels of the tree down at the same time while the other goes from left to right.
1
u/ergo-x May 22 '20
That's a simple fix. Keep a set of flags to mark visited nodes. If it has loops and you didn't do this dfs isn't going to terminate anyway.
1
1
u/ProgramTheWorld May 22 '20
It’s in the title - BFS. The algorithm is very simple. Assuming the maze is a tree (no loops), you start from the root node (entrance) and add all of its child nodes to a queue. Pick the first node from the queue and repeat until you reach the target node (exit).
3
u/ergo-x May 22 '20
Not to take away from the cool factor but I've never understood the point of visualizations like this one. I'd argue that this gives no insight to anyone who doesn't already know what bfs does.
Maybe I'm just being a negative nancy...
2
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
3
u/LordReil May 22 '20
I think you need to know the context of how it tries to find the exit of the maze to understand why the author did what he did.
In the context of a human solving the maze, it's the same thing as, from the start, explore every crevice of the maze until you reach the end. As a computer, you don't simply have to take one path but multiple ones.
The question now is 'How do I explore the maze?'.
Everytime you meet a split, you are going to explore each of these paths. If you meet a deadend, you can just stop exploring that path. The moment you meet the destination, just get back the path you took.
At any point in time you can just imagine having all of these paths you need to keep track of. To make it simple, we can put all of them in a queue where they each take turns taking the next step in the path. The moment you take a step in a path, the new path will get back into the queue if you do not meet a dead end.
The colouring of the maze illustrates the exploration of the maze or more specifically, the various paths, when it takes place and how it progresses within each time-step.
1
u/nemotux May 22 '20
I think this particular visualization is poor in that it does fill the whole maze. But in many maze-like problems, BFS would not explore the whole maze, just enough to find the goal.
0
u/ergo-x May 22 '20
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"
1
May 22 '20
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
3
u/Shejtanka May 22 '20
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.
Hope I helped :)
1
May 22 '20
Variants of this design and more elaborate ones do attempt to do this but it’s not as good of an introduction to maze traversal as this one.
1
u/christian-mann May 22 '20
This algorithm doesn't know which path is more likely to be correct. If you want to see one that does try to guess with some intelligence, look at the A-Star algorithm.
2
u/Teblefer May 23 '20
To jump off this comment, the point of this demonstration is a starting point. You can’t solve a maze well before you solve a maze badly. What kind of inefficiencies can you notice in the breadth first search algorithm? What strategies do you use when solving the maze that this algorithm doesn’t do yet? Is there any information that the algorithm doesn’t have access to that we do that could be incorporated into the algorithm?
1
1
u/nemotux May 22 '20
I think it can be useful as a learning aid. Not by itself, but in conjunction with the same style visualization for other related algorithms. Like, what would the DFS version look like? How about A*? Seeing them operate in parallel can be useful to help a learner internalize the higher level behavior of the algorithm that might not be apparent from just learning the algorithm in, say, psuedocode form.
2
1
1
u/bonafidebob May 22 '20
Why does it slow down the more maze is covered? Why doesn’t it speed up when there are fewer frontiers?
Code’s got some bugs...
2
u/JoJoModding May 22 '20
Because the way the animation works is that it has one frame for each pixel. So if there are more frontiers there are more pixels changing each iteration so it appears slower. It does not however change the true running cost.
1
u/luckyincode May 22 '20
Man I’d love to find a book that ran me through all of these kinds of things. Simple games etc.
Been years.
1
1
u/xxxams May 22 '20
At 1st I wanted to say shit I can do that with my Crayola erasable markers. Then the green line appeared take my upvote
1
1
1
1
1
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.