Coding Task 2 - Linked Lists

Time Estimate: 12 hours
Jump to current week
Requirements

Project Structure

You will continue to add functionality to your existing project from the previous task. There is no new repository to clone.

For this task, you will be writing code in the following classes:

  • SampleTopDownGame, located in the package app.games
  • Enemy, located in the package app.games.topdownobjects

You will also need to create new classes in these locations with these names (case-sensitive):

  • Pathfinding, in the package app.gameengine.model.ai (You will also need to create the ai package in the specified location. To do this, right-click the model package and choose new -> package)
  • TestTask2, in the package tests

You will also be using the provided LinkedListNode class from the app.gameengine.model.datastructures package. You may find it helpful to add methods to this class, however you cannot modify or remove any of the given code. You can use these additions in your implementation, but not in your tests (the TestTask2 class). The solutions in Autolab will use this class as given so using extra methods in your tests will cause errors when your tests are ran against these solutions.


Overview Video

Video link: https://youtu.be/kNhIJL5VPkk?si=i3aTK3mdM4OSiZfA

Our amazing TA Josh has made another overview video for Task 2. This video goes over the specifications for the task, the LinkedListNode class you will be using, and a conceptual overview of the goals for this task. It also covers some practical examples of using recursion in this task, which is not required, but is highly recommended. It is available on the cse116 Youtube channel, and is linked above

As before, watching this video is optional, and all of the information you need for this task is contained within this page. However, you may find it helpful for getting a better understanding of the task, and what is expected of you

Specification

In this task, you will test and implement the following specs. All methods are public and non-static, except for the findPath method which is static.

First, we'll update the SampleTopDownGame to use a Linked List of levels to control the flow of the game. Players will travel through each level in this list as they play through the game

  • SampleTopDownGame - Linked List Operations
    • Currently, the way the game handles loading levels is poorly implemented by hard-coding level names using conditionals. The first part of this task will be to improve it using a Linked List to store a sequence of levels. Players will start at the first level in the list and each time they advance to the next level they will move to the next level in the list
    • To implement the methods in this section, you will need to create an instance variable of type LinkedListNode of Level in the SampleTopDownGame class named llL for linked list level. Then, add the following methods in this class that will interact with your instance variable. This list should initially be empty (Please use the provided app.gameengine.model.datastructures.LinkedListNode class for your linked list)
    • getLevelList: Take no parameters and returns the head of the LinkedListNode of Levels stored in your instance variable
      • If no Levels have been added, this method should return null
    • setLevelList: Takes a LinkedListNode of Levels and returns void
      • This method replaces the instance variable representing the head of the list with the LinkedListNode in the parameter
    • addLevel: Takes a Level and returns void
      • This method appends the Level specified in the parameter to the end of the Linked List of levels.
    • removeLevelByName: Takes a String and returns void
      • This method removes the level with the specified name String from the Linked List of levels
      • If multiple Levels exist with this name, it only removes the first one that appears in the list
      • You can use the getName method within a level to get the name of that level as a String
  • SampleTopDownGame - Modifications
    • With the Linked List operations the following modifications will be made to utilize the linked list:
      • The init method will be modified to add the three given levels to the Linked List before the given loadLevel call. The resulting list should contain the levels returned by the methods levelZero, levelOne, and levelTwo in this order and call loadLevel on the first level in the list ("level0")
      • Replace the body of the advanceLevel method to use the Linked List of levels. When this method is called, call this.loadLevel on the next level in the list. To do this, first find the current level in the list then get the level at the next node
        • You should use the getCurrentLevel method to access the current level.
        • You can use the getName method within a level to get the name of that level as a String
        • If the game is already on the last level, this method has no effect (ie. Do not call loadLevel with an argument of null)
    • With these changes, you should be able to play through the 3 levels of the game as before. However, it will now be much easier to add more levels to the game and create new games with any number of levels without maintaining a giant if/else block

