******************************************************************************* mazeSolver.cpp Zak Walton and Nick Schrock cis263 ******************************************************************************* ***Purpose*** The purpose of this project was to write two different algorithms to solve a maze. The theoretical performance of each algorithm was analyzed and compared. ***Brute Force Algorithm*** The first algorithm that we implemented was a brute force algorithm. This algorithm runs by prioritizing the direction in which the program executes. After reading in the maze, the algorithm will first try going right. If it encounters a wall, it will then try going up, then down, then left. If none of these directions work, it is understood that the path has reached a dead end. At this point, the algorithm will backtrack. The backtracking is lower in priority than the general directions and is done by saving each move in a stack. When backtracking is necessary, the latest move is popped of the top of the stack and the program then reverts back one step. When backtracking is executed, the program leaves breadcrumbs to represent that it has already been there. With this algorithm, the program will wind its way around the maze until it reaches the finishing point. This is a brute force approach because the algorithm does not optimize the path to the finish in anyway, it simply prioritizes the direction taken while keeping track of where the dead ends are until it inevitably reaches the finish. The big O notation for this implementation is O(n^2). In the worst case scenario, the algorithm will have to try and backtrack at every junction on the maze before it reaches the finish. This behavior equates to an n^2 big O. ***Randomized Algorithm*** The second algorithm that we implemented was a randomized algorithm. This algorithm moves straight when it has two or four open directions to move, and it randomly picks a new direction when it has one or three open directions to move. The moves are all stored on a stack, so that if the algorithm directly backtracks, like if it goes down a dead end path, it pick back up where it's been. All of the cookie crumbs are added to the maze from the stack after it finds the solution. The Random algorithm always finds a solution, and for all of the sample graphs that we tested the have a solution, it finds it pretty fast. We were unable to analyze the actual timing for the random algorithm because it solved all of the mazes so fast. You can't really determine a bit O for this algorithm either because it randomly choses which directions to go. A larger maze on average obviously takes longer than a smaller one, but you can't really put a number to it. The speed is also affected by the number of decision points in the maze. The more decision points, the longer the algorithm takes, on average. If a graph is very large but has very few decision points, the algorithm doesn't take long at all. ***Sample Output*** zacharywalton@Zacharys-MacBook-Pro:~/cis263/project2$ ./mazeSolver Reading a 20 by 20 matrix. ******************** *******S ******** ***** *** **** *** * ** **** * ****** *** * ****************** * **************** *** *********F*** * * ***** *** * ******* ***** *** ** ***** *** *** ** ****** *** ***** ** *** *** ***** ****** * ***** * ******* ***** *** ***** *** *** **** *** ***** *** **** **** *** ********* ***** ******************** 1.43814e+09 1.43814e+09 Brute force distance: 87 units away! Brute force time: 0.000730991 ms ******************** *******Soooo******** *****ooo***ooooo**** ***ooo*oooooo**o**** *ooooo******oooo *** *o****************** *ooo**************** ***oooo*********F*** * *ooooo*****o*** * *******o*****o*** ** *****o***ooo*** ** ******o***o***** ** ***o***o***** ******ooooo *o***** * ooo*******o***** *** o***** ***ooo*** ****o*** *****o*** ****oooooo****ooo*** *********oooooo***** ******************** Randomized distance: 200 units away! Randomized time: 0.000730991 ms ******************** *******S<<<^******** *****<<>***v<<<>**** ***<>>*v>>>vv**^**** *<<<<v******v>>> *** *v****************** *v>>**************** ***<< *********F*** *^<vv* *****^*** *<v******* *****^*** **v^ ***** ***<>>*** **v>****** ***^***** ** <>>^*** ***^***** ******< *^***** * ^<>*******^***** *** v***** ***v<^*** ****v***^^ *****^*** ****v>>>vv****<>>*** *********<>>>>v***** ********************