Coding Task 4 - Binary Trees

Time Estimate: 10 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.

Overview Video

Video link: https://youtu.be/pdIPmXGCpVU

You get it by now

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 implement the following specs. Once all of these are complete, your enemies will have an AI that allows them to make decisions based on their surrounding environment.

  • Before we begin with the AI implementation, there are some additional features we will need to add to the game to make it more "game-like".
  • DynamicGameObject - Invincibility Frames (app.gameengine.model.gameobjects.DynamicGameObject)
    • In game development, invincibility frames (Or i-frames) are a short period of time when players become immune to taking damage. They're used to prevent players from constantly taking damage every frame from the same source without having the opportunity to escape danger. In this part of the task, you will implement invincibility frames for the players so that enemies can now deal the proper amount of damage
    • Add an instance variable of type double to the DynamicGameObject class representing the amount of time remaining on their invincibility frame timer in seconds. This should be initialized to 0.0 since i-frames will not start until triggered by a game action (ie. The player getting hit by an enemy). Add getters and setters for this instance variable named getInvincibilityFrames and setInvincibilityFrames
    • Override the update method that was inherited from the GameObject class
      • Your overridden method should begin with a call to the superclass' update method since we still want the functionality of the super class. Pass the parameters of this method as the arguments for the super method call
      • This method should then subtract the invincibility time (The instance variable you just created) by the change in time (dt from the parameter of this method), where dt is the number of seconds elapsed since the last time update was called. Note that the game runs at 60 fps (frames per second) so dt should be about 0.0167 seconds when it's called during gameplay. This number can be different during testing.
      • This method should then check if the object's hp is 0 or less. If it is, call its destroy method
  • Projectile (app.games.topdownobjects.Projectile)
    • Modify the existing overridden collideWithDynamicObject method in Projectile to deal damage to the other object rather than destroying them. (Replace the call to otherObject.destroy with otherObject.takeDamage.) Use the projectile's damage instance variable in your call to takeDamage
    • Be sure to still destroy the projectile itself when it hits an object
  • Enemy (app.games.topdownobjects.Enemy)
    • Modify the existing overridden collideWithDynamicObject method to deal damage to the player rather than destroying them. The amount of damage dealt (By calling the takeDamage method) should be equal to the enemy's strength instance variable.
      • Your method should check if the player has more than 0.0 seconds left on their invincibility frames timer (by calling the corresponding getter). If so, the method should do nothing. If the player doesn't have any invincibility time left, you should have the Player take damage equal to the enemy's strength instance, then set the amount of invincibility time to 0.5 seconds
    • Move the instance variable for the enemy's path you made in task 2 into DynamicGameObject, along with the getter getPath and setter setPath. Since Enemy extends DynamicGameObject, this should not have any effect on the game because of the power of inheritance.
    • Delete the update method. Enemies will now use the inherited update method unaltered. For pathing behavior, we will add decision trees to make enemies do more than always move towards the player (You should save this code in a safe place as it will be reused in the decision tree. If you lose your code, you can always download your old submissions from Autolab to recover it)

Now, you should be able to run into enemies and watch your health go down in the UI without instantly being reset to the beginning of the level. You should also be able to shoot enemies and have them take damage rather than dying right away.
Note that the default projectile damage is 5, meaning you can kill enemies in 2 hits. If you wish to change this, you can edit the actionButtonPressed method in app.gameengine.Level to create projectiles which deal more or less damage. This should not interfere with testing in Autolab, since this method is only called when the game is running

Now let's start working with trees. For the rest of this task, you will build a decision tree for the AI of the enemies. Each node of the tree will either make a decision (Move to the left or right child), or take an action (when we reach a leaf of the tree, a node with no children). You'll create a variety of new classes to implement this functionality.

  • Decision (app.gameengine.model.ai)
    • In the ai package, create a new class named Decision
    • Create a constructor that takes a String as a parameter representing the decision's name and store this value in an instance variable
    • Create a getter and setter getName and setName for the name instance variable. This name will be used when testing and debugging your decision tree
    • Create a method named decide that returns a boolean and takes in a reference to a DynamicGameObject, Level, and a double dt (in this order). This method should be blank initially (just return false). You will be overriding this method using inheritance
      • This is the method that will be called when deciding to move left or right in the decision tree if the node is an internal node (Not a leaf)
    • Create a method named doAction that returns void and takes in a reference to a DynamicGameObject, Level, and a double dt (again, in this order). This method should be blank and will also be overridden using inheritance
      • This is the method that will be called to take the action that has been deciding after reaching a leaf node
  • DecisionTree (app.gameengine.model.ai)
    • In the ai package, create a new class named DecisionTree
    • Create a constructor that takes in a BinaryTreeNode<Decision> and store it in an instance variable
    • Create a getter getTree and a setter setTree for that instance variable
    • Create a method named traverse that returns a reference to a Decision and takes a BinaryTreeNode<Decision>, DynamicGameObject, Level, and double dt as parameters (In this order)
      • This method will traverse through the tree in the parameter (Not the tree in your instance variable), making decisions to go left or right by calling decide on the value of each tree node. A value of true indicates that you should "travel" to the right child node, and a value of false means travel to the left child node. When a leaf node is reached (A node where both left and right children are null), the Decision value at that node should be returned. Keep in mind that the node in the parameter itself might be a leaf node
      • When calling decide, pass the required arguments using the parameters of this method
      • If no leaf node is reached, the method should return null to indicate that something went wrong. This can happen if the tree is empty, or if the tree has a node with only one child. In the case of a node with only one child, the method should return null if that node's decision tells it to traverse in the opposite direction of that child (eg. The tree only has a left node so it's not a leaf, but it tells you to travel right which is null). Otherwise, it should continue the traversal
    • Create a second (overloaded) traverse method that returns void and takes a DynamicGameObject, Level, and double dt as parameters (In that order). This method will call the traverse method you wrote previously with the instance variable tree as the first argument and all the parameters of this method as the remaining arguments. Then call doAction on the returned Decision, again using the parameters of this method as arguments
      • If the returned Decision is null, do nothing
    • Create a method reverse that returns void and takes a reference to a BinaryTreeNode<Decision> as a parameter
      • This method will reverse the binary tree, switching the left and right nodes all the way down the tree. Meaning that every single node's left and right children should be switched
        • Example image of reversing a binary tree
      • This method can allow you to "confuse" an enemy--Instead of making the enemy heal when they have low HP and move towards the player when they're not low on HP, you can make the enemy move towards the player on low HP and heal when they're not on low HP. (This will make sense when you get to the next part of the handout).
    • Create a second (overloaded) reverse method that returns void and takes no parameters. This method will call the reverse method you wrote previously with the instance variable tree as the argument
  • Decision child classes (app.gameengine.model.ai)
    • Write the following classes in the ai package. While the amount of classes here may seem daunting, each class, ignoring all the imports and class declaration boilerplate, should have relatively few lines of code; try not to overthink these classes.
    • Decisions will be written such that they only override one of decide/doAction. The nodes that override doAction will be placed in your tree as leaf nodes, and the nodes that override decide will be placed in your tree with two child nodes. This will allow us to give enemies complex behavior based on their surroundings.
      • LowHP
        • Create the LowHP class that extends Decision. Add a constructor that takes in a String for the name (so that the super constructor may be called) and an int representing the HP threshold the enemy should have before it's considered "low" on HP. You should make an instance variable to store this value
          • All constructors in this section will take a name that will only be used as the argument for the super constructor call
        • Override decide and return true if the DynamicGameObject's health is less than or equal to the Decision's low HP threshold
      • NearPlayer
        • Create the NearPlayer class that extends Decision. Add a constructor that takes in a String for the name (so that the super constructor may be called) and a double representing the acceptable distance that this node should use. You should make an instance variable to store this distance
        • Override the decide method and return true if the distance between the DynamicGameObject and the player is less than or equal to the acceptable distance instance variable and false otherwise. You can access the player through the level object (Hint: Use the Pythagorean theorem/Euclidean Distance to determine distance!)
      • TargetingPlayer
        • Create the TargetingPlayer class that extends Decision. Add a constructor that takes in a String for the name (so that the super constructor may be called) and a double representing the distance the player can stray from where the DynamicGameObject is targeting. You should make an instance variable to store this distance.
        • Override the decide method and will return true if the distance from the DynamicGameObject's target destination (the tail node of their path) to the player's current location is less than or equal to the distance instance variable and false otherwise (as previously, you should being using the Euclidean Distance in your calculation). Also return false if the path is empty
      • MoveTowardsPlayer
        • Create the MoveTowardsPlayer class that extends Decision. Add a constructor that takes in a string for the name and call the super constructor; there are no additional parameters or instance variables for this class
        • Override the doAction method and make the DynamicGameObject move towards the player. (Hint: you should move all your update code in Enemy from task 2 to this method. This includes all 3 cases that we had to either calculate a path, remove the head of the path, or travel to the head of the path)
      • Heal
        • Create the Heal class that extends Decision. Add a constructor that takes in a String for the name (so that the super constructor may be called), an int representing the health to heal, and a double representing the cooldown time before healing. You should make 2 instance variables to store these values. You will also want a 3rd instance variable storing the amount of time spent on this node
        • Override the doAction method to heal the DynamicGameObject once the cooldown expires. When this method is called, use the dt parameter to add the total time that has elapsed across all calls of this method (ie. by adding this time to your 3rd instance variable). If the value of this 3rd variable (The total time spent on this node) is greater than or equal to the cooldown time (The 3rd constructor parameter), heal the DynamicGameObject (Using get/set hp) by the amount given by the 2nd constructor parameter. When the object heals, reset your 3rd instance variable so they have to wait for the cooldown again before healing
        • While healing, the object should not be allowed to move. Each time the doAction method is called, both x and y velocity should be set to 0
        • Additional considerations:
          • While it is not required, you may wish to change the sprite of the DynamicGameObject while it's healing. To do this, you can take a look at how animations are handled in app.gameengine.controller.WASDMovement and app.gameengine.model.gameobjects.Player
          • Again, this is by no means required to complete the task and get credit on autolab, but it can be a fun rabbithole to go down and can make your game feel more like your own.
      • RecalculatePath
        • Create the RecalculatePath class that extends Decision. Add a constructor that takes in a string for the name and call the super constructor; there is no additional instance variables you will need.
        • Override the doAction method and should set the DynamicGameObject's velocity to 0 and recalculate the DynamicGameObject's path with the destination at the player just like in MoveTowardsPlayer (Set their path to the result of Pathfinding.findPath). You do not have to handle all 3 cases like before. Always set their path when this method is called
        • Note: Combining this with TargetingPlayer will allow you to build trees that will update the path as the player moves so enemies are no longer moving to your old position
      • RunAway
        • Create the RunAway class that extends Decision. Add a constructor that takes in a string for the name and call the super constructor; there is no additional instance variables you will need.
        • Override the doAction method and will do the same as what MoveTowardsPlayer does, but the velocity should be reversed (multiplied by -1)
  • DynamicGameObject - DecisionTree implementation
    • Now that you have implemented your decision tree, you can implement it into your game! You should give DynamicGameObject a DecisionTree instance variable, along with a getter getDecisionTree and a setter setDecisionTree. Modify the update method to call traverse on the DynamicGameObject's instance variable if it is not null (the DynamicGameObject parameter in traverse should be this and the remaining arguments come from the parameters of the update call). In the Enemy constructor, you should assign the DecisionTree to have one node containing a MoveTowardsPlayer decision. This is important so that the default behavior of an enemy remains unchanged, and your Task 2 tests still pass
      Note: There are two constructors in the Enemy class. You should add the decision tree in the constructor which takes two parameters, as the other constructor simply calls this one
      Now, you can assign decision trees to enemies to create more complex behavior. To see this in-game, you should create and set decision trees in the SampleTopDownGame class for each enemy that you wish to enhance.
      • Feel free to get creative! Experiment around, try to come up with interesting behaviors for enemies. Keep an eye out on piazza, because we will be sharing some DecisionTrees and Decisions of our own that you can add to your game.

Note: You can see feedback in Autolab for your tests without completing the programming portion of this task, but you must at least create every class/method from this specification. 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

Write a public static method named compareBinaryTreesOfDecisions in the app.tests.TestTask4 class that returns void and takes two BinaryTreeNode of Decisions as parameters. This method should fail a junit assert if the two trees are not equal and do nothing if they are equal. You should compare the inner Decision value's getName method to check for equality. Two nodes are considered equal, according to this method, as long as their names are the same. The trees must additionally have identical structures


Testing Class

Testing your traverse method using the Decision child classes you created previously would be quite difficult and tedious. You would need to create a game, level, player, and enemy with specific characteristics (eg. location, health, etc) so that the tree traversal happens in exactly the way you want. Because of this, it is highly recommended that you create a new class in your tests package that extends Decision. The name of this class is not important as long as it is in the tests package and is only used inside of the tests package. If either of these rules is not upheld, autolab will not be able to compile your code

The purpose of this testing class is to give you greater control over how the tree traversal occurs, without relying on complicated state of the game, level, player, and enemy. One possible way to achieve this control would be to make the constructor of this class take in a boolean, and have the decide method use this boolean to determine the direction to traverse.

You must also test that the doAction method is properly called when a leaf node is reached. To check this, your test decision class should also override the doAction to have some obvious and testable side effect on either the enemy or level object passed in to the method. The specifics of this side effect are unimportant, as long as you detect it properly in your tests.

Note: since this specific type of decision will never be used in game, it's okay that it doesn't make sense in the context of the game. For example, in this specific case, it is okay to override both the decide and doAction methods, even though this is prohibited for other types of decisions.

This class is not required and will not be tested on autolab, but it is recommended that you do this as it will make your testing significantly easier.


Testing Requirements

Create a class named TestTask4 in the tests package.

You will write tests for the following functionality from the specification:

  • Write tests for the traverse & reverse methods in the DecisionTree class
    • When testing the reverse method, you should test the version that takes no parameters. When testing the traverse method, you must test the version that returns void. It may also be helpful to test the other version. The reason for this is that the other methods are helper methods, so testing the base methods will test both
    • When checking if the tree was properly reversed, you only need to check the name of each decision at each node. If their names are the same, we consider them to be the same node for the purposes of this test (ie. Call your testing utility method with a tree that has the names you expect)
    • If you choose hard mode by not creating and using the optional test class, you will need to create meaningful DynamicGameObjects and Levels in your tests. If you use a test class, these arguments can be null as long as you don't use them in your test class (Which would cause a null pointer exception)

While you are not required to use your testing utility and test object, it is recommended. They will make your tests considerably easier to write.


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.