Earn Higher Grades With Instant Assignment Help.Ask Question!

C Programming
(5/5)

In this programming assignment you’ll be expected to build an AI algorithm to solve Pac-Man. You  can play the game compiling  the code given to you using the keyboard.

INSTRUCTIONS TO CANDIDATES
ANSWER ALL QUESTIONS

Purpose

The purpose of this assignment is for you to:

  • Increase your proficiency in C programming, your dexterity with dynamic memory allocation and your understanding of data structures, through programming a search algorithm over

  • Gain experience with applications of graphs and graph algorithms to solving games, one form of artificial

 

Assignment description

In this programming assignment you’ll be expected to build an AI algorithm to solve Pac-Man. The game invented in 1980 is one of the classics among arcade games. You  can play the game compiling  the code given to you using the keyboard, or using this web implementation.

 

The code in this assignment was adapted from the open-source terminal version made available by Mike Billars1 and the original version can be installed as a standard package in Ubuntu2.

 

The Pac-Man game

As explained in the wikipedia entry, The player navigates Pac-Man through a maze with no dead ends. The maze is filled with Pac-Dots, and includes four roving multi-colored ghosts: Blinky, Pinky, Inky, and Clyde.

 

The objective of the game is to accumulate as many points as possible by eating dots, fruits, and ghosts. When all of the dots in a stage are eaten, that stage is completed, and the player will advance to the next. The four ghosts roam the maze and chase Pac-Man. If any of the ghosts touches Pac-Man, a life is lost. When all lives have been lost, the game is over.

 

Pac-Man can eat a fruit first and then eat the ghosts for a fixed period of time to earn bonus points. The enemies turn deep blue, reverse direction and move away from Pac-Man, and usually move more slowly. When an enemy is eaten, its eyes return to the center ghost box where the ghost is regenerated in its normal color. The bonus score earned for eating a blue ghost increases exponentially for each consecutive ghost eaten while a single energizer is active: a score of 200 points is scored for eating one ghost, 400 for eating a second ghost, 800 for a third, and 1600 for the fourth.

 

The level id and a scoreboard can be found on the lower part. The information in the last three lines of the screen reveals information about the algorithm execution.


The game is won when all dots have been eaten. An AI agent or human player can change the direction of Pac-Man movements.

1https://sites.google.com/site/doctormike/pacman.html

2https://packages.ubuntu.com/xenial/games/pacman4console

Figure 1: The UI of the Terminal version. c is pacman, & are ghosts, * are fruits, and . is a regular  food.

The Algorithm

Each possible configuration of the Pac-Man game 29x28 grid and other relevant  information such as  the direction of pacman movements, number of lives left, etc.  is called a state.  The Pac-Man Graph    tt = (V, E) is implicitly defined. The vertex set V is defined as all the possible configurations (states), and the edges E connecting two vertexes are defined by the legal movements (right, left, up, down).

 

Your task is to find the path leading to the highest score, i.e. leading to the most rewarding vertex  (state).  A path is a sequence of movements.  You  are going to use a variant  of Dijkstra to explore     the most rewarding path first, up to a maximum budget B of expanded/explored nodes (nodes for which you’ve already generated its children).

 

Every time the game asks you for a movement (action), you should explore all possible paths until consuming the budget B if possible. Once you finished generating all the paths, you should return the ftrst action only of the path leading to the highest score vertex. This action will then be executed by the game engine.

 

You might have multiple  paths  with  the  same  maximum  score.  If  more  than  one  action  (left,right,up or down) begins paths with the same maximum score, you’ll have to break ties randomly.

 

Make sure you manage the memory well. Everytime you finish running the algorithm, you have to free all the nodes from the memory, otherwise you are going to run out of memory fairly fast or cause memory leaks.

 

GraphSearch(ttraph, start, budget)

  • node ← start

  • explored ← empty Array

  • frontier ← priority Queue Containing node Only

  • while frontier ƒ= empty

5     do

  • node ← pop()

  • add(node)

  • if size(explored) < budget

9                  then

  • for each APPLICABLE action a ∈ {Left, Right, Up, Down}

11                              do

  • newNode ← applyAction(node)

  • propagateBackScoreToFirstAction(newNode)

  • if lostLife(newNode)

15                                           then

  • delete newNode

17                                           else

  • add(newNode)

19

  • freeMemory(explored)

  • bestAction ← select best action breaking ties randomly

  • return bestAction

 

Figure 2: Online Graph algorithm variant of Dijkstra

Every time that you consider all the actions that can be applied for a given node, only use the ones that will face Pac-Man towards a free tile. For example, in Figure 1 you should only consider the actions Left, and Right.

When you applyAction you have to create a new node, that

  1. points to the parent,

  2. updates the state with the action chosen,

  3. updates the priority (used by the priority queue) of the node to be the negative node’s depth d (if the node is the dth step of the path, then its priority is -d).  This ensures the expansion of      the shortest paths first, as the priority queue provided is a max heap;

  4. updates the reward to be r(n) = (h(n) + score(n) − score(nParent)) × γd

    • the heuristic value h(n) that biases the reward to account for losing lives and eating fruits, plus

    • the change in score from the current node and the parent node

    • times a discount factor of γ = 0.99d, where d is the depth of the node,

  5. updates the accumulated reward from the initial node up to the current node, and

  6. updates any other auxiliary data in the

The heuristic function is h(n) = i − l − g, where i = 10 if Pac-Man has eaten a fruit and becomes invincible in that state; l = 10 if a life has been lost in that state; and g = 100 if the game is over. Otherwise i = l = g = 0.

You are going to need some auxiliary data structures to update the scores of the first 4 applicable actions. The function propagateBackScoreToFirstAction takes the score of the newly generated node, and propagates back the score to the first action of the path.

This propagation can be either Maximize or Average :

  • If you Maximize, you have to make sure that the first action is updated to reflect the maximum score of any of its

  • If you Average, you have to make sure that the first action is updated to reflect the average score taking into account all its

Attachments:
(5/5)

Related Questions

Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Ask This Assignment To Be Done By Our ExpertsGet A+ Grade Solution Guaranteed

expert
joyComputer science
(4/5)
12 Answers Hire Me
expert
Robert DLaw
(4.8/5)
554 Answers Hire Me
expert
Dr Samuel BarberaStatistics
(5/5)
933 Answers Hire Me
expert
Tutor For YouEconomics
(5/5)
652 Answers Hire Me