+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: Off-Topic (https://forum.openredstone.org/forum-4.html)
+--- Forum: General computing and engineering (https://forum.openredstone.org/forum-66.html)
+--- Thread: My Maze solver! (/thread-11555.html)
My Maze solver! - Chibill - 01-05-2017
I am going to be dropping the video about my maze solver here.
I designed the way it works myself. And also it is writen in python.
https://www.youtube.com/watch?v=DpbpjH31EEw
RE: My Maze solver! - greatgamer34 - 01-05-2017
Very awesome Chibill!
RE: My Maze solver! - jxu - 01-06-2017
Maze solver how about a Maze Generator in Minecraft goml
RE: My Maze solver! - Chibill - 01-06-2017
Well I am implmenting it to solve mazes in MC. (Has same restictions as with pixels...)
And I want to make a Maze Gen to make my solver do.
RE: My Maze solver! - newomaster - 01-07-2017
Interesting... Generate maze-->Have human attempt maze-->show solution (if human fails to complete the maze in time?).
Your maze solving method intrigued me. Simple yet effective. I wonder what its time complexity is for an nxn maze?
Also, from what I see, since you're checking paths in a certain order, the completion time may somewhat be affected by the relative direction the exit is from the entrance. For example, hypothetically, if you choose to check in down-right-up-left order, then traveling from the bottom right of a maze to the top left would be considerably slower than travelling from top left to bottom right, since you'd always be checking against net direction of travel first. So then, is it always best to check in the direction that points most directly to the ending of the maze before trying other directions?
Another thing that might be worth looking into is noticing that as soon as you completely cut off a portion of unchecked territory (white) with "checked" territory (blue and black), you absolutely don't need to check that cut off territory anymore, so long as the ending isn't included within that territory. As an example of this principle, if you pause the video at 4:36, you can see the algorithm checking a small triangle of territory that has NO POSSIBILITY of reaching the end. The space it's checking here is surrounded by blue and the maze edge. The same principle applies again for the whole top-right portion of the maze at around 6:19. I imagine implementing code that does this might not be straightforward, and that it's basically an entirely different algorithm (heck it might end up being just as good if not worse than this one), but it sounds kinda fun. A maze is a giant convoluted tree, so think of it like trimming a tree branch: anything that's trimmed and isn't connected to a support (the ending) immediately falls off the tree. Let me know if you're interested in this idea, I'd love to brainstorm more.
RE: My Maze solver! - jxu - 01-07-2017
There's really no need to brainstorm; maze solving has been analyzed to death, almost as dead as sorting.
RE: My Maze solver! - greatgamer34 - 01-07-2017
well #rekt
RE: My Maze solver! - Chibill - 01-07-2017
Sound interesting. Mine is basically brute forcing the maze. Examining with why it can move and go till it hits a wall the back up till it can go another path. (That's why it does not like mazes that have any type of loop. Because I can trap the solver)