Game Features 4

Graphs and Testing
Overview

Game Features Overview

Game Features 4 asseses Graphs and Testing. You will continue to build functionality for the Game Engine. This will be done on top of the code written for the previous tasks; you should not reclone or remove said code for this task or any future Game Features tasks.

Once again, this document is split into sections for convenience. In the first section, you will be improving pathfinding using graphs and utilize it to create more advanced decisions. The second section will have you implement an algorithm to procedurally generate maps for a roguelike game, such that each playthrough entails a unique map.

Improved Pathfinding

Overview

The content of this section is primarily used in the Game Engine by the Roguelike. To play this game navigate to the class app.Configuration and change the GAME constant to "roguelike". Most of this content will also be testable within the sample game, accessible by changing the GAME constant to "sample game".

For this section, you will be writing code in the following classes which already exist:

  • PathfindingUtils, located in the app.gameengine.utils package.
  • Minotaur, Demon, Archer, and Sorcerer, located in the app.games.topdownobjects package.
  • Spike and Potion, located in the app.games.commonobjects package.
  • LevelParser, located in the app.gameengine package.

You should create the TestTask4 class in your tests package. We have provided tests for some of the Decision subclasses, the LevelParser updates, and a few miscellaneous classes. They can be accessed at this link: TestTask4.java. You can open this link in a new tab to copy and paste the content into your project, or right click and select "save link as", then download the file to the correct location within the project.

One of the tests relies on testing files, which should all be placed in the directory "data/levels/testing". They are: mario1.csv, roguelike.csv, and medium.csv

These tests are not overly thorough, but should validate some of the basic behavior of the features that they test, and let you know if you are on the right track.

You will also have to create several additional classes, which will be specified in the following instructions.

The largest part of this task deals with pathfinding with a BFS. If you previously completed the pathfinding component of Game Features 2, enemies will be able to follow these paths around walls to navigate to the player. If you did not complete it, you can still earn full points, but your enemies will not actually move at all.


Specification

You should read through all the following sections before you begin to implement the methods from the specification. Note that you will not receive feedback on the correctness of these methods until you've completed the testing component of this task (see the "Autolab Feedback" section for more details). However, you must at least create every class/method from this specification to receive feedback. You can "stub out" these methods by having them always return a fixed value, but they must exist so the grading code, and your tests, can compile and run.

For this section of the task, you will implement the following functionality:

    Navigate to the app.gameengine.utils.PathfindingUtils class. If it does not already exist, create this class.
  • findPath: Create a static method named findPath which takes two Vector2Ds as parameters and returns a LinkedListNode of Vector2Ds. If you completed this method already, you should leave it as is. Otherwise, this method should return null.
    • This method is worth no points, but is needed for the code to compile.
  • findPathAvoidWalls: Create a static method named findPathAvoidWalls which takes a Level and two Vector2Ds as parameters, and returns a LinkedListNode of Vector2Ds. The Vector2Ds are the starting and ending points of the path, respectively, and the Level is the level being navigated.
    • This method should return a shortest valid path between the tile containing the starting location and the tile containing the ending location such that no point in the returned path shares a location with any solid object contained in the level.
    • Any GameObject (dynamic or static) can be solid or non-solid. This can be determined by the GameObject.isSolid method. You can access the lists of static and dynamic objects of a level with the getStaticObjects and getDynamicObjects methods respectively.
    • Any GameObject that is solid should be avoided. Specifically, the tile containing that object should be avoided. So, if there is a Wall at (1.5, 2.8), the location (1, 2) should be avoided. You can use the Math.floor or Vector2D.floor methods to account for this.
      • Be sure not to modify the locations of the objects themselves.
    • This method has the same criteria for a valid path as the findPath method: all locations in the path must be aligned to a tile (i.e. whole numbers only) and all tiles must be one tile above, below, to the left, or to the right from the tile preceding and succeeding it.
      • Recall that this still applies to the starting and ending nodes in the path. The first and last nodes should be the tiles containing the starting and ending location rather than the starting and ending locations themselves.
      • Again, you can use Math.floor or Vector2D.floor for finding the tile that contains a given vector. Be sure not to modify the input vectors directly, though.
    • If the start/end location is either not within the Level's boundary or is inside a solid object, this method should return null.
      • You can use the GameUtils.isInBounds method to determine if a vector is within the bounds of a level.
    • Similarly, a path should never go outside the bounds of a level. That is, the path that you return should only contain Vector2Ds that are within the bounds. Levels are not guaranteed to be surrounded by solid objects.
    • If there does not exist a valid path between the start and end locations, this method should return null.
    • The image below shows an example of a valid path from (1, 1) to (3, 1). The full path is [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1)].
      visual depiction of an agent's path
    • Completing this method will earn you 20 points.

