Lab #4: Space : : : The Final Frontier Solution

Description

Congratulations! You are the rst ECE244 student to serve onboard the Starship Galaxy Ex-plorer NCC-1701X. The ship just had a erce battle with the Romulans near the Neutral Zone. Although the ship emerged victorious, it sustained much damage. The warp engines are o ine, the shields are down and all photon torpedoes are depleted. The Captin is taking the ship at impulse speed to the nearest star base for repairs. However, the ship must rst navigate through the no-torious Huya-5381 asteroid belt. To avoid the destruction of the ship, phaser banks must be used, while the ship is going through the belt, to destroy the asteroids. As the leading programming expert on the ship, you are called upon to write a C++ program that receives sensor data of the asteroids and directs phaser re to destroy them before they hit the ship. Your journey begins : : : live long and prosper!

1 Objectives

The main objective of the assignment is for you to learn how to build, use and maintain linked lists. You will do so by extending a game server that simulates the asteroids and the actions of the Starship as it navigates through the belt of asteroids.

2 Game Overview

The game consists of two major components: the game server (or simply the server) and the player code (or simply the player), as depicted in Figure 1. The server contains the asteroids observer, which randomly generates asteroids with di erent masses, positions and velocities. This observer reports to the player changes in the status of the asteroids by making calls to a set of asteroids observer functions. The player maintains a linked list of the asteroids currently active in the game, based on the asteroids observer function calls made. The player implements a set of linked list methods to manipulate this linked list.

The player has a Game AI module, which implements the AI of the game: code that examines the list of asteroids, decides which one to re at and then uses a set of ship functions to instruct the ship controller module in the server to rotate the ship and/or re. The game server updates the status of the asteroids based on the ring and calls back the asteroids observer functions, so the player can also update its linked list of asteroids. The display manager in the server graphically displays the asteroids, the ship and the ring actions. The game remains active until all the asteroids are either destroyed or they exit the game, or until an asteroid hits (and thus destroys) the ship.

The code for the server is provided to you as a set of object les. It is the code for the player that you must write, including the code that implements the linked list of asteroids, the code for the asteroids observer functions, which calls the linked list functions, and the game AI.

Asteroid Linked List

Player Code

Figure 1: The game server and the player code. The grayed boxes represent code you have to write.

3 Problem Statement

You will write in C++ code that: (1) implements methods that create, manipulate and maintain a linked list of asteoids, (2) makes calls to the linked list methods based on the methods the asteroids observer invokes to signal changes in the status of asteroids, and (3) implments the game AI. The remainder of this section details the various classes used in the game, pointing out what is implemented for you and what is it that you have to implement.

3.1 The Asteroid Class

This class represents Asteroid objects and it is de ned in the le Asteroid.hpp. You should examine the header le to become familiar with the variables used to represent an asteroid and the methods of the class (see Section 4 for the location of this and other class les).

In summary, each asteroid object has an ID, a mass, a velocity and a health. The ID is an identi er unique for each asteroid. The mass is a non-zero integer that re ects the relative mass of the asteroid. The velocity is a 2-dimensional vector that has the speed of the asteroid in the x and y dimensions of the game grid (see Section 3.6 for a description of the game grid). The health is an integer that indicates how close the asteroid is to being destroyed. On every phase blast, health is decremented and when health becomes 0 the asteroid explodes.

In addition, each asteroid has a hit box associated with it, which represents the rectangular area around the asteroid within which a phaser hit is considered a hit of the astertoid. The mass of an asteroid determines how many phaser shots are needed to destroy it. For a small asteroid, a single phaser shot is su cient to destroy it. For a large asteroid, two shots are needed. A large asteroid once hit may also split into multiple smaller ones.The implementation of the Asteroid class is within the server code and you need not implement it. Thus, you are not allowed to modify the Asteroid.hpp le.

3.2 The AsteroidListItem Class

This class is used to represent an entry of the linked list of asteroids, called AsteroidListItem. The de nition and the implementation of this class appear in the le AsteroidList.hpp. An object of this class simply contains a pointer to an Asteroid object and a pointer to an AsteroidListItem object, the next item on the list. The class has methods to allow you access to its Asteroid object and pointer data. You are not allowed to modify the contents of the AsteroidList.hpp le.

3.3 The AsteroidList Class

This class de nes a linked list of AsteroidListItem objects. It’s de nition appears in the le AsteroidList.hpp. It contains methods to add and delete AsteroidListItem objects to and from the list, as well as methods for traversing the list. An example of an AsteroidList is shown in Figure 2. The AsteroidList class simple contains an AsteroidListItem that represents the head of the linked list. The Asteroid data associated with this head is unde ned. The next pointer points to the rst AsteroidListItem on the list. You must implement the methods of this class in the le AsteroidList.cpp. You are not allowed to modify the contents of the AsteroidList.hpp le.

Figure 2: An example of an AsteroidList with two items. Note that the rst AsteroidListItem is the head of the linked list.

