What is an efficient way to store and reference hundreds of values?

Question

In my game, I have many different types of units that are instantiated/destroyed with regularity. They have certain values, like MaxHP or Level or Defense, which need to be referenced at instantiation, and may vary based on certain factors. For example, MaxHP may be higher if Level increases, but not based on a strict formula, which varies by unit. So, for example:

• Soldier Level 1 Max HP: 5
• Soldier Level 2 Max HP: 6

• Soldier Level 3 Max HP: 8

• Mage Level 1 Max HP: 3

• Mage Level 2 Max HP: 4
• Mage Level 3 Max HP: 5

The class name would be easy to reference, and the level of the units would be stored elsewhere, and I'd need to know which trait I'm looking up to look it up in the first place. Therefore, what makes sense to me is to store these as key/value pairs. I can programmatically check something like (className + lvlString + traitName) as the key, so the key would end up being Mage2MaxHP and the value would be 4.

Usually my instincts in this regard are pretty bad since I never learned much about data structures. So, I'm wondering if there's a better way to achieve this and organize this amount of data. For example, it seems like this would be incredibly large for a dictionary. Perhaps it would be more manageable split into several dictionaries (one for MaxHP, one for Defense, etc.), but I still feel like I'm overlooking a data structure more suitable for this purpose. Any recommendations?

Answer 1

"Hundreds" really isn't much in terms of a modern CPU, a Dictionary adds a lot of complexity and ties you to one access pattern. Often it's best to start simple: with a List<T> and figure out what your access patterns will be. You can use LINQ against it to query by class name, hp, level or any combination thereof. Once you have it working, if you find that you need to boost performance for some queries, then, at that time go ahead and refactor it maybe using a Dictionary as an index.

But never underestimate the power of a modern compiler and a modern CPU to iterate over a contiguous block of memory blindingly fast beating many other data structures than might offer a better theoretical performance for very large values of N.

Answer 2

The following would approach your issue using both inheritance and Dictionaries in order to avoid having to class-name-strings etc.

public abstract class Unit
{
    // This approach would use one Dictionary per Trait
    protected abstract Dictionary<int, int> MaxHpByLevel { get; }

    public int Level { get; set; } = 1;

    public int MaxHp => this.MaxHpByLevel[this.Level];
}

public class Soldier : Unit
{
    protected override Dictionary<int, int> MaxHpByLevel => new Dictionary<int, int>
    {
        [1] = 5,
        [2] = 6,
        [3] = 8
    };
}

public class Mage : Unit
{
    protected override Dictionary<int, int> MaxHpByLevel => new Dictionary<int, int>
    {
        [1] = 3,
        [2] = 4,
        [3] = 5
    };
}

You would use it like that:

var soldier = new Soldier { Level = 2 };
Console.WriteLine(soldier.MaxHp); // 6

Just like you, I also think one could solve this issue in different ways.

What I like about this particular approach is that it is based on OOP-Principles and that it reduces redundant structural elements (e.g. avoids enums for trait-types etc.). You can access the properties of a unit over - well - Properties of a unit.

The Dictionaries used here would be rather small. However, I agree with the folks from the comments/answers when it comes to the size-restrictions. No matter what approach you choose, you will likely not bring your dictionaries any close to its limits.

Answer 3

I usually use code like below :

   public class Unit
    {
        public static Dictionary<string, Unit> units { get; set; } // string is unit name

        public string name { get; set; }
        public int level { get; set; }
        public Dictionary<string, int> attributes { get; set; }
    }

Answer 4

You might want to have the classes and attributes as enums, which I'd expect to come in handy in a lot of other places, too. Something like:

public enum Class
{
    Soldier,
    Mage,
    /*...*/
}

public enum Attribute
{
    Health,
    Magic,
    /*...*/
}

And then combine them to have a key for a dictionary that should be a bit more efficient and "useful" than just a concatenated string. Something like:

public struct AttributeKey : IEquatable<AttributeKey>
{
    public AttributeKey(Class @class, Attribute attribute, int level)
    {
        Class = @class;
        Attribute = attribute;
        Level = level;
    }

    public readonly Class Class;
    public readonly Attribute Attribute;
    public readonly int Level;

    public bool Equals(AttributeKey other)
    {
        return Class == other.Class && Attribute == other.Attribute && Level == other.Level;
    }
    public override bool Equals(object obj)
    {
        return obj is AttributeKey && Equals((AttributeKey)obj);
    }
    public override int GetHashCode()
    {
        unchecked
        {
            return (((Class.GetHashCode() * 397) ^ Attribute.GetHashCode()) * 397) ^ Level;
        }
    }
}

Most important for the use as a key in a dictionary is to be very deliberate with the Equals and especially the GetHashCode methods.

See for example Why is it important to override GetHashCode when Equals method is overridden? and MSDN for further information about that.

Answer 5

