Random Item or Monster Spawn Table

Unity Engine
1

RageByte is coding an MMO (working title BR38) and I thought I would share our random weighted List code. Please dissect, interpret, and comment. It works great and please test (with your custom classes).

To use it would be:

WeightedList<int> lootTable = new WeightedList<int>();
lootTable.AddEntry(100, 8); // 80% chance to spawn item 100
lootTable.AddEntry(119, 2); // 20% chance to spawn item 119
int spawnedLoot = lootTable.GetRandom();

To use a custom class:

WeightedList<Monster> monsterList = new WeightedList<Monster>;
monsterList.AddEntry(monster1, 70); // 70% chance to spawn monster1
monsterList.AddEntry(monster2, 30); // 30% chance to spawn monster2
Monster monster = monsterList.GetRandom();

    class WeightedList<T> {
        private struct Entry {
            public T Item;
            public int Threshold;
        }
        private List<Entry> _entries = new List<Entry>();
        private int _totalWeight;
        public void AddEntry(T item, int weight) {
            _totalWeight += weight;
            _entries.Add(new Entry { Item = item, Threshold = _totalWeight });
        }
        private Random _rand = new Random();
        public T GetRandom() {
            int r = _rand.Next(1, _totalWeight + 1);
            foreach (Entry entry in _entries) {
                if (r <= entry.Threshold) return entry.Item;
            }
            return default;
        }
    }
2

The basic algorithm looks sound, though I think there’s room for a few improvements:

  • I’d have your weights be floats instead of ints. If you’ve already got a pool of 50 things at weight 1 and then you want to add something new and have it be less common, you don’t want to have to go through and change all the existing stuff.

  • GetRandom() could use a binary search instead of traversing the list in order. This would make the asymptotic running time O(log n) instead of O(n), which could be a significant advantage for large pools. (But note this is only really relevant if you’re going to have a lot of random drops from a single pool; creating the pool is O(n) so if you only use it a few times this probably doesn’t matter.)

  • “List” is a bit of a misnomer, since you don’t provide random access and can’t remove stuff. I might call it something like “WeightedPool”.

By the by, you have an error at the start of line 3 of your second example snippet.

3

Your comments are well noted. I attempted implementing the BinarySearch to the custom list but had no luck. Probably didn’t get the IComparer working correctly. The spawn lists and loot lists are not huge and are one offs from time to time so I think they will work as is. Call it a List because of the norm as in a spawn list, loot list, could call it a table I guess. Spawn table, loot table. I guess it’s pick your poison.

4

Well, spent the whole afternoon researching C# List BinarySearch that applies to an Int range and had no luck…
n = 1;
n = 5
n = 10;
Assume those are in a list and do a BinarySearch where a random variable is <= n. Good luck!