Now you will implement several new Decision subclasses that will make use of this pathfinding, along with other behaviors used within the roguelike and sample games. These will all live in the app.gameengine.model.ai.roguelike package, which you should create.

Completing all of these Decisions will earn you 15 points.

  • MoveTowardPlayer: Create a class named MoveTowardPlayer which extends Decision. This class represents the action of acquiring a path to the player, and moving along that path. Implement the following methods in this class.
    • Create a constructor that takes an Agent and a String, which are passed to the super constructor.
    • Override the decide method to always return false.
    • Override the doAction method. If the Agent's path is null, use the PathfindingUtils.findPath method to assign it a path. The starting location should be that Agent's location, and the ending location should be the location of the Player within the level. If the Agent's path is not null, call the followPath method on it, passing in the double parameter.
  • MoveTowardPlayerAvoidWalls: Create a class named MoveTowardPlayerAvoidWalls which extends Decision. This class's constructor and other methods should be the same as in MoveTowardPlayer, except using PathfindingUtils.findPathAvoidWalls instead of findPath.
  • ShootPlayer: Create a class named ShootPlayer which extends Decision. This class represents an action of firing an EnemyArrowProjectile at the player. Implement the following methods in this class.
    • Create a constructor that takes an Agent, a String, and a double. The first two should be passed to the super constructor, and the third should be used as the cooldown for a timer, which should be stored in an instance variable.
      • Use the app.gameengine.utils.Timer class. This is a utility that allows for keeping track of time, so that enemies can only shoot on a cooldown.
    • Override the decide method to always return false.
    • Override the doAction method. This method should always zero the Agent's velocity. It should then advance the timer by the double parameter, and if the cooldown has elapsed, it should set the orientation of the agent to face the player, and fire a projectile.
      • The Timer.tick method advances the timer, and returns a boolean representing whether the cooldown has elapsed.
      • The orientation of the Agent must be set in the direction of the player, with a magnitude of 1. To get a vector pointing from the agent to the player, subtract the agent's location from the player's location (either manually or with the Vector2D.sub method). Then, normalize this vector, ie. make it's magnitude 1. You can use the Vector2D.normalize method for this.
        • For example, if the agent is located at (0, 0) and the player is at (4, 3), the agent's orientation should become (0.8, 0.6). Take a moment to understand why.
        • This is done so that when the projectile is fired, it moves in the correct direction.
      • To fire a projectile, call fireProjectile on the Agent. The projectile argument should be a new EnemyArrowProjectile, the double speed should be 10, and the Level should use the parameter.
  • ShootHomingProjectile: Create a class named ShootHomingProjectile which extends Decision. This class's constructor and other methods should be the same as in ShootPlayer, except using EnemyHomingProjectiles instead of EnemyArrowProjectiles.
  • Heal: Create a class named Heal which extends Decision. This class represents an action of remaining still to recover HP. Implement the following methods in this class.
    • Create a constructor that takes an Agent, a String, an int, and a double. The first two should be passed to the super constructor. The third represents the amount that this will heal the agent by each time. The double should be used as the cooldown for a timer, which should be stored in an instance variable.
      • Use the app.gameengine.utils.Timer class. This will be used to ensure that the agent does not heal too frequently.
    • Override the decide method to always return false.
    • Override the doAction method. This method should always zero the Agent's velocity. It should then advance the timer by the double parameter, and if the cooldown has elapsed, it should heal the agent by the set amount.
      • The Timer.tick method advances the timer, and returns a boolean representing whether the cooldown has elapsed.
      • You can use the getHP and setHP methods to modify the agent's health.
  • LowHP: Create a class named LowHP which extends Decision. This class represents a decision of whether the Agent's health is below a certain threshold. Implement the following methods in this class.
    • Create a constructor that takes an Agent, a String, and an int. The first two should be passed to the super constructor, and the third represents the health threshold, which should be stored as an instance variable.
    • Override the decide method to return whether the current health of the Agent is less than or equal to the threshold.
    • Override the doAction method to do nothing.
  • NearPlayer: Create a class named NearPlayer which extends Decision. This class represents a decision of whether the Agent is closer than a certain distance to the player. Implement the following methods in this class.
    • Create a constructor that takes an Agent, a String, and a double. The first two should be passed to the super constructor, and the third represents the distance threshold, which should be stored as an instance variable.
    • Override the decide method to return whether the distance between the agent and the player is less than or equal to the threshold. You can use the Vector2D.euclideanDistance method for this check.
    • Override the doAction method to do nothing.
  • Now you will use these decisions to give various Agents different behaviors. The Agents you must modify are Demon, Minotaur, Archer, Sorcerer, and Tower, all in the app.games.topdownobjects package.
    • The decision tree for each of these types of agents must be set. The specific contents are up to you, as long as each decision tree contains at least one Decision. You are encouraged to play around and design different behaviors.
    • The recommended minimum decision trees are as follows:
      • Demon: A single MoveTowardPlayer decision.
      • Minotaur: A single MoveTowardPlayerAvoidWalls decision.
      • Archer: A single ShootPlayer decision.
      • Sorcerer: A single ShootHomingProjectile decision.
      • Tower: A single ShootPlayer decision. Note that decisions that cause the tower to move will do nothing. It is also recommended to override the isSolid method to always return true, to test that solid DynamicGameObjects are handled properly. We will not test for this, though.

    The last additions are to the Spike and Potion classes in the app.games.commonobjects package, and to the LevelParser.
  • Spike: Most of this class already exists. You must override the collideWithDynamicObject method to kill any player it contacts.
    • Recall that you can use the isPlayer method to determine if an object is or is not the player.
    • You should use the destroy method to kill the player.
  • Potion: Most of this class already exists. You must override the collideWithDynamicObject method to heal/harm a player on contact. Also create the getHealAmount method.
    • Recall that you can use the isPlayer method to determine if an object is or is not the player.
    • A potion can have a positive or negative heal amount. A positive heal amount indicates that it should heal the player, and a negative heal amount should damage the player. You can use the takeDamage method to harm the player, but note that this method does nothing if the argument is negative, so it cannot be used to heal the player. You can use setHP instead.
    • getHealAmount should be a getter for an int instance variable representing the amount to heal. This instance variable should initially be set to the third constructor parameter.

    • Implement the following updates to the LevelParser class. These changes will allow the game engine to parse levels which contain objects for the roguelike and sample games.

    • readDynamicObject
      • Add a case for Minotaur objects. If the string being checked is exactly "Minotaur", a new Minotaur object should be returned. The Minotaur constructor takes two doubles, which should be the variables x and y which already exist in this method, and two ints, which will be the fifth and sixth values in the ArrayList for that object. These are the same parameters as the Demon constructor, which already exists in this method.
      • Add a case for Archer objects. If the string being checked is exactly "Archer", a new Archer object should be returned. The Archer constructor takes the same parameters as the Demon and Minotaur constructors.
      • Add a case for Sorcerer objects. If the string being checked is exactly "Sorcerer", a new Sorcerer object should be returned. The Sorcerer constructor takes the same parameters as the Demon, Minotaur, and Archer constructors.
    • readStaticObject
      • Add a case for Spike objects. If the string being checked is exactly "Spike", a new Spike object should be returned. The Spike constructor takes only two doubles, which should be the variables x and y which already exist in this method.
      • Add a case for Potion objects. If the string being checked is exactly "Potion", a new Potion object should be returned. The Potion constructor takes two doubles and an int. The doubles should be the variables x and y which already exist in this method. The int should be the fifth value in the ArrayList for that object.
      • Add a case for Marker objects. If the string being checked is exactly "Marker", a new Marker object should be returned. The Marker constructor takes two doubles and a String. The doubles should be the variables x and y which already exist in this method. The String should be the fifth value in the ArrayList for that object.
      • Add a case for DirectionalWall objects. If the string being checked is exactly "DirectionalWall", a new DirectionalWall object should be returned. The DirectionalWall constructor takes two doubles and a Level. The doubles should be the variables x and y which already exist in this method, and the Level should be the method parameter.
    • parseLevel
      • Modify this method to return either a TopDownLevel, MarioLevel, or RoguelikeLevel depending on the content of the csv file being read.
      • Just like in Task 2, the level type can be determined from the first field in the first line of the level file. If that field is exactly "RoguelikeLevel", then the level you create, modify, and return should be a RoguelikeLevel object. This method should still work for both TopDownLevels and MarioLevels.
  • Completing these classes and level parser updates will earn you 5 points.

