Record Manipulation

Summary (Notes)

• A record or dictionary is a mapping between keys and values, e.g., mapping characters a count of their occurrences, names of employees to their salaries, or IDs of players to their scores.
• The keys and values are of arbitrary type in a record but they should be consistent per record, e.g., a dictionary that maps strings to integers.
• To create a record, you can use record initialization syntax:

{ <key1> : <value1>, <key2> : <value2>, ..., <keyn> : <valuen> }

• For example, here is a dictionary mapping names (strings) to ages (integers): d = { 'barry' : 15, 'ronda' : 11, 'andy' : 19, 'zac' 21 }.
• To access a particular value given a key, use indexing notation, providing the key, e.g., d['ronda'] evaluates to 11.
• To add an entry to an existing dictionary, use assignment where the left-hand side is the entry in the map, e.g., d['jane'] = 12.
• Only one key can be mapped to a value in a particular dictionary, so to update a key to point to a new value, we use the same syntax as adding an entry, e.g., d['ronda'] = 12.
• Frequently, we want to access the keys and values separately or together as a list. There are three methods to perform these operations:
  • d.keys() retrieves the keys of the dictionary in a list, e.g., ['barry', 'ronda', 'andy', 'zac']. Note that the order of the keys in the list is not guaranteed.
  • d.values() retrieves the values of the dictionary in a list, e.g., [15, 11, 19, 21].
  • d.items() retrieves both the keys and values of the dictionary as a list of pairs, e.g., [('barry', 15), ('ronda', 11), ('andy', 19), ('zac', 21)].

Loot Generator

Procedural content generation in the context of video games is the process of generating content such as levels, art, or other assets “on the fly” rather than up-front. For example, instead of designing a series of levels for a game, we may instead provide several level primitives and then write a series of rules as to how these primitives can be combined to form actual levels. Then we can write a series of procedures or methods that automatically combine primitives according to the rules to form complete levels.

Many video games have used procedural content generation to great effect. One of those games is the venerable Diablo series of which Diablo III released in 2012 is the latest iteration. Diablo is a Hack and Slash role-playing game that focuses on leveling up and getting loot for your character by killing monsters. The appeal of Diablo is that both the levels and loot are procedurally generated so that the replay value is huge. Many games have emulated Diablo’s procedural design, in particular, the action role-playing game Torchlight and the first-person shooter/role-playing mash-up Borderlands. However, the Diablo series is in a class of its own and remains the most celebrated of these sorts of games.

In this homework, we’ll be implementing the loot generation algorithm found in Diablo II. Since Diablo II has been around for over a decade, dedicated fans have put together exactly how the game procedural generates loot as detailed on the Diablo Wiki. For our purposes, the loot generation algorithm is interesting because it highlights both file I/O and how far we’ve come this semester. We are at the point where we can start understanding and simulating how real-world systems out there!

The algorithm and data files we use are simplified versions taken from the above article. However, the core ideas remain the same, so you can faith that after this assignment, you’ll understand how Diablo II procedural generates items!

The loot generation algorithm

Diablo II uses a collection of files in order to randomly generate loot. For this homework, we’ll be providing you two sets of these files to power your loot generator. All the files are comma-delimited text files, so you can open them up either in a text editor like Vim or a spreadsheet program such as Excel or OpenOffice. In the sections that follow, we’ll describe the contents of each of the files, but you should look at these text files yourselves in order to get a sense of the layout.

To generate a single piece of loot, our loot_generator program will go through the following steps:

• We randomly pick a monster to fight and beat.
• We look up the treasure class of that particular monster and using that treasure class, generate the base item that is dropped by the monster.
• We generate the base stats for the generated base item.
• We generate affixes (i.e., prefixes and suffixes) for the item and stat modifiers from those affixes.

Like the previous homework, the loot_generator program will repeatedly prompt the user to go through this process until they decide to quit.

Step 1: Picking the monster

The data file monstats.txt contains the list of possible monsters in the game. It has the following format:

Class,Type,Level,TreasureClass
<entries>

Within monstats.txt, the entries are all comma-separated lists of values. This is true of the other data files as well.

The class of the monster is its name. The type and level are irrelevant for our purposes, and the treasure class defines the class of items that the monster drops when it dies. In the next step, we’ll look up this treasure class in another file to determine the item the monster drops.

You should choose a random monster from this file to slay. Each monster has equal probability of being chosen.

Step 2: Looking up the treasure class

Once we’ve picked a monster and extracted its treasure class (TC), we next go to TreasureClassEx.txt to determine the base item that the monster drops. A base item in Diablo II is an armor or weapon type that we’ll build upon to generate a final item. For this lab, we will only consider armor pieces.

TreasureClassEx.txt has the following format:

Treasure Class,Item1,Item2,Item3
<entries>

Each treasure class entry in this file describes three possible drops that can occur for that TC. For example, here is one line of the TreasureClassEx.txt from the simple data set.

Act 5 (H) Equip B,armo60b,armo60b,Act 5 (H) Equip A

Act 5 (H) Equip B is a treasure class. It has two possible drops: armo60b (which appears twice) or Act 5 (H) Equip A. Because armo60b appears twice, it has 2/3rds of a chance of being picked. armo60b and Act 5 (H) Equip A are both TCs because they have entries in this file. Here is the entry for armo60b:

armo60b,Embossed Plate,Sun Spirit,Fury Visor

Here, armo60b has three drops. These three drops are base items (rather than TCs) because they do not have entries in the file.

To determine the drop that actually occurs from a monster, we go through the following process.

• We look up the monster’s TC in TreasureClassEx.txt.
• For that TC, we randomly choose one of three drops listed in the file.
• If the drop we choose is a TC, we look up that new TC in the file and randomly choose from one of its drops. We repeat this process until we finally arrive at a base item.
• The base item that we finally choose is the randomly generated drop from our monster!

Note that this process is inherently recursive in nature. Your implementation should reflect this fact!

Step 3: Computing base stats for a base item

Since we are not actually simulating any combat mechanics, computing the base stats for the base item we generated in the previous part simply means we generate a string that contains the base statistic for that base item. For armor pieces, the base statistic is defense and should be printed out in the following form:

Defense: <defense value>

The defense value is derived from the entry for the base item in armor.txt which has the following form.

name,minac,maxac
<entries>

This defense value for armor is simply a random integer in the range minac to maxac inclusive. You will need to generate such a random integer to create the base statistic string. You should use the randint function of the random module to do this.

Part 4: Generating affixes

Finally, we generate a prefix and suffix for our item. A prefix and suffix each have a 1/2 chance of being generated. So our item generator may make an item with both a prefix or suffix, one of a prefix or suffix, or neither a prefix nor a suffix.

Prefixes and suffixes exist in the MagicPrefix.txt and MagicSuffix.txt files respectively and have the following identical formats:

Name,mod1code,mod1min,mod1max

name is precisely the prefix and suffix that you will attach onto the base item’s name. mod1code is the additional statistic text that the affix will introduce to the base item. That statistic will have a single, random integer value in the range mod1min and mod2max inclusive.

Thus, the format of the final item name will be:

<prefix (if exists)> <base item name> <suffix (if exists)>

The format of the additional statistics from the prefix and suffix have the form:

<value> <statistic text>

Each additional statistic should be printed on a separate line with the prefix statistic coming before the suffix statistic. If a prefix or suffix is not generated, then you should not include an extra line for that prefix or suffix.

Format of the output

Each “round” of the loot generator has you squaring off against a randomly-chosen monster, killing it, and then displaying its loot. The format of your output for each round should look as follows:

Fighting <monster name> (Level <level> <type>)...
You have slain <monster name>
<monster name> dropped:

<complete item name>
<base item statistic>
<additional affix statistics>

The prompt has the following format:

Fight again? <user input>

To implement this prompt, use the raw_input() built-in function which prompts the user to enter a line of text; that string is the value returned by the function. Your code should be “generous” in that it is case-insensitive (i.e., “y”, “n”, “Y”, and “N” are all valid responses) and re-prompts the user if they do not enter a valid value. The re-prompt message is the same as the original prompt message:

Fight again [y/n]? <user input>

Data sets

The set of files armor.txt, MagicPrefix.txt, MagicSuffix.txt, monstats.txt, TreasureClassEx.txt, and weapons.txt comprise a single data set for your program. You should assume that all of these files exist in the same directory as your loot_generator program.

We provide two data sets for testing purposes. The small dataset consists of a single monster, 6 treasure classes, 9 armor pieces, and 5 affixes. A common technique is to test your program on a toy data set. This toy data set is small enough for you to easily reason about how your program deals with the data. You should start out with this data set and make sure that your program works with it.

The large dataset includes 49 monsters, 68 treasure classes, 202 armor pieces, and 758 affixes. Once you have your program working on the small data set, you can move onto the large data set to further test your code.

One testing technique you may want to try is to temporarily remove the prompt for your code when you use the large dataset, so that the program rapidly generates new items. If your program can do this for an extended period of time without throwing an exception, then you can have confidence that your program works correctly.

• datasets.zip

This zip file contains two directories, one for each of the small and large datasets. You should write your program so that it is in the same directory as the directory that contains these two dataset directories. At the start of the program, you should prompt the user for which dataset to load. They should specify the (relative path of) the directory containing the dataset files to load.

Example of item generation

To tie everything together, here is an example of generating an item from the small data set. While you read through this example, you should follow along with the data files in small_data.zip.

• Pick a random monster: there is only one monster in monstats.txt, hell bovine, so we pick it.
• Get the TC for that monster: we look back in monstats.txt and find that the TC for the hell bovine is Cow (H) which we know is a treasure class because it has an entry in TreasureClassEx.txt.
• Generate the base item: going to TreasureClassEx.txt, we look at the entry for Cow (H) and randomly pick one of the three items on that line. Let’s say we end up picking armo3. This is a treasure class, so we look at the entry for armo3 and randomly pick again. Let’s say we end up picking Leather Armor. This is not a treasure class as it does not have an entry in TreasureClassEx.txt so it is the base item that we generate.
• Generate base stats: We scan armor.txt for a Leather Armor entry. As per the instructions, we randomly choose a number between the values minac and maxac which we find is 14 and 17 for Leather Armor. Say we choose the value 15, so the base statistic for our item is "Defense: 15".
• Generate affixes and affix stats: finally we need to generate the affixes for our item. Let’s say that we end up only generating a suffix for our item. We go to MagicSuffix.txt and randomly choose one of the entries, for example, say we pick of the Titan that has entries "Strength", "16", and "20" for mod1code, mod1min, and mod1max respectively. Let’s say that we pick 18 as our statistic value, a random number between 16 and 20 inclusive. Then our affix statistic is the string "18 Strength".

Putting this together, our output for the round should look like:

Fighting Hell Bovine (Level 90 Cow)...
You have slain Hell Bovine!
Hell bovine dropped:

Leather Armor of the Titan
Defense: 15
18 Strength

Sample Output

Here is a example run of the loot_generator function against the small data set. Like always, you should be able to reproduce the format of the output exactly.

>>> loot_generator()
This program simulates the random item generator
from the game Diablo II.  Happy hunting!

Path to data directory: doesnotexist
Please enter a valid path to the data directory: soln.py
Please enter a valid path to the data directory: small

Fighting Hell Bovine (Level 90 Cow)...
You have slain Hell Bovine!
Hell Bovine dropped:

Glowing Embossed Plate of Regrowth
Defense: 282
2 Light Radius
5 Regeneration

Fight again? y

Fighting Hell Bovine (Level 90 Cow)...
You have slain Hell Bovine!
Hell Bovine dropped:

Glorious Buckler of the Leech
Defense: 5
44 Enhanced Defense %
5 Lifesteal

Fight again? y

Fighting Hell Bovine (Level 90 Cow)...
You have slain Hell Bovine!
Hell Bovine dropped:

Dragon's Diadem
Defense: 52
38 Mana

Fight again? y

Fighting Hell Bovine (Level 90 Cow)...
You have slain Hell Bovine!
Hell Bovine dropped:

Glowing Mage Plate of the Tiger
Defense: 249
2 Light Radius
23 Health

Fight again? y

Fighting Hell Bovine (Level 90 Cow)...
You have slain Hell Bovine!
Hell Bovine dropped:

Diadem
Defense: 52

Fight again? nope
Fight again [y/n]? n

Design

This is our largest program yet, so decomposition and good design will be essential in order to manage its complexity. The outline of the algorithm at the top of the write-up the suggests the top-level methods that we’ll need for our program. You need at least one function for each top-level bullet in the algorithm outline. Some of the bullets necessarily require multiple methods, e.g., a separate method to generate armor versus weapon base statistics, but it will be up to you to make that determination. A good rule of thumb is that any task that requires processing a file should be factored out to its own function.

In addition to these required functions, you should also include at least three other helper functions in your program that do interesting work.

A good approach to tackling this program is to decide up front what top-level functions you need and then writing each independently as if they were separate questions for the homework. For example, you will likely need a method to randomly pick a monster from the monstats.txt file. You should write and test this method independently from the rest. Once all of these methods are written, you can then put them all together in main.