On green flag, this will automatically generate a random maze. Press space for the AI to solve it and draw a path to the goal! Then press again to have it draw out its search process step-by-step. If you want to see the maze generation in action (rather than just drawing it instantly), check out the original project by pacificapilot. It's very satisfying to watch! Original instructions: This program automatically generates mazes. Press the flag to generate one. Every maze has a single solution. Got the basic information about this algorithm from good old Wikipedia.
Many thanks to pacificapilot for the part of the project that generates the maze, and for hosting the solving challenge. If you'd like to enter, check out their studio! https://scratch.mit.edu/studios/3790874/ This solution solves the maze with a depth-first search approach. (This is a lot like how you'd intuitively solve the maze, by following a path until you reach a dead-end, then backtracking to the last junction and trying again, and so on.) It prioritizes moves up and to the right, which tends to reduce the amount of the maze it needs to traverse. According to pacificapilot, there should always only be one solution, so the one found will also be optimal! For the graph representation, I chose a 35x35 matrix. Each cell represents a square in the maze, with a bitmask indicating which of the four directions of travel are possible from the cell. When DFS chooses a cell to explore, the cell it travels from and the one it travels to are modified so that specific edge can no longer be traversed in either direction, preventing the algorithm from getting stuck in an infinite loop. All my modifications (with the exception of a couple new backdrops) are in the 'solver' sprite. I also adjusted the maze generation to run without screen refresh, because otherwise it takes quite a while to run. More specifics on the implementation can be found by looking inside - there are comments! If there's interest, I can also make a project that gives a more in-depth visual explanation of graphs and depth-first search.