Testing Utility

In the tests.TestUtils class, create a static method named validatePath that takes in a LinkedListNode of Vector2Ds and returns void. This method should contain JUnit asserts to verify that the linked list is a valid path, and should fail a JUnit assert if the path is invalid.

This uses the same criteria as the findPath method to determine validity of a path. This means that every pair of vectors in the path must be horizontally or vertically adjacent (no diagonals), a distance of 1 tile apart, and each vector must have x and y components that are whole numbers.

Consider an input path of null to be valid.

Note that this method does not assert every property necessary. Namely, it does nothing to guaranteed that the path avoids solid objects.

Note that this method is not a test, and thus should not have the @Test annotation. Rather, this is a static method intended to be used in your testing. You are encouraged to use this method to simplify your test cases.


Testing Requirements

Write JUnit tests for the following method from the specification in the TestTask4 class. These tests should be annotated with @Test.

You may find it useful to create level csv files and read them with the LevelParser in your tests. You can create levels with the level editor, which should contain all of the objects and level types you may want to use.

  • findPathAvoidWalls (20 points):
    • Your tests should verify that the path returned by calling this method is valid and of the shortest possible length that avoids solid objects.
    • You will need to create levels with obstacles for your tests (note that the base Level class is abstract). You can use the TopDownLevel or RoguelikeLevel classes, and can use Wall objects as obstacles.
    • Since there may be multiple shortest paths that avoid solid objects, you should not test for a specific path to be returned in such cases.
  • You DO NOT need to write tests for any of the remaining classes or methods. Tests have been provided for some of these as described in the overview section above.

Programming Requirements

Implement the methods from the specification. You may wish to complete the Testing Requirements before you begin implementation, and it's suggested that you run these tests as you implement the methods.


Autolab Feedback

Autolab feedback will be given in several phases. These phases dictate the order you are expected to complete this assignment. Although you can still earn points from completing these phases out of order, you are nonetheless expected to have the previous phases completed before trying to fix a later one.

  1. Testing your testing utility: Your testing utility will be checked for correctness. Passing this phase will earn you the points associated with the utility. If you do not pass this phase, you should correct your testing utility so it can be used in the testing component.
  2. Running your tests on a correct solution: Your tests will be run on a correct solution to this assignment. If any of your tests crash or fail, you will earn 0 points for testing. If a test fails here but passes your implementation locally, it's likely you have a bug both in your code and in your test.
  3. Checking your tests for feature coverage: Your tests will be checked for feature coverage by determining if it can successfully catch bugs associated with incorrect solutions. For each feature your tests covered, you will earn some amount of points. Passing this phase doesn't mean your testing is fully comprehensive, but can be considered the minimum for effective testing. If you failed the previous phase, this phase will not run and you won't get any points for testing.
  4. Running my tests on your solution: Your code will be run against our tests. Once you've passed all the tests associated with some part of the specification, you'll earn some points for a correct implementation. If any feature for that part fails our tests, you won't earn any points for this part. If that happens, you should write more tests to catch that bug and fix it in your implementation.
Roguelike

Overview

For this portion, you will implement functionality in the app.games.roguelikeobjects.RoguelikeGame class to add procedurally generated levels to the roguelike. If you haven't already, you should change the GAME constant in app.Configuration to "roguelike" to be able to view and test the generation.

Since there is only one method you need to implement for this task, all points will be earned upon passing our tests for that method.


Procedural Generation

Procedural Generation in game development refers to the creation of levels, maps, or any content that is done through algorithms instead of manually. In this task, you will modify RoguelikeGame's generateMap method to accomplish this using a version of DFS.

The gif below shows an example of how it should work when it is finished.

visual depiction of how generating a map loops

As shown in the gif, generateMap works in such a way where it first generates the level and then connects a door to the level that discovered it.

There are some important parameters here that vastly change how the generated map looks. These can be modified in RoguelikeGame for testing purposes, or for fun!

  • Map Size - this.mapSize in RoguelikeGame, a Vector2D representing the size of the map grid.
  • Max Rooms - this.maxRooms in RoguelikeGame, an int that changes the maximum amount of rooms that can be generated.
    • The first room will always be the starting room, and the last room will always be the boss room.

Note: The order of level generation may seem unintuitive at first. Think about which room each other room was discovered from, and why this is the case.


Programming Requirements

Note: The existing implementation of this method should be completely replaced. However, before deleting the given code, you might want to look at it for examples on the using some of the helper methods as described below.

  • generateMap (40 points)
    • In the RoguelikeGame class, delete the given functionality of generateMap and overwrite it with a version that procedurally generates levels using a version of DFS.
      • All generated maps must start with a random Vector2D starting position. To create this position, call getRandomStartingPosition, a method in RoguelikeGame.
      • You are tasked with generating more Vector2D positions and a corresponding level for each. These positions should be picked out from the starting position in random directions. To get these random directions, you must call the given Randomizer.shuffleArrayList(DIRECTIONS) method exactly as shown.
        • Calling Randomizer.shuffleArrayList(DIRECTIONS) returns to you a new shuffled ArrayList of Vector2D directions. You should use this method every time you are exploring for new positions from your current position. (This means that the directions should be randomized every time you are exploring for new positions, not once per map generation.)
        • The generated positions must be valid. A valid position is one that has not already been explored and is within the bounds of this.mapSize.
        • Remember, you can see if a Vector2D is in bounds of another Vector2D by calling GameUtils.isInBounds.
      • Luckily, you don't need to choose the random levels. Once you have a new position and are ready to generate the next level, call getNextLevelToGenerate. This will return you a RoguelikeLevel object, which should be initialized with the new position by calling the initialize method on the returned level and passing in the generated position. This level also must be added to this.levelMap, which maps levels by their name. (Which you can get by calling the getName method on a level). You can also use the addLevel method to achieve this.
      • After a level is generated and initialized, it's door must be opened to the level that "discovered" it. You can open a door of a level by calling the openDoor method on a RoguelikeLevel object that takes an adjacent RoguelikeLevel.
        • For example, if I am a newly generated level at (1,0), I would look up which level discovered me, lets say (0,0), and open my door to that level. I would then also go to the level at (0,0) and open its door to me, (1,0), since it should have an open door to me as well.
      • Whenever you generate a level, you should also increment this.roomsGenerated. You should only generate this.maxRooms amount of levels.
      • Lastly, once the map is completely generated, you should call this.loadLevel on the first level you created, the starting level.
    • You should be generating a level before exploring for new level positions.
      • Example: The next level position is (1,0). This level should be generated and initialized before exploring new random level positions from (1,0).
    • When exploring for new positions, your current position should mark all of its neighbors as explored, which effectively blocks those positions and reserves them as connected to the level that discovered them. In this way, you can use the BFS algorithm explained in lecture and swap the queue for a stack to get the correct order of visiting positions.
    • It is extremely important that you call these randomization methods in the order listed below. If you deviate from this order, you will likely fail in Autolab.
      1. getRandomStartingPosition - only called once.
      2. getNextLevelToGenerate
      3. Randomizer.shuffleArrayList(DIRECTIONS) - this should always be called after getNextLevelToGenerate.

Now, when you play the Roguelike, you should get a different map every time you play, with a guaranteed boss room found somewhere throughout it. Testing this method largely involves playing the game and ensuring the correct amount of rooms were generated, with a boss room somewhere in the map. Sometimes, using a set seed for your randomization could also help with the testing process, but is optional. To do this, call Randomizer.setSeed with any number of your choosing before doing anything that involves randomization.

Autolab Feedback

Since there is no testing requirement for this part, Autolab feedback will only come in one phase for correctness. There is only one method, and passing all tests associated with this method will earn you 40 points.