Maze_ICS46_Winter2022

As a very young kid, I found myself fascinated by mazes. Whenever I saw a maze printed on a piece of paper, I was compelled to grab it and try to solve it. I recall having soft-covered books full of them and, when those weren't satisfying enough, I even tried drawing my own, though with the undeveloped skills I had at the time — both in terms of being able to design a challenging maze, and also the more fundamental skill of being able to draw a straight line — it proved to be a difficult proposition. While time marched on and I became less enamored with mazes as I got older, I became more interested in computer science, which provided a fresh impetus to consider mazes again; in particular, I considered how software could generate a challenging maze and also figure out automatically how to solve one. As I learned more about computer science, the solutions became evident, and I eventually found it an interesting problem for my students to solve. It's funny how things come full-circle sometimes. This project asks you to implement one or more classes in C++ that are capable of generating two-dimensional mazes of arbitrary size, along with one or more classes in C++ that are capable of solving them. The goal is to provide you with more practice and a fuller understanding of how to use recursion to solve real problems, as at least one of your generators and at least one of your solvers is required to use a recursive depth-first algorithm. It will also provide you with an opportunity to make heavy use of pre-existing classes for which you have no source code, and for which only part of it will have value to you; understanding how existing code works and determining what parts of it can be applied to solve your own problems are important real-world programming skills that you'll need to employ as you move from "sanitized" coursework to real-world work, so I'd like to help you to develop those skills here.