COMP5660-Assignment Series 1a Solved

Problem statement
In this assignment you will implement map generation for the game GPac. Automated design is a hallmark application of evolutionary computing that can generate art, solve engineering tasks, and even write code. For this assignment series, your task is to generate difficult maps to assess the performance of AI agents and eventually creating better AI agents that play a game.

GPac
In GPac, the world is a two-dimensional rectangular grid with the origin (0, 0) in the bottom-left corner. There are two types of units: Pac-Man and the Ghosts. Pac-Man always starts at the top left cell and all of the ghosts always start at the bottom right cell. These units are guided by controllers, which will be provided for you for the first assignment series. Units move in cardinal directions (up, down, left, right). They move from one grid cell to another in a discrete fashion (i.e., they move a whole cell at a time). Units cannot move off the edges of the map, and there is no world wrap. Ghosts can occupy the same grid cell as other Ghosts. If Pac-Man and a Ghost occupy the same cell, the game is over. If Pac-Man and a Ghost collide (i.e., exchange cells), the game is over.

Pills
Before the game begins, cells are chosen at random according to a preset pill-density parameter to contain “pills”. The pill-density parameter specifies the percentage chance for any given cell to contain a pill, subject to the constraints (a) at least one cell needs to contain a pill, (b) pills cannot be placed in walls and (c) PacMan’s starting cell cannot contain a pill. Thus: E[number of cells containing a pill] = MAX (1 , pill-density · (total number of cells - 1 - number of walls))

If Pac-Man occupies a cell that contains a pill, the pill is removed, and Pac-Man’s score is increased. When all pills have been removed from the world, the game is over.

Fruit
Each turn that the game is running, there is a user-configurable chance for a piece of fruit to spawn. There can only be one piece of fruit on the field at a time and it may not spawn in the same cell as a pill, a wall, or Pac-Man’s current cell. If Pac-Man occupies the cell that contains the piece of fruit, the fruit is removed, and Pac-Man’s score is increased by the fruit score which is user-configurable.

Time
Each GPac game starts with time equal to the number of grid cells in the world multiplied by the time multiplier. Each turn is one time step. When the time limit reaches zero, the game is over. This prevents games from getting stuck in infinite loops. It also promotes efficient controller evolution.

Game Play
Each turn, the game gives each of the unit’s controllers the current game state. This state includes at least: where all of the units are currently located and where all of the pills are located. Each controller will then choose what move to make (up, down, left, right for all controllers, also hold just for Pac-Man). Once all of the units have determined their next move, the game state will update everyone’s position and decrease the time remaining by one. Once everyone has moved, the game will check if:

1.    Pac-Man and any of the Ghosts are in the same cell, causing game-over.

2.    Pac-Man collided with a Ghost, causing game-over.

3.    Pac-Man is in a cell with a pill, causing the pill to be removed, and the score to be adjusted.

4.    Pac-Man is in a cell with a piece of fruit, causing the fruit to be removed, and the score to be adjusted.

5.    All the pills are removed, causing game-over.

6.    Time remaining is equal to zero, causing game-over.

Score
Pac-Man’s score is equal to the percentage of the total number of pills he has consumed truncated to an integer, plus the score for fruit consumed. If the game ends because there are no more pills on the board, Pac-Man’s score is increased by the percentage of time remaining truncated to an integer. This score can be used directly for the fitness of the Pac-Man controller. Ghost fitness should be inversely proportional to Pac-Man’s fitness (for example, negate his fitness) and if the game ends due to Pac-Man’s demise, then the Ghost score is increased by the percentage of time remaining truncated to an integer.

World File Format
GPac generates a sequence of your world states for a single run to facilitate debugging, visualization, and grading. The file format consists of header values for the width and height of the world, followed by, for each snap shot that you are outputting, a list of ordered triples consisting of <key><space><value><space><value>. The origin (0,0) is in the lower-left corner. The valid triples are:

m Pac-Man; second value is x-coordinate; third value is y-coordinate

1         Ghost 1; second value is x-coordinate; third value is y-coordinate

2         Ghost 2; second value is x-coordinate; third value is y-coordinate

3         Ghost 3; second value is x-coordinate; third value is y-coordinate p Pill; second value is x-coordinate; third value is y-coordinate w Wall; second value is x-coordinate; third value is y-coordinate f Fruit spawned; second value is x-coordinate; third value is y-coordinate t End of current turn; second value is remaining time; third value is current score

Here is an example file for a world with width 40, height 30, 3 snap shots, and 3 pills:

40

30

m 0 29 1 39 0

2 39 0 3 39 0 w 1 1 w 36 20 w 10 10

w 2 29 p 1 29 p 36 19 p 27 8 t 2400 0 m 1 29 1 38 0

2 38 0 3 39 1 t 2399 33 m 1 28 1 38 1

2 37 0 3 39 0 t 2398 33