Skip to content

In this project, the Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. I implemented general search algorithms such as depth-first, breadth-first, uniform cost, and A* search algorithms which are used to solve navigation problems in the Pacman world.

Notifications You must be signed in to change notification settings

ma-shamshiri/Pacman-Game

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 

Repository files navigation

Pacman Logo

Pacman Agent

COMP 6721 - Artificial Intelligence

Project Assignment 1 - Concordia University (Winter 2020)

Animated gif pacman game

📖 Table of Contents

Table of Contents
  1. ➤ About The Project
  2. ➤ Overview
  3. ➤ Project Files Description
  4. ➤ Getting Started
  5. ➤ Scenario 1: Depth First Search
  6. ➤ Scenario 2: Breadth First Search
  7. ➤ Scenario 3: Uniform Cost Search
  8. ➤ Scenario 4: A* search algorithm
  9. ➤ Scenario 5: Finding All Corners
  10. ➤ Scenario 6: Admissible and Consistent Heuristic
  11. ➤ Scenario 7: Eating All Dots
  12. ➤ Scenario 8: Suboptimal Search
  13. ➤ References
  14. ➤ Credits

-----------------------------------------------------

📝 About The Project

For those of you not familiar with Pacman, it's a game where Pacman (the yellow circle with a mouth in the above figure) moves around in a maze and tries to eat as many food pellets (the small white dots) as possible, while avoiding the ghosts (the other two agents with eyes in the above figure). If Pacman eats all the food in a maze, it wins.

-----------------------------------------------------

☁️ Overview

In this project, the Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. I implemented general search algorithms such as depth-first, breadth-first, uniform cost, and A* search algorithms which are used to solve navigation problems in the Pacman world.

-----------------------------------------------------

💾 Project Files Description

  • search.py - Where all of the search algorithms reside.
  • searchAgents.py - Where all of the search-based agents reside.
  • pacman.py - The main file that runs Pacman games. This file also describes a Pacman GameState types.
  • game.py - The logic behind how the Pacman world works.
  • util.py - Useful data structures for implementing search algorithms.

Some other supporting files

  • graphicsDisplay.py - Graphics for Pacman.
  • graphicsUtils.py - Support for Pacman graphics.
  • textDisplay.py - ASCII graphics for Pacman.
  • ghostAgents.py - Agents to control ghosts.
  • keyboardAgents.py - Keyboard interfaces to control Pacman.
  • layout.py - Code for reading layout files and storing their contents.
  • autograder.py - Project autograder.
  • testParser.py - Parses autograder test and solution files.
  • testClasses.py - General autograding test classes.
  • test_cases/ - Directory containing the test cases for each scenario.
  • searchTestClasses.py - Project specific autograding test classes.

-----------------------------------------------------

📖 Getting Started

You are able to start the game by typing the following commands in the command line:

$ python pacman.py

You can see the list of all options and their default values via:

$ python pacman.py -h
Note that all of the commands that appear in this project also appear in commands.txt, for easy copying and pasting.

-----------------------------------------------------

🔸 Scenario 1: Finding a Fixed Food Dot using Depth First Search

I have implemented the depth-first search (DFS) algorithm in the depthFirstSearch function in search.py.

The Pacman will quickly find a solution via running the following commands:

$ python pacman.py -l tinyMaze -p SearchAgent
$ python pacman.py -l mediumMaze -p SearchAgent
$ python pacman.py -l bigMaze -z .5 -p SearchAgent

Animated gif DFS Algorithm

-----------------------------------------------------

🔸 Scenario 2: Finding a Fixed Food Dot using Breadth First Search

I have implemented the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py.

I wrote a graph search algorithm that avoids expanding any already visited states.

The Pacman will quickly find a solution via 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

Animated gif BFS Algorithm

-----------------------------------------------------

🔸 Scenario 3: Finding the best path using Uniform Cost Search

I have implemented the uniform-cost graph search (UCS) algorithm in the uniformCostSearch function in search.py.

While BFS will find a fewest-actions path to the goal, UCS will find paths that are “best” in other senses.

UCS agents differ only in the cost function they use.

The Pacman will quickly find a solution via running the following commands:

$ python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
$ python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
$ python pacman.py -l mediumScaryMaze -p StayWestSearchAgent

Animated gif UCS Algorithm

-----------------------------------------------------

🔸 Scenario 4: Finding the best path using A* search algorithm

I have implemented the A* graph search algorithm in the aStarSearch function in search.py.

I used Manhattan distance as the heuristic function.

A* finds the optimal solution slightly faster than Uniform Cost Search.

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic

Animated gif A* search Algorithm

-----------------------------------------------------

🔸 Scenario 5: Finding All the Corners

I have implemented a search algorithm in searchAgents.py that helps Pacman agent to find the shortest path through the maze that touches all four corners.

The Pacman will quickly find a solution via running the following commands:

$ python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
$ python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

Animated gif Finding All of the Corners

-----------------------------------------------------

🔸 Scenario 6: Corners Problem - Admissible and Consistent Heuristic

I have implemented a non-trivial non-negative consistent heuristic function that returns 0 at every goal state and never returns a negative value.

This function is both Admissible and Consistent and has been written in searchAgents.py.

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

Animated gif Corners Problem

-----------------------------------------------------

🔸 Scenario 7: Eating All of The Dots

I have implemented a heuristic function that helps Pacman agent to eat all the food in as few steps as possible.

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l trickySearch -p AStarFoodSearchAgent

Animated gif Eating All of The Dots

-----------------------------------------------------

🔸 Scenario 8: Suboptimal Search

In this scenario, I have implemented a function that helps Pacman agent to find a path to the closest dot.

This function has been written in searchAgents.py

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5

Animated gif Suboptimal Search

-----------------------------------------------------

📜 Credits

Mohammad Amin Shamshiri

GitHub Badge Twitter Badge LinkedIn Badge

Acknowledgements: Based on UC Berkeley's Pacman AI project, http://ai.berkeley.edu

About

In this project, the Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. I implemented general search algorithms such as depth-first, breadth-first, uniform cost, and A* search algorithms which are used to solve navigation problems in the Pacman world.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages