Assignment 1.1 - Monster Battles
This is an individual open-book home assignment. It involves interacting with a game that is broken up into a set of programming questions. We provide a small set of tests to allow you to check the correctness of your solutions. However, these tests are not exhaustive, and passing the tests does not guarantee full marks. You should perform your own testing to ensure your solution is coded correctly.
The code scaffold can be found here .DO NO FORK THE REPOSITORY. Please use the 'Use Template' button instead
The assignment is worth 100 marks. 50 marks are for the code. 50 marks are for an individual written interview testing your knowledge of the theory, to be conducted during Week 6
The code part of the assignment is due on Friday Week 5 (25 August 2023 11.55 PM Melbourne time for Clayton students, 11.55PM MA time for Malaysian students)
For Malaysian Students - Since we can't extend the deadline for Malaysian students, any submission made in the last 3 hours of the deadline will be marked as late on Ed, but will not be considered late. Please ignore the message.
The final submission of the assignment is to be done through Ed. See this post for details on how to submit.
Please check the rubric for the assessment criteria
10% deduction per calendar day or part thereof for up to one week Submissions more than 7 calendar days after the due date will receive a mark of zero (0) and no assessment feedback will be provided. Generative AI tools cannot be used in this assessment task: In this assessment, you must not use generative artificial intelligence (AI) to generate any materials or content in relation to the assessment task.
Welcome to A1.1 - Monster Battles!
Welcome to Monster Battles. Monster Battles is a game played between teams of opposing monsters in an attempt to see who is the very best, like no one ever was! Monsters have stats like attack and defense, can evolve into other monsters, and level up.
In this assignment you'll be working on many of the features of the Monster Battles game, which should also test you on your ability to apply the concepts covered in the first 4 weeks of Fundamentals of Algorithms.
But, this is too easy! To make sure you are demonstrating all of the topics covered in this unit, the following restrictions are in place.
Any use of python inbuilt lists, dictionaries, sets, etc. Is banned. Use of such structures nulls both the test case and approach marks for the affected task. You can however use fixed size tuples.
Accessing the internals of the data_structures classes outside of the definition of the class is strictly prohibited (You can't access .array of CircularQueue for example, only interact with its methods)
Not only does your code need to be functional, it needs to be the most efficient choice that is best suited for the problem. In general, if there is a choice that is efficient and requires less code, not choosing this will lose you marks (So don't use an array when a queue would also work).
With all that in mind, make sure to read the next slide for a bunch of small tid-bits and we hope you enjoy this assignment!Any semblance to other RPG games with monsters (particularly those that fit in the pocket) that battle and evolve is purely coincidence 😉.
Tools used for image generation:
Important Information, Tips and Tricks
Important Information, Tips and Tricks
Before you get working on the application, please read these tips & tricks to ensure you don't get lost, or lose any silly marks!
Common Mistakes / Advice
Except for task 1, Every method you implement requires complexity analysis in the docstring. This should include both best and worst case analysis! Be sure to state your variables You can include a catch all at the top of your class definition to avoid writing constant time for a bunch of methods. "Unless stated otherwise, all methods in this classes are O(1) best/worst case." Use the RandomGen class from random_gen for anything where the task says to use random generation You are marked on correctness in Ed. It doesn't matter if your code passes locally, it needs to pass in Ed. Contact a TA if you are having trouble achieving parity. Be careful of the specific Python version used, and don't import any other third party modules excluding those already in requirements.txt . If introducing new classes, consider using dataclasses to simplify this definition. Separate your code into small methods of at most 20 lines, and try to abstract logic if you find lots of duplicated work.
First, ensure you've installed python locally, then install the required packages with py -m pip install -r requirements.txt (you must execute this in the downloaded project scaffold). Other than setting up your IDE , that should be everything sorted!
To run tests, call py run_tests.py . Note that you can restrict which tests are run using a second argument. For example, running py run_tests.py 1 will only run tests from the tests/test_monster_base.py file.
Basic Introduction to Monster Battles
The titular Monsters are the backbone of the Monster Battles. There are different types of monsters each with their own names and stats, and one type of a monster can evolve into another type of a monster when they level up.
Monsters have the following information:
- Maximum Hit Points (Max HP)
- Attack Points (Attack)
- Defense Points (Defense)
- Speed Points (Speed)
- Evolution Line
Some of these will be covered more in-depth when battles are covered, but the gist is the monsters have 5 main battle stats - Attack, Defense, Speed, Max HP, Element - that are defined at a per monster type level, and a few stats that change over time for each monster - their current HP and level. In terms of the code design, Each monster type has it's own class (deriving from MonsterBase ), which contains methods to retrieve the static bits of information, but each actual monster is an instance of this class, allowing it to store specific information like HP and Level: Monster evolution will be covered later on in the slide.
What is MonsterBase?
Because there are over 40 Monsters to define, and we don't want to write out all the classes individually, there are some smart automations defined in helpers.py . In particular, because almost all of the logic for all 41 Monsters are the same, all we have to do is define this shared logic in MonsterBase . Then helpers.py reads the file monsters.yaml , and dynamically creates 41 different classes, which all inherit from MonsterBase , and implements all of the abstract class methods at the bottom of monster_base.py .
For example, you can do the following without touching the assignment and it works just fine:
from helpers import Flamikin print(Flamikin.get_name()) # Flamikin print(Flamikin.get_description()) # A small, fiery creature with a passion for battle that evolves into # a larger, more powerful form. print(Flamikin.get_evolution()) # Class called Infernoth print(Flamikin.get_simple_stats().get_max_hp()) # Not implemented yet :)
So when implementing MonsterBase , know that you can use the abstract class methods as if they are implemented.
Complex vs. Simple Mode
In order to make the game approachable but also complex, two modes of play are defined. Each Monster has a set of "Simple" stats, and a set of "Complex" stats. Simple stats just gives every stat a single unchanging number, while Complex stats allow for expressions which take variables. For example, Leviatitan might have the following simple stats:simple: attack: 4 defense: 8 max_hp: 15 speed: 2But it might have more complicated complex stats, using a post�x expression (described further in Task 4):complex: attack: 4 2 + defense: 8 1.1 level power max_hp: 15 5 level 10 level middle speed: 2 level sqrtWhen a Monster is initialised, a parameter simple_mode is passed through, which determines whether to use the simple stats, or complex stats, in the stat calculation for the monster. You can see all de�nitions of Monsters in monsters.yaml , but you won't need to read/change this as part of the assignment.
Monsters are combined to form teams, which are used in battle. There are multiple options for teams, such as the team mode, and selection mode, but these will be covered in more detail in task 3.If you look at monster.yaml , you'll notice some monsters are marked as can_be_spawned . Those without this tag cannot be initially included in a team, but can only be reached through battling and evolving the spawnable monsters.
Battling is done between two teams in a turn based manner, where every "turn" includes an action from both teams. In a battle, each team selects one monster to be currently out on the �eld, while the rest of each team waits to help out.
In a battle, turns continue to occur until one or both teams have no more monsters left (in the team and on the �eld). If a monster on the �eld is killed (HP <= 0), then a new monster from the team is sent out at the end of the turn.
In a turn, each team selects an action, either ATTACK , SPECIAL or SWAP. If SWAP is chosen, the currently out on the �eld monster is returned to the team, and a new monster from the team is selected (possibly the same monster). If SPECIAL is chosen, the monster is returned to the team, the method .special() is called on the team object, and a monster is retrieved from the team (possibly the same monster). If ATTACK is chosen, then the currently out on the �eld monster attacks the currently out on the �eld monster for the other team.
Two things to note:
- SWAP/SPECIAL actions are always completed before ATTACK actions
- If both teams ATTACK, then some special logic occurs: The monster with the higher speed stat attacks �rst. If the slower monster is still alive after this (HP > 0), then it can attack in retaliation. If the speed stat of both monsters is equal, then both monsters attack simultaneously, ignoring whether the attack they are receiving would kill them.
The process of monster1 attacking monster2 is de�ned as follows: Step 1: Compute the damage This is done by comparing monster1's attack (call it attack) and monster2's defense (call it defense). If defense < attack / 2 : damage = attack - defense Otherwise, If defence < attack : damage = attack 5/8 - defense / 4 Otherwise, damage = attack / 4 Step 2: Apply element effectiveness When two monsters attack, the element of each monster is considered. For example, Leviatitan is a Water Elemental Monster, where as Infernox is a Fire Elemental Monster. Since Water has an e�ectiveness coe�cient of 2 against Fire, this is used to multiply by the calculated damage: effective_damage = damage 2 Step 3: Get the ceiling of the e�ective_damage Since at this point the damage may have a decimal component, round this number up. Step 4: Deduct HP from monster2 equal to the e�ective_damage.
If at the end of a turn, one monster is alive and the other is not, then the alive monster levels up. This may change the monster's stats, and if they have an evolution, will force the monster to evolve. When leveling up the di�erence between a monster's max hp and current hp must be maintained.
Some Monster types can evolve into other Monster types. The MonsterBase method get_evolution
will tell you whether it is possible for this monster type to evolve. If this method returns None, then the Monster cannot evolve. Otherwise the returned value is the class of the evolved Monster type. For example Flamikin.get_evolution() == Infernoth .
However, in order for a Monster (object) to evolve in battle, the following must be true:
- The monster type must be able to evolve (get_evolution is not None)
- The monster must be a di�erent level from the one it originally started as
In order to evolve a Monster, the evolve method is called. The evolve method, rather than modifying the current Monster object, returns a completely new Monster object, using the class returned from get_evolution . Additionally, the level and the di�erence between current HP and max HP should be preserved. So if a LV 2. 4/6HP Flamikin evolves, it should become a LV 2. 6/8HP Infernoth. Note: You might've noticed we mentioned twice that "the di�erence between current HP and max HP should be preserved". This is because the max_hp can change in both scenarios (when a Monster levels up or when a Monster evolves). So make sure you preserve the hp in both of these cases (they could even happen at the same time e.g. a monster could level up and its max_hp will change, then because it levelled up it will also evolve and its max_hp will change again).
The Battle Tower is a battle feature where one team faces a gauntlet of other teams in succession, and is covered in more detail in Task 5.
[TASK] Basic Monster StatsA reminder that use of inbuilt lists, dictionaries, sets are banned, and using less suited data structures will result in loss of marks.Before we can start implementing the battles and various systems in this game, we need to �rst implement the backbone of our game - The Monsters! In this task we have two main objectives:
- Implement the SimpleStats class in stats.py.
- Implement the required functionality for MonsterBase in monster_base.py .
As was discussed previously, Monster Battles can be played in two modes - Simple Stats and Complex Stats. In simple stats, the statistics of each Monster is static (unchanging), and speci�ed as an integer. In this task, we are simply implementing the SimpleStats class, which is initialised with 4 integer values - the statistics for attack, defense, speed, and max hp. You then just need to de�ne the four instance methods get_attack, get_defense, get_speed, and get_max_hp, which returns the relevant statistics.
- Now that we have a statistics class, we want to implement all of the helper methods that makes us able to use di�erent Monsters for battle. Monsters take in two parameters for initialisation,
- simple_mode and level.
- simple_mode is a boolean which determines whether to use the simple or complex stats
- module when computing stats like get_attack .
- level simply provides a starting level for the monster, defaulting to 1.
To complete this task, you need to implement the following methods for the MonsterBase: init get_level , get_hp, get_attack , get_defense , get_speed , get_max_hp level_up, set_hp, ready_to_evolve - whether the monster can evolve and their level is di�erent from its original value. alive and evolve Some method so that str(obj), where obj is an instance of MonsterBase , returns a string like the following: "LV.3 Flamikin, 5/6 HP" For the methods above, you can use the class methods de�ned at the bottom of the �le, such as get_element , get_evolution , get_simple_stats (You can assume all of these are already de�ned for your MonsterBase instance. Simple call them like self.get_evolution() . To be clear - you don't need to make individual classes for each Monster Type - this is done for you in helpers.py , which reads the yaml �le and creates the classes dynamically. You are only implementing the "glue" the makes all monster classes work. See the previous slide for more information
[TASK] Element E�ectiveness
A reminder that use of inbuilt lists, dictionaries, sets are banned, and using less suited data structures will result in loss of marks.Another important piece of the puzzle is calculating the multiplier used when one elemental monster is attacking another.
Luckily, all of this information is provided in type_effectiveness.csv , along with all the element names as well, and a good portion of the sca�old has already been provided in elements.py . elements.py de�nes two di�erent classes, Element and EffectivenessCalculator . The former is simply an Enumeration which de�nes all of the elements that monsters can have, while the EffectivenessCalculator gives an easy interface to determine what damage multiplier should be used between two elements.
For example, if you are a Fire elemental monster like Flamikin, attacking a Water elemental monster like Leviatitan, then the damage multiplier would be:print(EffectivenessCalculator.get_effectiveness(Element.FIRE, Element.WATER))# 0.5, if using the type_effectiveness.csv file.Your task is to edit the EffectivenessCalculator methods: init, and get_effectiveness See the docstrings of these two methods for a description of their arguments and process. You shouldn't touch anything else in this �le, but feel free to read it if you feel this would help.
[TASK] Monster Team
A reminder that use of inbuilt lists, dictionaries, sets are banned, and using less suited data structures will result in loss of marks.For methods that di�er in complexity based on the team mode selected, please include separate complexity analysis for all 3 team modes (For example, O(1) best/worst for FRONT, O(1) best/worst for BACK, O(n^5log(n!)) for OPTIMISE)Now that we have Monsters and can create them and view stats, it's time to group them into a team, in preparation for our battles! Teams are a bit complicated, and have a few di�erent options on creation, so we'll go through all the details here.
What is a Team?
A team is an ordered collection of Monsters, with an upper limit on the total number of monsters contained (this is currently set at 6, but you should design your code so that this limit is easily adjustable)
Teams have the following methods:
- init , to initialise the team. This takes some additional arguments to determine how initialisation occurs.
- add_to_team / retrieve_from_team , to add/retrieve monsters from the team
- choose_action , to determine a battle action in later tasks (ignore)
- regenerate_team , to revert the team to how it was on initialisation (Spawned Monsters, Level 1, Full Health)
- special, which does a certain action depending on the team mode (more to come)
- len(team) should return the total number of monsters currently in the team.
In a battle, monsters will be retrieved from the team and used in battle. If a monster is swapped out,
then it is added back into the team.
The way a team is ordered depends on the Team Mode. A team mode determines where a monster is placed in the ordering when it is added to the team. A monster is always retrieved from the front of the team. The team mode can be one of three values:
In TeamMode.FRONT, when a monster is added to a team, it is always added to the front of the team. Note that this means it is the monster that will be next retrieved from the team again. When team.special is used, the �rst 3 monsters at the front are reversed (Up to the current capacity of the team)
In TeamMode.BACK, when a monster is added to a team, it is always added to the back of the team. Note that this means this monster will be the last to be retrieved from the team. When team.special is used, the �rst half of the team is swapped with the second half (in an odd team size, the middle monster is in the bottom half), and the original second half of the team is reversed.
In TeamMode.OPTIMISE, when a monster is added to a team, it is added in the position which maintains the sorted order descending with respect to a particular stat, which is provided at initialisation. For example, if the initial stat was HP, then monsters would be inserted so that they are sorted by HP descending.
In the case of a draw in the statistic selected, you can order the monsters in either order. It does not matter.
When team.special is used, the sorting order toggles from descending to ascending (or vice-versa if used again).
In order to initialise a Team, we �rst need to select some monsters! This can be done in one of three ways:
- Manually - ask the user how many team members they want, and ask them to select the monster accordingly
- Provide the monsters as arguments to Team initialisation
The selectionmode passed to the initialiser of MonsterTeam determines which of these 3 processes to take. If this selection mode requires additional arguments, then you can pass these through the initialiser to be passed on to the selection* method. selection_random has been implemented for you, but the other two selection options need to be implemented.
So what do I need to do?
As part of this task, you need to implement the following methods on the MonsterTeam class:
- init - ingest the team_mode and selection_mode arguments, and pass any kwargs to
- the relevant selection_* method.
- add_to_team , retrieve_from_team - add/remove as appropriate. For team mode FRONT and
- BACK, these should be O(1) methods.
- special - do the special action depending on the team_mode - Reminder: these methods
- should not access ADT internals.
- select_manually , and select_provided - Implement the selection processes outlined above
- and in the docstring.
- len - Get the number of monsters in the current team.
[TASK] Battle & Complex Stats
A reminder that use of inbuilt lists, dictionaries, sets are banned, and using less suited data structures will result in loss of marks.Finally, we make it to the Battles :) Battles Most of the battle logic has already been discussed in the Basic Introduction slide, so there isn't a whole lot to cover here. In battle.py , we have the Battle class, with which you'll need to implement the following methods:
- process_turn : Completes a single "turn" of the battle procedure. You can assume battle()
has already been called.
To reiterate, process_turn should:
Handle all possible actions each team makes ( ATTACK, SWAP, SPECIAL)
Subtract 1 from HP if both survive
Handle level ups and evolutions
Return any fainted monsters and replace them with ones from the relevant team (if possible)
So far we've just been assuming that the simple stats for monsters were being used, but now we're going to use the complex ones instead. In monsters.yaml , each monster de�nes 4 values in the simple stats, and 4 expressions in the complex stats (which might also just be numbers). These complex expressions are written in post�x / reverse polish notation , where every operator is written after its operands. For example, 2 3 1 2 + - is (2 3) - (1 + 2) .
In the world of monster battles, we have the following operators:
- +, \/, -, *, acting as they usually do: a b / = a / b, etc.
- level - simply returns the current monster level
- power - a b power = a to the power of b.
- sqrt - a sqrt = the square root of a.
- middle - a b c middle = the median value between a, b and c (median of 9, 32, 14 is 14).
The result of the complex stats should always be integers, so please convert the �nal result using int(result) (but don't do this for every intermediate step). In stats.py, implement the functionality for ComplexStats . On init, the formulas will be passed in in the form of an array containing each element in the expression as a string, for example ['1.1', 'level', 'power'] for expression 1.1 level power .
[TASK] Battle Tower
A reminder that use of inbuilt lists,dictionaries, sets are banned, and using less suited data structures will result in loss of marks.The �nal task! In the monster battles game, what's better than a battle between Monsters? Why multiple of course!
In the battle tower, the player (with a team of monsters), faces a gauntlet of teams of monsters to battle.
Each team (both the player's team and the enemy teams) have some amount of lives. The enemy teams take it in turns to battle the player's team, and the result is either a win/loss or draw. The losing team loses a life, and in the result of a draw both teams lose a life.
The order in which enemy teams face up against the player team is determined in the following manner: Some initial ordering for the enemy teams is decided.
After all enemy teams have fought the player team, then of the remaining enemy teams, those with at least 1 life will �ght the player again, following the same initial ordering as before. Before every battle, regenerate_team is called on both teams to heal the entire team and revive fainted monsters.
So for example, suppose we have 3 enemy teams, A B and C, each with 2, 1 and 3 lives.
Then in the order of play, assuming that the player wins every battle:
- We face team A, B and then C
- We face team A, then C
- We face team C
The battle tower ends when there are no enemy teams left, or no lives left for the player team, or both.
Your task is to implement the following functionality in tower.py:
- init method: Initialises the class.
- set_my_team : Sets the player team for the battle tower, and generates between MIN_LIVES
- and MAX_LIVES lives
- generate_teams : Randomly generates the enemy teams. All teams must use team_mode
- BACK, and selection_mode RANDOM. Generate each team a number of lives between
- MIN_LIVES and MAX_LIVES , after each team is generated but before the next team is
- battles_remaining : Returns True if there are more battles to be had, False if either the player
- or all enemy teams have ran out of lives.
- next_battle : Simulates one battle in the tower, between the player team and the next enemy
- team. Returns 5 values: The battle result, the player team, the enemy team, the player lives
- remaining after the battle, and the enemy lives remaining after the battle.
- out_of_meta . The description of the out_of_meta method is below:
The out of meta method should compute what elements of monsters have been present in the battles in the battle tower so far, but are not present in the upcoming battle. For example, suppose we had a player team with a Fire and Grass Elemental Monsters, and two enemy teams:
Enemy Team 1 has Grass, Electric, Fairy and Water Elemental Monsters Enemy Team 2 has Fire, Electric and Normal Elemental Monsters
And suppose we've iterated over the object once, so the player team has fought enemy team 1, and the upcoming battle is the player team versus the enemy team 2. Then out_of_meta should return an Array containing two Elements, WATER and FAIRY. This is because of all the types present in the battle tower up until this point ( FIRE, GRASS, ELECTRIC, WATER, FAIRY), the only types not in either of the player team nor enemy team 2 is WATER and FAIRY.
The array of elements should be in the same order as the order of the element de�nition in Elements.py . You can loop over the Elements enumerator with for element in Element . So returning an array like [FAIRY, WATER] would be incorrect, but [WATER, FAIRY] would be correct.
[TASK - 1054 ONLY] A Balanced Tournament and Ordered Tower
A reminder that use of inbuilt lists, dictionaries, sets are banned, and using less suited data structures will result in loss of marks.For those in 1054, we have two short but sweet tasks just for you, both in tower.py! Sorting the tower
In the battle tower, an initial ordering is chosen, and then from there it is set in stone. But we want to reorder the tower easily at any time. In the BattleTower , implement the method sort_by_lives . What this should do, is when called, reorder the process in which battles are conducted based on how many lives each enemy team has remaining ascending - then this ordering is the new "initial order" which is followed from now on.
For example, suppose we have 4 teams, A B C and D, with lives 4, 3, 5, 2. We �rst played 3 games, beating teams A B and C, so next we will �ght team D, and the lives of each team is 3, 2, 4, 2. If at this point, we call sort_by_lives , then we order the teams by their remaining lives. This gives us D B A C or B D A C (we don't mind for equal lives what the ordering is). Now the next team we �ght will be team D again, with 2 lives. After that we'll �ght team B, then A, then C, then D again...Just sorting is too easy though! for this task, you must sort the enemy teams, without introducing any additional data structures! You can only use whatever structure you use in the tower task to store enemy teams
For those familiar, we are asking you to execute the algorithm with O(1) auxilliary space complexity (But don't worry if you don't know what that is, you just can't introduce a Stack/Queue/whatever object of size n - only a �xed number of variables)
A reminder that you also can't access the internals of whatever structure you selected. There are no complexity requirements on the running time of this program.
Balancing the tournament Another way that Monster Battles is played is in elimination brackets . These brackets can also be stated in post�x notation, where a + denotes two teams facing o�. For example, the quarter �nal draw of the latest Australian Open can be represented as Khachanov Korda + Tsitsipas Lehecka + + Rublev Djokovic + Shelton Paul + + + .
What we are interested in is whether a string like the one above representing an elimination bracket is balanced and legal. What this means is that:
- The string actually de�nes a valid tournament, and
- For any battle in the tournament, the two teams battling must have played the exact same amount of games so far.
Implement the method tournament_balanced , which returns a boolean determining whether the tournament string is balanced.
Submit your entire code assignment in the submission box below Please follow the instructions here: https://edstem.org/au/courses/12108/discussion/1462288