In this program, pacman will find paths through the maze world to either reach a particular location or find food in the most efficent way. The user may select three searches: Depth First Search, Breadth First Search, and A* Search.
The graph search version of Depth First Search is implemented. This version will avoid expanding states that have already been visited.
Depth First Search should be able to find paths for the following:
python pacman.py -l tinyMaze -p SearchAgent
python pacman.py -l mediumMaze -p SearchAgent
python pacman.py -l bigMaze -z .5 -p SearchAgent
The graph search version of Breadth First Search is implementing, so states that have already been visited will not be expanded. BFS can be tested by running the following commands:
python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5
A* takes a heuristic function as an argument. This implementation uses the Manhattan Distance as the heuristic. The algorithm can be tested using the following:
python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
python pacman.py -l mediumCorners -p SearchAgent -a fn=aStarSearch,prob=CornersProblem,heuristic=cornersHeuristic -z 0.5