Consider the following Maze Game Engine Library files, the Maze Description data files and the sample programs that utilizes the Maze Game Engine:
Maze Game Engine - a set of three files. You will need to look only at adapter.h because you will be calling its functions. The two other files actually do the work behind the scenes. You may but do not have to look at them. In the set of homework assignments you must use those three files as is, no modifications will be allowed.
Maze Data Files - it is not difficult but still laborous to create by hand your own Maze Data File. If you desire to create your own wolrds please look at the documentation included inside world.h.
File m_undo_redo.cpp is the only file that needs changes and is allowed to be changed in the first task. It contains simplified game engine stripped off from the automated maze searching procedures. This program has built in an undo functionality. Please inspect it before reading the tasks of this homework. You can do it by tracing use of a stack variable called UNDO through the program.
File m_solve_right.cpp is the only file that needs changes and is allowed to be changed in the second task. It contains simplified algorithm that solves the maze using the right hand algorithm. Your goal is to improve record keeping in that algorithm using stack operations so that the unnecessary parts of the solution path are eliminated. The work actually was started for you and commented out. Only two cases are left for you to solve and a few of error messages. See lecture comments for details if necessary.
Analyze the main program and add redo functionality to this program using the two already provided stacks UNDO and REDO. Actually redo is much simpler to implement that undo. You will need one more stack (already defined for you as REDO). Each time the user performs an undo operation you need to record it in the REDO stack. Then when user wants to redo an operation you simple take it from that stack and redo. Unlike in case of undo you do not need to reposition the person in the labyrinth. If the stack is empty, then there is noting to redo. In case someone makes an independent move (not a redo move) then you need to destroy all undo information because it becomes invalid. A function to do that is already provided and used for undo. In case the labyrinth is restarted both undo and redo information must be cleared. It is that simple.
Improve record keeping in that algorithm using stack operations so that the unnecessary parts of the solution path are eliminated. See lecture comments for details if necessary.
You only need to provide the source code of the modified main programs and the outputs of the running program that demostrates that your undo-redo feature works and the output for the improved right wall solver. In order to demonstrate undo-redo you may need to print the maze map with marked position, do, undo, and redo a few moves and print the maze map again. Please choose a small maze for printing for practical reasons.
If you are or became interested in mazes please visit . The m_solve_right.cpp is based on "Recursive backtracker" algorithm described on that page. The two other algorithms - "Prim's algorithm" and "Kruskal's algorithm" are used in computer aided design to route connections on printed circuit boards or inside VLSI chips.