There is no particular reason why this is better than any other approach. However you could use a class with an Indexer that has an internal Dictionary with a Tuple key

Note : Ideally you would want to store and load this stuff from db, or a file, or maybe just generate it dynamically if there is not too much. However, depending on the nature of the game, this maybe a novel approach.

Demo here

---

Main

private static readonly CharLookup _lookup = new CharLookup();

private static void Main()
{
   _lookup[CharacterClass.Mage, CharacterTrait.SingingAbility, 2] = 123;
   _lookup[CharacterClass.Mage, CharacterTrait.SingingAbility, 3] = 234;
   _lookup[CharacterClass.Soilder, CharacterTrait.MaxBeers, 3] = 23423;

   Console.WriteLine("Mage,SingingAbility,2 = " + _lookup[CharacterClass.Mage, CharacterTrait.SingingAbility, 2]);
   Console.WriteLine("Soilder,MaxBeers,3 = " + _lookup[CharacterClass.Soilder, CharacterTrait.MaxBeers, 3]);
}

Enums

public enum CharacterClass
{
   Soilder,

   Mage,

   SmellyCoder
}

public enum CharacterTrait
{
   MaxHp,

   MaxBeers,

   SingingAbility
}

CharLookup

public class CharLookup
{
   private Dictionary<Tuple<CharacterClass, CharacterTrait, int>, int> myDict = new Dictionary<Tuple<CharacterClass, CharacterTrait, int>, int>();

   public int this[CharacterClass characterClass, CharacterTrait characterTrait, int level]
   {
      get => Check(characterClass, characterTrait, level);
      set => Add(characterClass, characterTrait, level, value);
   }

   public void Add(CharacterClass characterClass, CharacterTrait characterTrait, int level, int value)
   {
      var key = new Tuple<CharacterClass, CharacterTrait, int>(characterClass, characterTrait, level);

      if (myDict.ContainsKey(key))
         myDict[key] = value;
      else
         myDict.Add(key, value);
   }

   public int Check(CharacterClass characterClass, CharacterTrait characterTrait, int level)
   {
      var key = new Tuple<CharacterClass, CharacterTrait, int>(characterClass, characterTrait, level);

      if (myDict.TryGetValue(key, out var result))
         return result;

      throw new ArgumentOutOfRangeException("blah");
   }
}

Answer 6

This is still storing in a dictionary but includes simple enums and methods to store and retreive the data.

public enum UnitType
{
    Soldier,
    Mage
}

public enum StatType
{
    MaxHP,
    MaxMP,
    Attack,
    Defense
}

// Where the unit initialisation data is stored
public static class UnitData
{
    private static Dictionary<string, Dictionary<StatType, int>> Data = new Dictionary<UnitType, Dictionary<StatType, int>>();

    private static string GetKey(UnitType unitType, int level)
    {
        return $"{unitType}:{level}";
    }

    public static AddUnit(UnitType unitType, int level, int maxHP, int maxMP, int attack, int defense)
    {
        Data.Add(GetKey(unitType, level), 
            new Dictionary<StatType, int> 
            {
                { StatType.MaxHP, maxHP },
                { StatType.MaxMP, maxMP },
                { StatType.Attack, attack },
                { StatType.Defense, defense }
            });
    }

    public static int GetStat(UnitType unitType, int level, StatType statType)
    {
        return Data[GetKet(unitType, level][statType];
    }
}

// The data is not stored against the unit but referenced from UnitData
public class Unit
{
    public UnitType UnitType { get; private set; }
    public int Level { get; private set; }
    public Unit(UnitType unitType, int level)
    {
        UnitType = unitTypel
        Level = level;
    }
    public int GetStat(StatType statType)
    {
        return UnitData.GetStat(UnitType, Level, statType);
    }
}

// To initialise the data
public class StartClass
{
    public void InitialiseData()
    {
        UnitData.Add(UnitType.Soldier, 1, 5, 0, 1, 1);
        UnitData.Add(UnitType.Soldier, 2, 6, 0, 2, 2);
        UnitData.Add(UnitType.Soldier, 3, 8, 0, 3, 3);

        UnitData.Add(UnitType.Mage, 1, 3, 10, 1, 1);
        UnitData.Add(UnitType.Mage, 2, 4, 15, 2, 2);
        UnitData.Add(UnitType.Mage, 3, 5, 20, 3, 3);
    }
}

// Use of units
public class Level1
{
    public List<Unit> Units = new List<Unit>();
    public void InitialiseUnits()
    {
        Units.Add(new Unit(UnitType.Soldier, 1));
        Units.Add(new Unit(UnitType.Soldier, 1));
        Units.Add(new Unit(UnitType.Mage, 1));
        Units.Add(new Unit(UnitType.Mage, 1));
    }
    public void Something()
    {
        int maxHP = Units.First().GetStat(StatType.MaxHP);
        // etc
    }
}