A detailed description of the methods of this class appears in the comments of the AsteroidList.hpp le. Read these comments to nd out what each method should do and implement it correctly.

3.4 The AsteroidsObserver Class

This class de nes the interface by which the game server provide updates about asteroids to the player. It contains methods that are called by the game server to inform the player when an asteroid appears in the game, has moved, has left the game or has been destroyed. The class de nition appears in the le AsteroidsObserver.hpp and you must implement these functions in the le AsteroidsObserver.cpp. You implementation of these methods must manipulate the linked list of asteroids (pointed to by asteroid list declared in the AsteroidsObserver class) to re ect what happened to the asteroids. However, you are not allowed to modify the contents of the AsteroidsObserver.hpp le.
3.5 The GameAI Class

This class de nes methods that implement the logic or AI of the game. This class is de ned in the le GameAI.hpp. The main method in this class is called suggestAction. It is where the AI is implemented. This method should examine the list of asteroids and the ship state (contained in a structure called ShipState, see below) and then decide what the ship should do. The method informs the game server about the desired action through a structure called suggestedAction, see below.

You must implement the suggestAction method of the GameAI class. You should consider factors such as the proximity of asteroids to the ship, the time until the phaser bank charges, the mass of an asteroid as well as its remianing health. The more and bigger asteroids are destroyed, the higher the score of the game.

3.5.1 The ShipState Structure

This structure carries information from the server regarding the state of the ship. This information includes: whether a phaser re has already been requested, how many more cycles before the phaser banks can re, the current location and rotation of the ship, and the current game score. The server automatically updates this structure on each cycle (see Section 3.6 for the de nition of a cycle). This structure is declared in the le GameAI.hpp and you may not modify it.

3.5.2 The SuggestedAction Structure

This structure, de ned in the le GameAI.hpp, simply contains two variables that indicate the yawing of the ship, i.e., its tilt and the ring action. The structure utilizes two enums to list the possible values for each of these variables. It also pre-de nes some simple common actions that can be taken (thos pre-de ned actions are de ned outside the structure). You must not modify this structure.

3.5.3 The myAIData Structure

This structure is de ned in the le myAIData.hpp and it contains sample elds that can be used to store relevant information about your game AI. You will likely need to modify this structure to add more elds to it.

3.5.4 The debug rt Object

The debug rt data member of GameAI is a special SFML object that you can draw to, much like you have done in lab assignment 2. It is of tyoe RenderTarget, which is similar to RenderWindow. Every time the game server updates the screen, the contents of debug rt is drawn over the game. In other words, anything you draw to debug rt will be drawn over the game. Use debug rt to help you debug your AI by visualizing it’s state. However, you need not use it if you do not want to.

3.6 Game Operation

The game server operates in cycles. In every cycle, the asteroids observer generates new asteroids into the eld of the game. It then makes a sequence of calls to the asteroids observer methods to re ect changes to the state of each asteroid (one call per asteroid), both existing and new. The changes in state include: the motion of an existing asteroid, the creation of a new asteroid or the destruction of an asteroid. The server then invokes the suggestAction method of the player’s

GameAI class to get the the suggested action of the player in the structure suggestedAction. The server updates the game based on the suggested action and updates the screen, thus completing a cycle. It immediately begins the next cycle by repeating the process above. The game server keeps track of your score in the game.

Asteroids and the ship are located on a 2-dimensional grid that is used to de ne the position of an asteroid or the ship. The origin of the grid is the top left corner of the window. The x axis is the horizontal, increasing to the right. The y axis is the vertical, increasing towards the bottom.

3.7 Sample Game

The executable of a sample game is provided in the release called galaxy-explorer-ref) so you can see how the game is played. Run the executable to start the game window. The sample game contains a basic AI module to show you the action of the game.

The asteroids in the game are randomly generated based on random seeds. Thus, every time the game is run, a di erent set of asteroids appear. While this desirable in a game, it is not very conducive to debugging and to improving your AI. Thus, both the sample game and the game you build can be run with a speci c random seed. For example, the sample game can be run with a random seed of 137137411 as follows:

galaxy-explorer-ref 137137411

You can also play the game without the AI using the keybord. Whan the initial game screen starts and before you hit the space key to start, you can press the a key. This key toggles the game to use or not use the AI. If the AI is not used you can use the keyboard to control the ship and to re. Use the left and right arrow keys to rotate and the space bar to re.

4 Procedure

