Dictionary Ordered by Insertion Order?

I am building a game that takes in different types of “defends” for entities. I would want these defends ordered by insertion so when the entity is attacked it drains the first defend, then the second, etc.

In order to achieve this, I have a Dictionary that uses the type of defend as a key and an int as the value. Everything works well but upon research, it seems that Dictionaries do not return an order based on insertion. I have tried testing this and the Dictionary always prints correctly (ordered by insertion), so I am confused as to if this is an issue that arises when the game is built on different systems or perhaps if Unity handles dictionaries differently?

Thanks for the help.

Dictionary’s are a .net implementation of what is called a “HashMap”, “Map”, “Hash Table”, or any number of other names. Basically the key is hashed and modulo’d around some range to generate an index, and the value is placed into that index (well a linked-list at that index, to avoid collisions).

Hashing is inherently unsorted.

Things could accidentally end up sorted if your keys just so happen to hash in an ordered way. Like the has of an int is itself, if your key is all ints, they will end up inserting in order. Or say you used strings that happen to hash in order… like a 1-letter string “A”, “B”, “C” will hash in order as well just because of how the hash algorithm works. It’s all incidental though… the design of hash tables does not guarantee this, it can just happen accidentally.

There is a SortedDictionary:

But it doesn’t sort on insertion, it sorts on the key.

Is there a reason you need this in a dictionary? How are you looking things up in the dictionary by key? Where did you get the key to look it up? Why can’t you use a List/Stack/Queue (which is sorted by insertion).

I don’t know what your key or this int value represent. Maybe if you showed us what you’re attempting to do we could help more.

1 Like

Ok thanks for the info, I will definitely have to find another solution to how I have it set up!

An entity (player, enemy, etc.) casts skills that have different elemental types, these skills interact with each other differently depending on the type. Defensive skills are cast and (currently) added to the dictionary with the Key being the Elemental type and the Value being the amount of defense, this way additional casts of the same element for defense simply add to the value and new elemental types of defense are “stacked” below.

When an entity attacks another it is supposed to cycle through the “defensive stack” that the other entity has. The attack also has its own elemental type and is applied to each stack in order until either the defensive stacks are depleted or the attack amount is depleted. The main reason I chose a Dictionary is it allows to easily call the Elemental type of the defensive stack and update its Value accordingly. If you have a better idea of implementing a way for a “defensive stack” I am all ears, thanks for the help and below is the code for the Combat Handler as well.

    static readonly Dictionary <Element, Element[]> doubleDamage = new Dictionary<Element, Element[]>
    {
        {Element.Earth, new Element[]{Element.Fire, Element.Energy}}, //EARTH 2x
        {Element.Water, new Element[]{Element.Earth, Element.Fire, Element.Death}}, //WATER 2x
        {Element.Air, new Element[]{Element.Earth, Element.Water, Element.Fire}}, //AIR 2x
        {Element.Fire, new Element[]{Element.Life, Element.Death}}, //FIRE 2x
        {Element.Life, new Element[]{Element.Physical}}, //LIFE 2x
        {Element.Death, new Element[]{Element.Physical, Element.Air, Element.Life}}, //DEATH 2x
        {Element.Energy, new Element[]{Element.Water, Element.Air, Element.Death}} //ENERGY 2x
      
    };
    static readonly Dictionary <Element, Element[]> halfDamage = new Dictionary<Element, Element[]>
    {
        {Element.Physical, new Element[]{Element.Life, Element.Death}}, //PHYSICAL 0.5x
        {Element.Earth, new Element[]{Element.Water, Element.Air}}, //EARTH 0.5x
        {Element.Water, new Element[]{Element.Air, Element.Energy}}, //WATER 0.5x
        {Element.Air, new Element[]{Element.Death, Element.Energy}}, //AIR 0.5x
        {Element.Fire, new Element[]{Element.Earth, Element.Water, Element.Air}}, //FIRE 0.5x
        {Element.Life, new Element[]{Element.Fire, Element.Death}}, //LIFE 0.5x
        {Element.Death, new Element[]{Element.Water, Element.Fire, Element.Energy}}, //DEATH 0.5x
        {Element.Energy, new Element[]{Element.Earth, Element.Energy}} //ENERGY 0.5x
    };
  
    public enum Element
    {
        Physical, Earth, Water, Air, Fire,
        Life, Death, Energy
    }
  
    public static void CalculateDamage(CSkill attackSkill, CEntity targetEntity, float criticalChance)
    {
        int attackDamage = attackSkill.damage;
        float damageMultiplier = 1f;
        bool criticalHit = false;
        List<Element> depletedStacks = new List<Element>();
      
        //CRITICAL CHANCE
        if (RNG.Roll100F() < criticalChance) {criticalHit = true;} //CRITICAL HIT
        //TODO: Indicate a critical strike has taken place
      
        //CYCLE THROUGH ALL DEFENSE STACKS OF THE PLAYER
        foreach (KeyValuePair<Element, int> stack in targetEntity.defenseStack)
        {
            if (attackDamage == 0) {return;}
          
            //CRITICAL HIT DAMAGE (RESET DMG MULTIPLIER)
            damageMultiplier = criticalHit ? 1.5f : 1f;
            //UPDATE THE DAMAGE MULTIPLIER
            damageMultiplier += ElementInteraction(attackSkill.skillElement, stack.Key);
            //APPLY THE CURRENT DAMAGE TO THE CURRENT DEFENSE STACK
            DefenseStackFormula(damageMultiplier, attackDamage, stack.Value, stack.Key);
        }
      
        //CRITICAL HIT DAMAGE (RESET DMG MULTIPLIER)
        damageMultiplier = criticalHit ? 1.5f : 1f;
        damageMultiplier += ElementInteraction(attackSkill.skillElement, targetEntity.element);
        //DAMAGE TARGET ENEMY HEALTH
        attackDamage = Mathf.RoundToInt(attackDamage * damageMultiplier);
        targetEntity.DamageEntityCombat(attackDamage, depletedStacks);
      
        void DefenseStackFormula(float damageModifier, int attack, int defense, Element defenseElement)
        {
            //MODIFIER DEFENSE ACCORDING TO ELEMENT INTERACTION
            defense = Mathf.RoundToInt(defense/damageModifier);
          
            if (attack - defense >= 0)
            {
                attackDamage = (attack - defense); //Update remaining attack value
                targetEntity.defenseStack[defenseElement] = 0; //Defense is depleted
                depletedStacks.Add(defenseElement);
            }
            else
            {
                attackDamage = 0; //Attack is depleted
                targetEntity.defenseStack[defenseElement] -= attack; //Update remaining defense value
            }
        }
    }
  
    public static float ElementInteraction(Element attackingElement, Element defendingElement)
    {
        float multiplier = 0;
      
        if (doubleDamage[attackingElement].Contains(defendingElement)) {multiplier = 1f;} //Damage increased by 100%
        else if (halfDamage[attackingElement].Contains(defendingElement)) {multiplier = -0.5f;} //Damage reduced by 50%
      
        return multiplier;
    }

If you need ordering, use a list.

Unless your list is super long, the performance cost of iterating through every item to find the one you want isn’t going to be huge.

If you really need both ordered and random access, then you can create your own collection. Use a list to store the data. Then use a dictionary to store the key and the data index. Wrap the while thing up in a single collection. There are a whole bunch of edge cases for this set up though, I wouldn’t reccomend it.

I’ll bring up OrderedDictionary, only because it does exactly what you are describing. However, there may very well be better approaches to your game mechanics.

I didn’t read your code too carefully, but it looks to me as if your defense “stacks” probably don’t do what you expect. If I were to interpret a bit, I think you expect the defense stacks to reduce the incoming damage, but I don’t think they will do that when the attack is large enough to deplete all the defense.

1 Like