Search Unity

Best approach to polimorphic lists?

Discussion in 'Scripting' started by calpolican, Nov 21, 2019.

  1. calpolican

    calpolican

    Joined:
    Feb 2, 2015
    Posts:
    204
    I'm wondering what's the best way to handle this design issue
    Imagine this scenario:
    I have a class MyObject. All the objects of the inventory in my game are of this type.
    Now, there are many clases of objects, say MyWeapon, MyArmor, etc., that derive from that base class (MyObject).
    Now, when I handle the character's inventory, I have a list for every inherited type of object: one for the weapons, one for the armors, etc. The purpose of having all in different lists, is that if I need to evaluate what's the best armor, I just look into that list and that's it, I don't have to filter the class from the main list every time. This is useful for when I pick an armor at random, I can order the armors by property, see if a gun meets certain criteria, etc.
    But... I also need to do stuff to every object. Things that will afect my inventory as a whole. Like I may need for example to populate the trade balance, or take into account the overall weight, etc. For this I have a super list of type MyObject.
    Now, having all of this lists plus a superlist gets tedious, because if I want to add an item, I have to find the proper list where I may add it, and also add it to the super list, and everytime I want to do something I have to write it for every list (i.e. " if (object is MyArmor){myArmorsList.Add(object);}if (object is MyWeapon){myWeaponList.Add(object);}" ), this seems stupid as it creates a lot of code and introduces error.
    For the past days I've been trying to find the best solution for this type of thing. Using just one list and filter it with linq seems like I'm doing to much usless processing, you're always filtering stuff you filtered a few seconds ago. Interfaces haven't been of much help here either. Generics allow to do several things, and I've used them, but they're a bit ugly and is difficult to make them work (there are cases where you'll need to use some sort of reflection to make them work too). Properties could be a solution, but also seems a bit ugly and prone to error.
    So, how would you handle such a thing?
     
    Last edited: Nov 21, 2019
  2. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,605
    You can have a dictionary of lists with the type as a key.
     
  3. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,605
    or, you can extend list class and make two classes
    first extended list should have events for add/remove/replace items
    and second list should rely on those events to maintain it's content automatically

    Code (CSharp):
    1. class MasterList<T> : List<T>
    2. {
    3. public event Action<T> onAdd;
    4. public void Add(item) {
    5. base.Add(item);
    6. onAdd?.Invoke(item);
    7. }
    8.  
    9. public class SlaveList<U> : List<U>  where U : T {
    10.   public SlaveList(MasterList<T> master) {
    11.     master.onAdd += HandleAdd;
    12.   }
    13.   private void HandleAdd(item) {
    14.     if(item is U){
    15.        base.Add(item as U);
    16.     }
    17.   }
    18. }}
    19.  
    20.  
     
    jvo3dc likes this.
  4. calpolican

    calpolican

    Joined:
    Feb 2, 2015
    Posts:
    204
    Well that idea looks very interesting.
    I'm a bit confuse about the code though. I guess is pseudo code because it throws several erros when I put it in VS. So, let me ask you a few things on how you override the Add method of the List class.
    The first thing that it says is that the paremeter "item" can't be found. Since it doesn't have a type, I tried adding a generic type T. After that it says Add() is hiding the baseclass member. I thought that was the idea, so I marked "Add()" as an override and it says that it can't because the original Add() is not marked as abstract. As far as I know I can't change the original List class (?).
    So I've heard many times of exapanding the List class or making a class that inherits form it, but I'm not sure how to do it. There are other errors that throws that I'm not sure how to fix, for example "master.onAdd += HandleAdd;" says that "no overload for HandledAdd matches delegate Action<T>".
     
  5. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,605
    This is just a pseudocode to illustrate the idea and nothing more. I real implementation i suggest you inherit IList, not List, and delegate implementation to it's private field

    Code (CSharp):
    1. class MasterList<T> : IList<T>
    2. {
    3.   private readonly List<T> list = new List<T>();
    4.   public void Add(T item) {
    5.     list.Add(item);
    6.   }
    7. }
     
    calpolican likes this.
  6. calpolican

    calpolican

    Joined:
    Feb 2, 2015
    Posts:
    204
    I've been trying to follow what you said as best as I could.
    I tried to extend the idea to the rest of the methods of the implementation. Also, not only the master must be able to change the slave lists, but also, the other way around (hopefully without creating an infinte loop).
    This is the code. I post it in case anyone can make use of it, or if you or anyone detects any issues or have any advice on how to improve it. Thanks a lot.

    Code (CSharp):
    1.  
    2. using System.Collections;
    3. using System.Collections.Generic;
    4.  
    5. public class UberList<T> : IList<T>
    6. {
    7.     #region propiedades
    8.  
    9.  
    10.     readonly IList<T> list = new List<T>();
    11.  
    12.     public T this[int index] { get => list[index]; set => list[index] = value; }
    13.  
    14.     public int Count => list.Count;
    15.  
    16.     public bool IsReadOnly => list.IsReadOnly;
    17.  
    18.  
    19.     #endregion
    20.  
    21.     #region eventos para las clases dependientes
    22.  
    23.  
    24.     public event System.Action<T> OnAdd;
    25.     public event System.Action<T> OnRemove;
    26.     public event System.Action OnClear;
    27.  
    28.  
    29.     #endregion
    30.  
    31.     #region acciones disparadas por las clases dependientes
    32.  
    33.  
    34.     private void SlaveAdds(T item)
    35.     {
    36.             list.Add(item);
    37.     }
    38.     private void SlavesRemoves(T item)
    39.     {
    40.             list.Remove(item);      
    41.     }
    42.     private void SlavesClear()
    43.     {
    44.         list.Clear();
    45.     }
    46.  
    47.  
    48.     #endregion
    49.  
    50.     #region implementación
    51.  
    52.  
    53.     public void Add(T item)
    54.     {
    55.         list.Add(item);
    56.         OnAdd.Invoke(item);
    57.      
    58.     }
    59.  
    60.     public void Clear()
    61.     {
    62.         list.Clear();
    63.         OnClear.Invoke();
    64.     }
    65.  
    66.     public bool Contains(T item)
    67.     {
    68.         return list.Contains(item);
    69.     }
    70.  
    71.     public void CopyTo(T[] array, int arrayIndex)
    72.     {
    73.         list.CopyTo(array, arrayIndex);
    74.     }
    75.  
    76.     public IEnumerator<T> GetEnumerator()
    77.     {
    78.         return list.GetEnumerator();
    79.     }
    80.  
    81.     public int IndexOf(T item)
    82.     {
    83.         return list.IndexOf(item);
    84.     }
    85.  
    86.     public void Insert(int index, T item)
    87.     {
    88.         OnAdd.Invoke(item);
    89.         list.Insert(index, item);
    90.     }
    91.  
    92.     public bool Remove(T item)
    93.     {
    94.         OnRemove.Invoke(item);
    95.         return list.Remove(item);
    96.     }
    97.  
    98.     public void RemoveAt(int index)
    99.     {
    100.         OnRemove.Invoke(list[index]);
    101.         list.RemoveAt(index);
    102.     }
    103.  
    104.     IEnumerator IEnumerable.GetEnumerator()
    105.     {
    106.         return list.GetEnumerator();
    107.     }
    108.  
    109.  
    110.     #endregion
    111.  
    112.  
    113.     public class SlaveList<U> : IList<U> where U : T
    114.     {
    115.         readonly IList<U> list = new List<U>();
    116.         UberList<T> master;
    117.  
    118.         #region >> propiedades
    119.  
    120.  
    121.         public U this[int index] { get => list[index]; set => list[index] = value; }
    122.  
    123.         public int Count => list.Count;
    124.  
    125.         public bool IsReadOnly => list.IsReadOnly;
    126.  
    127.  
    128.         #endregion
    129.  
    130.         #region >> constructor
    131.  
    132.  
    133.         //Constructor
    134.         public SlaveList(UberList<T> master)
    135.         {
    136.             master.OnAdd += HandleAdd;
    137.             master.OnRemove += HandleRemove;
    138.             master.OnClear += HandleClear;
    139.             this.master = master;
    140.  
    141.         }
    142.  
    143.         #endregion
    144.  
    145.         #region >> cambios ordenados por el master
    146.  
    147.  
    148.         private void HandleAdd(T item)
    149.         {
    150.             if (item is U myU)
    151.             {
    152.                 list.Add(myU);
    153.             }
    154.         }
    155.         private void HandleRemove(T item)
    156.         {
    157.             if (item is U myU)
    158.             {
    159.                 list.Remove(myU);
    160.             }
    161.         }
    162.         private void HandleClear()
    163.         {
    164.             list.Clear();
    165.         }
    166.  
    167.  
    168.  
    169.         #endregion
    170.  
    171.         #region >> implementación
    172.  
    173.  
    174.         public void Add(U item)
    175.         {
    176.             list.Add(item);
    177.             if (item is T obj)
    178.             master.SlaveAdds(obj);
    179.  
    180.         }
    181.  
    182.         public void Clear()
    183.         {
    184.             list.Clear();
    185.             master.SlavesClear();
    186.         }
    187.  
    188.         public bool Contains(U item)
    189.         {
    190.             return list.Contains(item);
    191.         }
    192.  
    193.         public void CopyTo(U[] array, int arrayIndex)
    194.         {
    195.             list.CopyTo(array, arrayIndex);
    196.         }
    197.  
    198.         public IEnumerator<U> GetEnumerator()
    199.         {
    200.             return list.GetEnumerator();
    201.         }
    202.  
    203.         public int IndexOf(U item)
    204.         {
    205.             return list.IndexOf(item);
    206.         }
    207.  
    208.         public void Insert(int index, U item)
    209.         {          
    210.             list.Insert(index, item);
    211.             master.SlaveAdds(item);
    212.         }
    213.  
    214.         public bool Remove(U item)
    215.         {
    216.             if (item is T obj)
    217.             {
    218.                 master.SlavesRemoves(obj);
    219.             }
    220.          
    221.             return list.Remove(item);
    222.         }
    223.  
    224.         public void RemoveAt(int index)
    225.         {
    226.             if (list[index] is T obj)
    227.             {
    228.                 master.SlavesRemoves(obj);
    229.             }
    230.             list.RemoveAt(index);
    231.         }
    232.  
    233.         IEnumerator IEnumerable.GetEnumerator()
    234.         {
    235.             return list.GetEnumerator();
    236.         }
    237.  
    238.         #endregion
    239.     }
    240. }
     
  7. calpolican

    calpolican

    Joined:
    Feb 2, 2015
    Posts:
    204
    I found that I can't use AddRange() and a few other things with IList.
    Would it affect me if instead of using an IList as my private list I usea a regular list? after all is readonly, it shouldn't matter, right?
     
  8. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,605
    You work is very good, but there are still things to do
    1. When calling an event, you missed ? sign. This is important. It should be OnAdd?.Invoke(item), without it this line will throw exception if there are no slave lists
    2. this[int index] shoud invoke onReplace event because it replaces item in master list with some another item and slave lists must be informed of this change. You need to add this event
    3. It is better to implement IReadOnlyList interface in slave lists than IList so slave lists are just for viewing items and no make changes in master. It is always easier to maintain one point of control(changes) than multiple ones.
     
  9. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,605
    You may implement this method yourself or create your own list interface with it and use it

    Code (CSharp):
    1. IBulkList<T> : IList<T>
    2. {
    3.   void AddRange(IEnumerable<T> range);
    4. }
    I suggest you do that because if you ever use it, then it will be easier to add another event and process multiple added items at once in all slave lists than handling multiple OnAdd events.
     
  10. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    6,775
    Personally I'd just have a List<MyObject> that holds all my inventory. And if I needed the parts of it use the linq method 'OfType'.

    Code (csharp):
    1.  
    2. List<MyObject> Inventory = new List<MyObject>();
    3.  
    4. //elsewhere
    5. var lightestItem = Inventory.OrderBy(o => o.Weight).FirstOrDefault();
    6. var lightestArmor = Inventory.OfType<MyArmor>().OrderBy(o => o.Weight).FirstOrDefault();
    7.  
    As long as this is something you're not doing all the time (like several times per frame, all the time)... it'll work fine.

    I wouldn't bother optimizing this unless I found some bottle-neck down the line.
     
    eisenpony likes this.
  11. eisenpony

    eisenpony

    Joined:
    May 8, 2015
    Posts:
    840
    If you get tired of typing OfType you can make read only collections for the query work
    Code (csharp):
    1. List<MyObject> Inventory = new List<MyObject>();
    2.  
    3. IEnumerable<MyArmor> Armor => Inventory.OfType<MyArmor>();
    4. IEnumerable<MyWeapon> Weapons => Inventory.OfType<MyWeapon>();
    5. IEnumerable<MyItem> Items => Inventory.OfType<MyItem>();
    Or you can flip the idea on its head and have a read only master list

    Code (csharp):
    1. List<MyWeapon> Weapons {get; set;}
    2. List<MyArmor> Armor {get; set;}
    3. List<MyItem> Items {get; set;}
    4.  
    5. IEnumerable<MyObject> Inventory => Weapons.Concat<MyObject>(Armor).Concat(Items);
     
    palex-nx and lordofduct like this.
  12. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    1,524
    If the only thing you would do with the "master list" containing all types is to iterate it, you can easily write a wrapper for iterating all of the sublists:
    Code (CSharp):
    1. IEnumerable<Item> All_Items()
    2. {
    3.     foreach (var i in weapons) yield return i;
    4.     foreach (var i in armor) yield return i;
    5.     foreach (var i in potions) yield return i;
    6.     // etc.
    7. }
    8.  
    9. // Used like this:
    10. foreach (Item i in All_Items())
    11. {
    12.     // Do stuff with item
    13. }
     
    lordofduct likes this.
  13. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    6,775
    This is also a good idea as an inverse of eisenpony and I. Where you join the disparate lists, rather than split the total list.

    Both are equally effective.

    No need to write some large class that has a lot of moving parts that may be hard to test/debug to a stable state.
     
  14. palex-nx

    palex-nx

    Joined:
    Jul 23, 2018
    Posts:
    1,605
    I don't like Enumarables and linq because they introduce allocations in every foreach, have costly count operation, and no fast access to content.
     
    eisenpony likes this.
  15. eisenpony

    eisenpony

    Joined:
    May 8, 2015
    Posts:
    840
    I don't actually use Unity, so I don't always know the caveats hidden in it.. though I thought they had resolved that garbage issue with foreach after getting off that old version of mono.
     
  16. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    6,775
    They have with the foreach.

    linq still has garbage issues.

    But I find its convenience worth it when it's for in frequent stuff. Sure doing it every frame over and over can be bad. But "when user clicks a button in the inventory screen, use linq to filter inventory" and the subsequent 60 bytes of garbage it creates aren't all that bad.

    Heck, a display timer that requires regular updating, and thusly regular string creation, is going to create way more garbage. And that doesn't stop me from having a display timer.

    And yeah, I'm with you... most of my work is actually not in Unity, and linq is freaking awesome in my regular work!
     
    eisenpony likes this.
  17. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    1,524
    You can write wrappers for count and index, too, if you want. (And then you can avoid the IEnumerable by iterating using a regular for loop on the index.)

    Code (CSharp):
    1. public int Count { get {
    2.     return weapons.Count + armors.Count + potions.Count + ...;
    3. } }
    4.  
    5. public Item this[int index]
    6. {
    7.     get
    8.     {
    9.         var sub = ConvertMasterIndex(index);
    10.         return sub.sublist[sub.index];
    11.     }
    12.     set
    13.     {
    14.         var sub = ConvertMasterIndex(index);
    15.         sub.sublist[sub.index] = value;
    16.     }
    17. }
    18.  
    19. private struct SublistAndIndex
    20. {
    21.     public List<Item> sublist;
    22.     public int index;
    23. }
    24.  
    25. private SublistAndIndex ConvertMasterIndex(int masterIndex)
    26. {
    27.     if (masterIndex < weapons.Count)
    28.     {
    29.         return new SublistAndIndex { sublist = weapons, index = masterIndex };
    30.     }
    31.     masterIndex -= weapons.Count;
    32.     if (masterIndex < armors.Count)
    33.     {
    34.         return new SublistAndIndex { sublist = armors, index = masterIndex };
    35.     }
    36.     masterIndex -= armors.Count;
    37.     // etc.
    38. }
    (If I were being serious about this, I would probably put all of the sublists into some kind of meta-collection, like a List<List<Item>> or a Dictionary<ItemCategory, List<Item>>, so that it would be possible to iterate over them and eliminate a lot of the copy/paste code.)

    You could do something similar the other way around by keeping an explicit master list that is sorted by category and caching the starting-index of each category, but that would make it expensive to add new items in any category other than the last one. (Though if your list isn't too big, that might not matter much.)
     
  18. calpolican

    calpolican

    Joined:
    Feb 2, 2015
    Posts:
    204
    I end up using a base class list and made a few Properties that would get the list of subclases (as suggested). The OfType<>() method is much better than what I was using ( ist.Where (x => x is Subclass).Cast<subclass>().toList())
    The biggest issue with this approach is that I can't look at the subclasses bit of info in the inspector. Eisenpony's second approach also seems to have this problem.
     
    Last edited: Nov 23, 2019
  19. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    1,524
    You're not going to be able to see it in the inspector without creating a redundant explicit representation of the data. (Though you could theoretically use a custom inspector where the explicit representation only exists in the inspector and not the class itself.)

    But you don't necessarily want your alternate representations exposed in the inspector--what happens if someone uses the inspector to edit them? You may want to think about alternate ways of accessing that information for debug purposes, such as logging it, or simply using your game's regular UI to view it (presumably you intend to build a way for the player to look at their inventory anyway, and once you do that's probably nicer than using the inspector anyway).

    By the way, remember not to use ToList() unless you actually need the result in list form. If you're just iterating the collection, this causes an unnecessary memory allocation.
     
  20. Owen-Reynolds

    Owen-Reynolds

    Joined:
    Feb 15, 2012
    Posts:
    825
    I always forget caveman tricks and have to force myself to slow down.

    You mentioned how adding an object could add to the masterList and also the particular armour/weapon sublist, but that's lots of code and error-prone? Yes, but write a function Inventory.AddItem(item1). I've done the exact thing -- I was so worried about some complex issue that I forgot the basics.

    Likewise, so many options for storage: keep all lists, or compute sublists as needed, or recompute the master list as needed. But the solution is basic OOP: Inventory.getArmourList(); and so on. Implement it in any piece-of-garbage way and fix it later. I always get all wrapped-up in details and forget interfaces are exactly for this sort of "I don't want to close off making this thing way better, later on" problem.

    And lastly, and I also do this all the time, it's just a speed issue. And it's inventory. How many things do you pick up each frame? Doing it in the worst, sloppiest way will probably be fine. I often start out thinking of the best way to organize it to be readable and easy to code, then slide into the ways it could be more "awesome", when I could have it working good enough and have moved on.
     
    palex-nx likes this.
  21. calpolican

    calpolican

    Joined:
    Feb 2, 2015
    Posts:
    204
    Anistone, my game is an RPG and may not be super conventional inventory wise. Every npc has an inventory, and some items may change hands even when the characters are not in the current scene. So I have like a database where I have all the characters, and it's useful to just expand a particular character I'm targeting and see how the items change hands and properties and check if everything worked as expected. Something that would be useful would be to have a custom inspector that will show a tooltip with this data when you hover over the item. I just would like some way to not have to write every property of the tooltip, as this will force me to write a property every time. Maybe use reflection or something to do it automatically. I'm not very good with custom inspectors, so any ideas are welcome.

    Owen Reynolds, I 've already made the caveman approach since the start and I'm pretty close to completing the game. I've used AddItem() functions, interfaces and many other things. It worked, but even though I'm finishing the game, the caveman systems still give me a lot of headeaches. You may have an AddItem function, but someone in your team (or you!), could make a slip and add an element using List.Add(), and that's only one example of what can go wrong for widely used things.From my experience I don't recommend using this approach in subjects that may be too basic and fundamental like the inventory.
    My game has a lot of inventories, all NPCs use one and may take decisions during playmode base on what elements do they have... but even considering that, I now believe that just using the main list as was proposed in this thread is the best and most practical approach. I totaly agree that it's not worth it using multiple lists.

    The system of using just one list of the base class works really great. It just has this small problem of easily debugging the subclass data. If we find a solution for that, we could use it not only with this but with other polymorphic lists.
     
    Last edited: Nov 28, 2019
  22. Owen-Reynolds

    Owen-Reynolds

    Joined:
    Feb 15, 2012
    Posts:
    825
    Books on OOP from the 1980's (which is when cave men roamed the earth) cover this. This simplest, most useful OOP trick is making data private and designing an interface using public functions. The user might need only dropItem, giveItem, ... . If they really need to run through a list (which they probably don't) then Inventory.getArmourItem(0) is the old way to do it. The explicit point is to prevent what you mentioned -- using ArmourList.Add() by mistake, when they should be using the public Add function for Inventory.
     
    palex-nx likes this.
  23. calpolican

    calpolican

    Joined:
    Feb 2, 2015
    Posts:
    204
    By forcing the list to be private you are already restricting the possibilities of your solution. Think about this: you'd need to write the implementations every time you use a polymorphic list. Is not a bad solution, is just not the best of the ones discussed. If you'd go in that direction, then extending the list class is a similar idea, but a much better option for genralization... basically all the implementation that you're putting to your inventory class (Add, Remove), are now moved to your list class. Not only you can acess the list from another class if you need to, but more important, you only have to write the implementation of the interfaces once and you'll be able to use it for all types of polymorphics list in your project (or in any other project).
    The list extension is better by a factor of all the operations you'd need to do with a polymorphic list * all the time you use one.
     
    Last edited: Dec 3, 2019