Make your ece244 directory (in your home directory) your current working directory (using the cd command. Download the lab4 release.zip le, un-zip it in the ece244. This creates a sub-directory called galaxy-explorer that contains all the assignment les.

You will write your code in the following les: AsteroidList.cpp, AsteroidsObserver.cpp, GamaAI.cpp and MyAIData.hpp, as described earlier in Section 3. These les are contained in the directory ~ /ece244/galaxy-explorer/src/galaxy-explorer.

There is a sample game executable in ~/galaxy-explorer/. It is called galaxy-explorer-ref. You can run this executable to see how the game plays with a simple AI.

The hearder (.hpp) les described earlier in this document (e.g., Asteroid.h) are located in the directory /share/copy/ece244f/lab4/src/galaxy-explorer. They are only reasable to you, thus ensuring that you cannot modiy them.

The galaxy-explorer directory contains a pre-con gured project for NetBeans as well as a Makefile should you want to directly use the command line. To use the supplied NetBeans project, start NetBeans, open a project through the menus: File -> Open Project and select ~/ece244/galaxy-explorer. You can then compile and run the code in Netbeans. You can also locate the include les easily within NetBeans.
To use the command line to compile, make ~/ece244/galaxy-explorer/src your current working directory and type make. This will utilize the provided Makefile and place the ex-ecutable in ~/ece244/galaxy-explorer/build/EXE/galaxy-explorer. Thus, you can run this executable by making the directory ~/ece244/galaxy-explorer your current working directory and typing: ./build/EXE/galaxy-explorer.

If you wish to work on the assignment remotely from you home machine, use VNC to connect to remote.ecf.utoronto.ca. This is the most convenient way to work remotely, allowing you to use SFML and the provided Makefile on ECF while working at home. Refer to the handout titled: \Remote Access to ECF with VNC” for details on how to connect with a VNC client.

When you build your code, either using the command line or using NetBeans, a special exe-cutable is generated. It is called test galaxy-explorer and it is located in the directory ~/ece244/galaxy-explorer/build/EXE along with the game executable. You can run this exe-cutable by making the directory ~/ece244/galaxy-explorer your current working directory and typing: ./build/EXE/test galaxy-explorer -s. You can also run the test executable from Net-beans by changing to the Debug Test con guration.

The test galaxy-explorer executable runs your code against a set of test cases for the linked list class (but not for the AI). These tests exercise insertion and deletion into your linked list. They report back what each test does and if it failed. The following are examples of the output for two tests, one that fails and one that passes.

The output of the test that fails is shown below. The test runs the scenario Baic Insertion. It is given an empty list and adds two list elements to it using pushFront(). Thus, is expects the rst element on the list to be the last element inserted. The test also requires the size of the list to be 2. Howeven in this case, the list remains empty and thus the test fails as shown.

——————————————————————————-

Scenario: Basic Insertion

Given: an empty list

When: pushFront()ing an element

And when: pushFront()ing another element

Then: the front element should match the newly pushed-in value ——————————————————————————- … galaxy-explorer/testing/asteroid_list_test_public.cpp:39

…………………………………………………………………….

… galaxy-explorer/testing/asteroid_list_test_public.cpp:40: FAILED:

REQUIRE( alist.size() == 2 )

with expansion:

0 == 2

 

The output of the test that passes is shown below. The scenario is Basic Invariants. Given an emty list, then the list must be empty. The condition tested for is alist.begin() == alist.end(), which is true and thus the test passes.
—————————————————————————–

Scenario: Basic Invariants

Given: a empty list

Then: the list should be empty

——————————————————————————-

… galaxy-explorer/testing/asteroid_list_test_public.cpp:17

…………………………………………………………………….

… galaxy-explorer/testing/asteroid_list_test_public.cpp:18:

PASSED:

REQUIRE( alist.begin() == alist.end() )

with expansion:

nullptr == nullptr

… galaxy-explorer/testing/asteroid_list_test_public.cpp:19:

PASSED:

REQUIRE( alist.size() == 0 )

with expansion:

0 == 0

 

Since you are able to test your code directly with the test galaxy-explorer, there is no exercise for this assignment.

5 Deliverables and Marking

The assignment is marked in three parts. The rst part auto-tests your code for the correctness of your linked list implementation. This part is worth 60% of the total mark of the assignment. The second part checks for the style (structure, descriptive variable names, useful comments, consistent indentation, use of functions to avoid repeated code and general readability) of your code. This part is worth 20% of the total assignment mark. The last part is based on your score in the game, is worth 20% of the total mark of the assignment, and is assigned on a competitive basis. The scores of all students in class are sorted from highest to lowest. The highest score (scorehighest) receives a mark of 20%. The lowest score (scorelowest) receives a mark of 0%. A score in between (score) receives a mark based on the following formula:

mark = 20% ((score scorelowest)=(scorehighest scorelowest))

Your score is displayed on the game window. In order to nd out how your score stands in relation to the rest of the class, you must rst submit your assignment (remember that you can submit your assignment multiple times and that every new submission overwrites the previous one). Every night, all submitted assignments will be collected, compiled and executed. The resulting scores will be displayed on the following web page: http://www.ecf.utoronto.ca/~ece244i/lab4rankings.html. You can nd your score by searching for yout student number. Please note that the scores will not be available on the web site until the second week of the assignemnt.

Submit the les in your ~/ece244/galaxy-explorer/src/galaxy-explorer directory (i.e., change your working directory to that directory before executing the submit command) as lab 4 using the command: ~ece244i/public/submit 4.

 

Page 7 of 7