Implementation of a string-based loot table

Question

I wanted to create a loot table mechanic for any future game projects, and came up with what I am about to show you guys. I was wondering if someone could give it a glance and see if there could be any errors, or if it could be improved in any way.

using System;
using System.Collections.Generic;

namespace NovaEngineFramework.Framework.Probability
{
    /// <summary>
    /// A String-based loot table.
    /// The table is based upon a pie-chart design. In other words,
    /// each item is added with a desired rarity; that rarity counts
    /// towards a total maximum of 100. Example:
    /// Item1 = 10
    /// Item2 = 40
    /// Item3 = 50
    /// Total = 100.
    /// Item1 is the rarest item in the table, while Item3
    /// is the most common.
    /// </summary>
    public class StringBasedLootTable
    {
        private readonly List<string> _loot;
        private readonly Dictionary<string , int> _cachedItems;
        private int _remainingStorage = 100;
        private readonly Random _rngInstance;

        public StringBasedLootTable()
        {
            _cachedItems = new Dictionary<string , int>();
            _loot = new List<string>();
            _rngInstance = new Random();
        }

        /// <summary>
        /// Adds an item to the Loot Table with it's own specified rarity.
        /// An error may be thrown if the storage capacity(maximum 100) is
        /// exceeded by a previously added item.
        /// </summary>
        /// <param name="rarity">How rare the item will be.</param>
        /// <param name="itemName">The string name representation of the item to be added.</param>
        /// <exception cref="InvalidOperationException">Thrown if the capacity has already been exceeded, or is about to be exceeded.</exception>
        public void Store( int rarity , string itemName )
        {
            int test = ( _remainingStorage - rarity );
            if( test < 0 )
            {
                throw new Exception( "Storage Capacity Was full" );
            }
            _remainingStorage = _remainingStorage - rarity;
            _cachedItems.Add( itemName , rarity );
        }

        /// <summary>
        /// Shows the remaining storage of this loot table.
        /// </summary>
        /// <returns></returns>
        public int CheckRemainingStorage()
        {
            return _remainingStorage;
        }
        /// <summary>
        /// Rebuilds the loot table. An error will be thrown if
        /// all of the available space has not been properly utilized.
        /// This function should only be called once all the items have
        /// been added to the table.
        /// </summary>
        /// <exception cref="InvalidOperationException">Thrown if the capacity is not full.</exception>
        public void Rebuild()
        {
            if( _remainingStorage > 0 )
            {
                throw new Exception( "The Capacity was not completely full." );
            }
            _loot.Clear();
            foreach( KeyValuePair<string , int> pair in _cachedItems )
            {
                for( int i = 0; i < pair.Value; i++ )
                {
                    _loot.Add( pair.Key );
                }
            }
        }

        /// <summary>
        /// Finds a random item(string) within the loot table.
        /// </summary>
        /// <returns></returns>
        public string GetRandomItem()
        {
            return _loot[ _rngInstance.Next( _loot.Count ) ];
        }
    }
}

And here is a brief implementation:

StringBasedLootTable swordTable = new StringBasedLootTable();
swordTable.Store( 40 , "Rusty Sword" );
swordTable.Store( 20 , "Steel Sword" );
swordTable.Store( 10 , "Titanium Sword" );
swordTable.Store( 30 , "Iron Sword" );
swordTable.Rebuild();
Console.WriteLine( swordTable.GetRandomItem() );

And the general concept of how it works:

It is based upon a pie-graph, in a way. Each item you add takes up a slice of the pie, and all the item probabilities must add up to exactly 100. A visual rendition would likely facillitate better understanding, so I went ahead and made this:

As you can see, the most probable item for one to recieve from the above implementation is a "rusty sword", being that it has the largest section of the pie graph. The least common item would be a Titanium sword, etc.

This post is not meant to fuel an argument about the use of var. Please do not offer it as an example of something that could be used towards fixing the code. The use of var is based upon purely personal, arbitrary taste; I have no intentions of using it.

Answer 1

If you're going to build a game on this stuff, you better start coding object oriented. Good OO coding naturally manages complexity. Without coherent classes, proper encapsulation, etc. adding game complexity will turn your code base to mush.

public class Loot {
    public string Name {get; protected set;}
    public int Rarity { get; protected set;};

    public Loot (string theName, int theRarity) {
        Name = theName ?? string.Empty;
        Rarity = theRarity;
    }

    public override string ToString() {
        return string.Format("{0} : {1}", Name, Rarity);
    }

    // if your loot table can have only one of each kind of loot
    // then perhaps override Equals (and GetHashCode)
    // The fact that your Dictionary uses the name as the key 
    // tells me this is the case.

    public override bool Equals(object other){
        if(other == null) return false;

        Loot theOther = other as Loot;
        if(theOther == null) return false;

        return this.Name == theOther.Name;
    }
}

---

StringBasedLootTable

Strongly typed Dictionary List

private readonly List<Loot> _cachedItems;

Store() has a bug - We don't want duplicates

public void Store( Loot theLoot ) {
   if(! _cachedItems.Contains( theLoot )  // made possible by Equals() override above.
        _cachedItems.Add(theLoot);
}

Implement an Equals(), could be handy

public bool Equals (Loot left, Loot right) {
    // null is never equal to null
    if (left == null || right == null)
        return false;

    return left.Equals(right);  // brought to you by: Loot.Equals() override!
}

Encapsulate the "remainingStorage"

protected int MaxStorage {get { return 100; }} // yeah, maybe a constant instead.
protected int CurrentStorage {
    get { return _cachedItems.Sum( x => x.Rarity ); }
}

public int RemainingStorage {get {return MaxStorage - CurrentStorage; } }

public bool CanStore(Loot thisLoot) {
    return thisLoot.Rarity + CurrentStorage <= MaxStorage;

       // duh, radarbob. Could be simpler still. Good ol' OO.
    return thisLoot.Rarity <= RemainingStorage;
}

---

---

• I don't understand why there is both _loot and _cachedItems. In any case I expect they are not both needed.
• CheckRemainingStorage() - delete this.
• If you must have Rebuild(), how in the world is the client code supposed to know when and why to call it? The table should be re-building itself when necessary.
• I like that the Dictionary List is encapsulated, rather than StringBasedLootTable inheriting from List<Loot>. This controls exposure of all the list public methods and allows you to write methods in terms of a loot table - thus the class has the "look and feel" (API) of a "loot table".
• Good OO code tends to have short(er) methods. Good OO coding manages complexity. The CanStore(), Equals(), and CurrentStorage implementations demonstrate this.

---

Answer 2

Use var for definitions where the right hand side of the statement makes the type obvious. You should also use var for loop indexers.

e.g.

int test = ( _remainingStorage - rarity );

Should be

var test = ( _remainingStorage - rarity );

Additionally, you really don't need brackets there. They serve no purpose other than to make the code harder to read.

Another example:

foreach( KeyValuePair<string , int> pair in _cachedItems )
        {
            for( int i = 0; i < pair.Value; i++ )
            {
                _loot.Add( pair.Key );
            }
        }

I also really don't like the naming of "pair" here. They're not pairs, they're cachedItems, so call them that!

foreach( var cachedItem in _cachedItems )
        {
            for( var i = 0; i < cachedItem.Value; i++ )
            {
                _loot.Add( cachedItem.Key );
            }
        }

As for CheckRemainingStorage() that's really just a getter method disguised by another name. Make it a read-only property instead.

public int RemainingStorage {get; private set;}

And then retarget your use of _remainingStorage to point to RemainingStorage.

_remainingStorage is hardcoded to 100. This is an odd choice, because it specifically prevents you from having more than 100 items in the table and a minimum probability step no smaller than 1/100. Instead, consider double arithmetic, where your probabilities are stored between 0 and 1. This way you can have an incredibly large number of possible items and smaller probability steps.

If you are to remain to the hard-coded 100, consider assigning that value to a well-named const such as "MaximumStorage" for reuse.

Lastly, I see no way to remove an item from the loot table, which seems like an oversight to me.

Answer 3

Micro

Don't Repeat Yourself (DRY)
The overloaded constructors should chain each other instead of duplicating the code - if you need to make changes, they currently need to be made in two places.

public LootTable() : this (new Random()) 
{
}
public LootTable( Random random )
{
    _rngInstance = random;
    _cachedLoot = new Dictionary<string , int>();
    _lootTable = new List<string>();
}

Rebuild Required
Why throw an exception if a rebuild in required?. Why not perform the rebuild? (see below)

Design
What is the intent behind this table? (There is no background given and we have to try and induce usage from the code)

If you are building a loot table for an encounter and there are fixed percentages for the items which the player might gain then there seems to be a lot of extra moving parts.

Are you really likely to change the table once created. If not, then Delete and ClearAll (and to a degree Add) seem superfluous. We could create the table from a config (in a game, I would push for the loot tables to be generated from data files not constructed in code) and consider them to be immutable at that point. If we have multiple encounters, we create multiple tables rather than changing the existing table.

If the table needs to be mutable then there should be no need to explicitly Build. The only point at which the build becomes necessary is when getting an item. If a build is necessary at that point, perform it and then return the generated item.

The _cachedLoot and _lootTable combo seems like over-engineering. All we need in order to generate the loot correctly is a list of items (call each one a LootConfig) containing the name and the percentage chance. A simple loop down the list will allow us to generate the correct item. Looking at the code this looks like it should be slower than the index into _lootTable but for 10,000 items the times were comparable. As a rule of thumb, unless one knows that performance will be an issue, I would go with the simpler implementation first and then, if performance is an issue, optimize.

Other
Instead of passing in a Random, I would pass in an interface that provides the next value. We can have a default version that uses Random, but for unit tests we can pass in a fixed set of values. I would push this for any place where you are using random numbers.

Proposed Implementation
There are a lot of pieces in the code below (and I did comment on over-engineering above) but each solves a specific problem

IPercentGenerator, PercentGenerator
Allows us to unit test more easily as we can select the values rolled.

// generates values 1-100
public interface IPercentGenerator {
    int Next();
}
public class PercentGenerator : IPercentGenerator {
    private const int MaxValue = 100;
    private readonly Random _random;
    public PercentGenerator() {
        _random = new Random();
    }
    public int Next() {
        return _random.Next(MaxValue) + 1;
    }
}

ILootTableConfig, LootTableConfig
If we are going to use this as part of a generic game system we will want to load data from files/stores and not have to create tables in code. (Say we want to change the pcts for the items, changing the text in a config file and re-running is a lot simpler and less error prone than changing the code, rebuilding and re-running) The interface allows us to source the loot items from anywhere.

public interface ILootTableConfig {
    IEnumerable<LootItemConfig> GetLootItems();
}
public class LootTableConfig : ILootTableConfig {
    public IEnumerable<LootItemConfig> GetLootItems(){
        yield return new LootItemConfig("Rusty Sword", 40);
        yield return new LootItemConfig("Steel Sword", 20);
        yield return new LootItemConfig("Titanium Sword", 10);
        yield return new LootItemConfig("Iron Sword", 30);
    }
}
public class LootItemConfig {
    public LootItemConfig(string name, int percentChance) {
        Name = name;
        PercentChance = percentChance;
    }
    public string Name { get; private set; }
    public int PercentChance { get; private set; }
}

LootTable
The internal constructor allows us to inject the IPercentGenerator for unit testing without impacting the public API.

In terms of effectiveness, when testing I got the following for 10,000 items.

• Rusty Sword : 3963
• Steel Sword : 2025
• Iron Sword : 3003
• Titanium Sword : 1009

public class LootTable {

    private const string ErrMsgPercentageChancesDoNotTotal100 = "Percentage chances do not total 100";
    private readonly IPercentGenerator _percentGenerator;
    private readonly List<LootItemConfig> _lootItems;

    public LootTable(ILootTableConfig lootTableConfig) 
        : this(lootTableConfig, new PercentGenerator()){}

    internal LootTable(ILootTableConfig lootTableConfig, IPercentGenerator percentGenerator) {
        _percentGenerator = percentGenerator;
        _lootItems = lootTableConfig.GetLootItems().ToList();
        if (_lootItems.Select(l => l.PercentChance).Sum() != 100) {
            throw new ArgumentException(ErrMsgPercentageChancesDoNotTotal100);
        }
    }

    public string GetLootItem() {
        var pct = _percentGenerator.Next();
        var itemName = string.Empty;
        var cummulativePct = 0;
        foreach (var lootItem in _lootItems) {
            cummulativePct += lootItem.PercentChance;
            if (pct <= cummulativePct) {
                itemName = lootItem.Name;
                break;
            }
        }
        return itemName;
    }
}

Answer 4

I think your approach is wrong - or at least sub optimal.

The consumer shouldn't need to explicitly rebuild the table. If that's what you want to do, then pair a LootTableBuilder and a LootTable class. The builder can have the Add, Update and Build methods and the LootTable can just have the Get.

I don't think you need to do that, I think it's fairly straightforward to keep a dictionary of items with thier bounds. It's a bit wierd that if I call .Store(1000, "Some weapon") then Build you duplicate the string 1000 times in a list.

Consider my alternative:

public class StringBasedLootTable
{
    private class Bounds
    {
        private readonly int _lower;
        private readonly int _upper;
        private readonly int _difference;

        public int Difference { get { return _difference; } }

        public Bounds(int lower, int upper)
        {
            _lower = lower;
            _upper = upper;
            _difference = upper - lower;
        }

        public bool Encloses(int value)
        {
            return _lower <= value && value < _upper;
        }
    }

    private IDictionary<string, Bounds> _loot; 
    private int _currentTotal;
    private Random _random;

    public StringBasedLootTable()
    {
        _loot = new Dictionary<string, Bounds>();
        _random = new Random();
    }

    public void AddItem(int probability, string itemName)
    {
        if (_loot.ContainsKey(itemName))
        {
            // todo - add new exception type and message.
            throw new Exception("");
        }
        var lowerBound = _currentTotal;
        _currentTotal += probability;
        _loot[itemName] = new Bounds(lowerBound, _currentTotal);
    }

    public string GetRandomItem()
    {
        var target = _random.Next(_currentTotal);
        return _loot.Single(kvp => kvp.Value.Encloses(target)).Key;
    }

    public void UpdateItem(int newProbability, string item)
    {
        if (!_loot.ContainsKey(item))
        {
            // Exception or nothing
            return;
        }
        var probabilities = new Dictionary<string, int>();
        foreach (var kvp in _loot)
        {
            probabilities[kvp.Key] = kvp.Key == item ? newProbability : kvp.Value.Difference;
        }
        RebuildFromProbabilityTable(probabilities);
    }

    private void RebuildFromProbabilityTable(Dictionary<string, int> probabilities)
    {
        _currentTotal = 0;
        _loot = new Dictionary<string, Bounds>();
        foreach (var item in probabilities)
        {
            AddItem(item.Value, item.Key);
        }
    }
}

Each entry in the loot table just tracks the range of values that should return it. Usage is basically the same:

StringBasedLootTable swordTable = new StringBasedLootTable();
swordTable.AddItem( 40 , "Rusty Sword" );
swordTable.AddItem( 20 , "Steel Sword" );
swordTable.AddItem( 10 , "Titanium Sword" );
swordTable.AddItem( 30 , "Iron Sword" );
Console.WriteLine(swordTable.GetRandomItem());

There is also the possibility of creating a constructor that takes a IDictionary<string, int> of item and probability for bulk population.

You'll note that I like to use var and also don't want to get into a holy war about it.

Answer 5

Here is an updated version of my Loot Table. I dropped the "all probabilities must add up to 100" and instead left it open for the programmers own implementation.

using System;
using System.Collections.Generic;
using System.Linq;

namespace NovaEngineFramework.Framework.Probability
{
    public class LootTable
    {
        private readonly List<string> _lootTable;
        private readonly Dictionary<string , uint> _cachedLoot;
        private readonly Random _rngInstance;
        private bool _isRebuildRequired;

        public LootTable()
        {
            _rngInstance = new Random();
            _cachedLoot = new Dictionary<string , uint>();
            _lootTable = new List<string>();
        }

        public LootTable( Random random )
        {
            this._rngInstance = random;
            _cachedLoot = new Dictionary<string , uint>();
            _lootTable = new List<string>();
        }

        public void AddLoot( uint probability , string name )
        {
            if( !_cachedLoot.ContainsKey( name ) )
            {
                this._cachedLoot.Add( name , probability );
                _isRebuildRequired = true;
            }
            else
            {
                throw new Exception( "Item: " + name + " Already Exists!" );
            }

        }

        public void DeleteLoot( string name )
        {
            if( _cachedLoot.ContainsKey( name ) )
            {
                this._cachedLoot.Remove( name );
                _isRebuildRequired = true;
            }
            else
            {
                throw new Exception( "Item: " + name + " Did not exist!" );
            }
        }

        public double CalculateProbability( string name )
        {
            if( _cachedLoot.ContainsKey( name ) )
            {
                double total = _cachedLoot.Values.Sum( n => ( int )n );
                double percent = _cachedLoot[ name ] / total;
                return Math.Round( percent * 100 , 2 );
            }
            throw new Exception( "Item: " + name + " Does not exist." );
        }

        public uint CheckRarity( string name )
        {
            if( _cachedLoot.ContainsKey( name ) )
            {
                return _cachedLoot[ name ];
            }
            throw new Exception( "Item: " + name + " Does not exist." );
        }

        public List<string> CheckLoot()
        {
            return this._cachedLoot.Keys.ToList();
        }

        public void EditLoot( string name , uint newProbability )
        {
            if( _cachedLoot.ContainsKey( name ) )
            {
                this._cachedLoot[ name ] = newProbability;
                _isRebuildRequired = true;
            }
            else
            {
                throw new Exception( "Item: " + name + " Does not exist." );
            }
        }

        public void ClearAllLoot()
        {
            this._cachedLoot.Clear();
            this._isRebuildRequired = true;
        }

        private void Build()
        {
            _lootTable.Clear();
            foreach( KeyValuePair<string , uint> pair in _cachedLoot )
            {
                for( int i = 0; i < pair.Value; i++ )
                {
                    _lootTable.Add( pair.Key );
                }
            }
            _isRebuildRequired = false;
        }

        public string NextRandomItem()
        {
            if( !_isRebuildRequired )
            {
                return _lootTable[ _rngInstance.Next( _lootTable.Count ) ];
            }
            this.Build(); // A rebuild is needed, let's go ahead and take care of it!
            return _lootTable[ _rngInstance.Next( _lootTable.Count ) ];
        }
    }
}

Loot can also now be edited freely. Manual rebuilding now no longer exists, because the method "NextRandomItem()" will automatically take care of it for you. I am also now using uints(which surprisingly no one suggested, even though it was a major bug with my first example).

Here is a simple example:

LootTable swordTable = new LootTable();
            swordTable.AddLoot( 40 , "Rusty Sword" );
            swordTable.AddLoot( 20 , "Steel Sword" );
            swordTable.AddLoot( 10 , "Titanium Sword" );
            swordTable.AddLoot( 30 , "Iron Sword" );
            Console.WriteLine( swordTable.NextRandomItem() );
            // Now for some deletion!
            swordTable.DeleteLoot( "Rusty Sword" ); // Removes Rusty Sword from the loot table.
            swordTable.EditLoot( "Steel Sword" , 10 ); // Change rarity.
            // Build no longer needs to be called. NextRandomItem will do it automatically for you
            // if it is needed!
            Console.WriteLine( swordTable.NextRandomItem() );

Edit/Update:

The method NextRandomItem now calls build if the loot table is currently within an invalidated state, ergo, the programmer no longer needs to worry about building/rebuilding.

And here is a better example along with a new pie chart.

            LootTable swordTable = new LootTable();
            swordTable.AddLoot( 1 , "Sword_Legendary_SwordOfIllimitableDemise" );
            swordTable.AddLoot( 200 , "Sword_Common_SteelGreatSword" );
            swordTable.AddLoot( 50 , "Sword_Rare_MagicImbuedLongBlade" );
            swordTable.AddLoot( 15 , "Sword_Epic_Hopesfire" );
            swordTable.AddLoot( 400 , "Sword_Trash_RustySword" );
            Console.WriteLine( swordTable.NextRandomItem() );

Here is a visualization:

And the interactive chart itself: Weapon Chart Interactive Link

The item probabilites, given the rarities listed, are as follows:

Sword_Legendary_SwordOfIllimitableDemise = 1(0.2%)
Sword_Common_SteelGreatSword = 200(30.0%)
Sword_Rare_MagicImbuedLongBlade = 50(7.5%)
Sword_Epic_Hopesfire = 15(2.3%)
Sword_Trash_RustySword = 400(60.1%)

I also added a new method to the class which calculates the above probabilites. It can be used like this:

swordTable.CalculateProbability( "Sword_Trash_RustySword");
output = 60.06%