01-07-2017, 09:03 AM
(This post was last modified: 01-07-2017, 09:41 AM by newomaster.)
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.
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.