Now, will see another application of Linked Lists by adding movement to the enemies of our game. Your code will compute paths for enemies to follow and set their velocity to travel these paths. With these updates, the enemies will hunt the player.

  • Pathfinding - findPath method
    • Create a class named Pathfinding in the app.gameengine.model.ai package (You'll also have to create this ai package)
    • In the Pathfinding class you created, write a static method called findPath that takes in two Vector2D objects as parameters and returns a LinkedListNode of Vector2Ds.
    • This method returns a shortest valid path that travels from the tile containing the first Vector2D object to the tile containing the location of the second Vector2D object.
      • To compute the tile containing a vector, you can take the floor of each coordinate in the vector. Recall that locations for rectangles are the location of their upper-left corner
        • The vector (3.9, 4.6) is contained on the tile at location (3.0, 4.0)
      • A path is valid if each Vector2D object after the head of the list is one tile above, below, to the left, or to the right of the previous one AND if each Vector2D object in the list is aligned to a tile (i.e. no decimals). Considered the following paths attempting to travel from eg. (3.9, 4.6) to (5.2, 5.999)
        • [(3.0, 4.0), (3.0, 5.0), (4.0, 5.0), (5.0, 5.0)] is valid.
        • [(3.0, 4.0), (3.0, 5.0), (5.0, 5.0)] is not valid as the third Vector2D is two tiles right of the second.
        • [(3.0, 4.0), (4.0, 5.0), (5.0, 5.0)] is not valid as the second Vector2D is diagonal to the first one.
        • [(3.9, 4.6), (3.1, 5.9), (4.6, 5.5), (5.2, 5.999)] is not valid as it is not aligned to a tile.
      • You may find it helpful to review the overview of the coordinate system in the task 1 handout.
      • Note that there are many correct solutions for this method since there are multiple valid paths that all minimal length (unless the start and end share a coordinate). For example, traveling from (0.2, 0.5) to (1.8, 1.3) both [(0.0, 0.0), (0.0, 1.0), (1.0, 1.0)] and [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)] are both correct solutions. When writing test cases, all valid paths must be treated as correct
  • Enemy Movement - Path Operations
    • Once this is complete, Enemies will be able to create and follow paths in game, which will be represented by a LinkedListNode of Vector2D objects. Add these methods to the app.games.topdownobjects.Enemy class
    • setPath: Takes a LinkedListNode of Vector2D objects and returns void. This method sets an instance variable (That you'll create) representing the Enemy's path that they'll follow
    • getPath: Takes no parameters and returns a LinkedListNode of Vector2D objects. This method returns the instance variable representing the Enemy's path
    • The initial value of your path instance variable can be null
    • update: Takes a double and a Level and returns void. This method is called every frame (60 times per second) and the double represents the number of seconds that have passed since the last update which won't be used in this task. You will add functionality to this method so enemies will "hunt" the player:
      • Note: in each update call, only one of these three things can happen (eg. an Enemy will not assign itself a path and start moving in the same call)
        • Compute a path: If the Enemy's path LinkedListNode is null, use the findPath method from the Pathfinding class to generate a path from the Enemy's location to the Level's Player's location. You have access to the player through the level object parameter. This path will then be stored in your instance variable (The same one controlled by setPath and getPath)
        • Advance to the next node in the path: If the Enemy is directly on the tile at the path's head, the Enemy's position is manually set to the location of the tile. The head of the list is then removed from the list so the enemy will travel to the next node
          • An enemy is considered to be "directly on" a tile if its distance from the tile is less than 0.01. Use Euclidean distance for this calculation (Square root of the sum of the squares of differences in each dimension)
          • This is necessary to prevent enemies from getting caught at the edge of a hitbox
          • When this happens, do not also set the velocity on the same call of update
        • Travel along the path: If neither of the 2 previous conditions apply, the Enemy's velocity is set to move towards the tile at the head of the Enemy's path
          • The Enemy's velocity must have a magnitude (speed) of 1.0
          • Since the Enemy can only move in four directions, only one component (x or y) of a moving Enemy's velocity will be non-zero at any point. This means there are only 4 possible values for the enemies velocity (1.0, 0.0), (0.0, 1.0), (-1.0, 0.0), (0.0, -1.0)

Note: You can see feedback in Autolab for your testing utilities and tests without completing the programming portion of this task, but you must at least create the classes and methods that you test. 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.


Testing Utilities

Create a class named TestTask2 in the tests package and write the following methods in that class (Note: Do not add the @Test annotation to these methods since they are not tests):

  • validatePath - Write a method named validatePath that:
    • Takes a LinkedListNode of Vector2D objects and returns void
    • This method fails a JUnit assert if the path from the parameter 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), and each vector must have x and y components that are whole numbers.
    • Note that you are not checking if the path travels between 2 specific tiles, just that it is a valid path between any 2 tiles.
    • Consider an input path of null to be valid
    • Consider an input path with only one vector to be valid as long as it's components are whole numbers.

Testing Requirements

Add test methods to the tests.TestTask2 class, using the @Test annotation, that tests the following method from the specification:

  • Test the findPath method from the Pathfinding class
    • Calling the validatePath testing utility method can make this much simpler to test. Don't forget to also check that the length of the returned path matches the shortest length

Programming Requirements

Implement all the functionality from the specification.


Autolab Feedback

The feedback in Autolab will be given in 4 phases. If you don't complete a phase, then feedback for the following phase(s) will not be provided.

  1. Testing your testing utility method
    • Your testing utility method will be checked with a variety of test cases to ensure that they make all the required checks. This phase will ensure that your utility method is accurate before you start using it in your tests
  2. Running your tests on a correct solution
    • Your tests will be run against a solution that is known to be correct. If your tests do not pass this correct solution, there is an error somewhere in your tests that must be fixed before you can move on with the assignment. If your tests don't get past this check, you should re-read this document and make sure you implemented your tests and code according the specification. You should also make sure that if there are multiple correct outputs to the input in your tests cases that you accept any of the outputs as correct
  3. Checking your tests for feature coverage
    • The next phase is to check if your tests check for a variety of features defined by different inputs. You should write at least one test case for each feature to pass this phase
    • Passing this phase does not necessarily mean that your testing is completely thorough. Satisfying Autolab is the bare minimum testing requirement. Not all possible inputs are checked, and it is sometimes possible to pass this phase with weak testing. If you are struggling to earn credit for code that you believe is correct, you should write more than the required tests
  4. Running my tests on your solution
    • Once Autolab is happy with your tests, it will run my tests against your code to check it for correctness. If your testing is thorough, and your code passes your tests, then you should pass this phase. If you pass your tests, but fail one of mine, it is an indicator that you should write more tests to help expose your bug

Once you complete all 4 phases, you will have completed this Task and Autolab will confirm this with a score of 1.0 for complete.