Interlude: A Crack in the Maze
Thus far, we've been working with mazes that are perfect: they have no loops and no inaccessible areas. Every cell in the maze is reachable from every other cell, and there is a unique path between any two cells.
Let's see what happens if we try to solve a maze that isn't perfect.
Making an Imperfect Maze
Make a copy of mazes/maze-79x23.txt and call it mazes/maze-79x23-cracked.txt. Open it in a text editor, and change the second line (the first real line after the top wall) to remove all the walls except for the exterior ones. The maze now has a shortcut that'll let us skip some of the maze.
When you're done, your maze should look like this:
# #############################################################################
# #
# # # # ### ####### ######### # # # ### ####### # ### ### ### # ### # ### # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # ### ### # # ####### ##### # # # ######### ##### # # # # # # # ##### #
# # # # # # # # # # # # # # # # # # # # # # # #
# ######### # # # # # # ### ##### ### # ### # ### ### # # # # ### ##### # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# ### # # ##### ### ### # ### # ####### # ### # ### # ##### ### ##### # ### ###
# # # # # # # # # # # # # # # # # # # # # #
# # ####### ##### ### ### # # # ##### ##### # ### ####### # # ####### ####### #
# # # # # # # # # # # # # # # # #
# ### # ####### # # ##### ####### ##### ####### ### ### ##### # ### ###########
# # # # # # # # # # # # # # # # # # #
# ####### # # ### ### # ####### # # # # # ##### ####### # # ### # ##### ##### #
# # # # # # # # # # # # # # # # # #
# # # ##### ####### ####### ##### # # ##### # ### ### ################### #####
# # # # # # # # # # # # # # # # # # #
# ### ### ### # # ### ####### ### # ######### # # # # # # # ### # ##### # ### #
# # # # # # # # # # # # # # # # # # # # #
### ### # # # # ### ### # ##### ##### # ### ####### ######### ##### ### ##### #
# # # # # # # # # # # #
############################################################################# #
Meh. Since you showed us how it should look, I'm just going to copy-and-paste the whole thing.
You do you, Goat.
Running Our Solver on the Cracked Maze
Let's try our solver on this new maze.
./amaze mazes/maze-79x23-cracked.txt
It solved it! It did meander about a bit, but it found the exit in the end.
-
Our solver will find a path to the exit if there is one.
But did it find the shortest path? I'm not sure.
-
Our solver makes no promise to find the shortest path. It just finds a path.
-
Meh. Good enough for me.
Not me! I want FEWER steps!!!??!? Wait, that doesn’t feel like my vibe… Oh, yeah— I want MORE unvisited cells!! That's better.
Partner Exercise: Discuss with Your Partner
Ponder these questions with your partner:
- Can you see alternate paths through the maze?
- Does one of them seem shorter than the path the algorithm found?
- If so, why didn't the algorithm find it?
(Don't spend too long pondering these questions, they're mostly a break from coding to think about the bigger picture. You don't need to submit anything for this part.)
-
I think I see a shorter path, and I'm convinced our algorithm won't find it because it's too greedy. It always goes as far as it can in one direction before trying another direction, so it might go way out of its way before it tries the shortcut.
-
Hey, being GREEDY is a great strategy lots of the time. But I'm always up for knowing MORE ways to do things.
-
There is a straightforward algorithm that will find the shortest path through the maze.
But that algorithm needs a queue. So our
CoordVectorclass needs some new operations.-
Meh. More work. Can't we just say good enough and call it a day?
-
We're in the home stretch. Let's do it right.
(When logged in, completion status appears here.)