Friday, January 20, 2006

The Oddment Table

I've only ever heard of oddment tables from one place - a Mr Ray Dillinger on the rec.games.roguelike.development group.. Here's the post in question.

Now I always thought this was pretty good idea but recently I decided it might be nice to implement it in a reusable fashion. First though let's quickly go-over what it is.

Basically it's a list and you ask for an item and recieve one at random. Each item has a different chance of being recieved, and this is called it's oddment. The item you pick remains in the list.

An easy way to think of this might be as a deck of cards. Shuffle the cards and pick the first card from the top. There are only two jokers in there. There are 56 non-joker cards and 2 joker cards. If you pick the top card you are unlikely to get the joker. A oddment table representing this situation would add each of the 56 non-joker cards with the oddment value of 56. Then you'd add the two jokers each with an oddment value of 2. It's that simple.

In a game, especially an RPG game, we might like to think of event cards or encounter cards. Let's say we had wilderness encounter deck, one might encounter rats quite commonly so we add rats with an oddment of 50 but a big box of treasure that's fallen off a cart is rather less likely, so we might put that in with an oddment of 1.

using System;

using System.Collections.Generic;

using System.Text;

using Debug = System.Diagnostics.Debug;

 

namespace EINFALL.Tools

{

    public class OddmentTable<T>

    {

        // Allows comparison of generic types.

        //See: http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=193203&SiteID=1

        private static readonly IEqualityComparer<T> comparer =

            EqualityComparer<T>.Default;

        protected List<Entry> entries = new List<Entry>();

        protected int oddment = 0;

        protected Random random;

 

        /// <summary>

        /// Each item must be associated with it's oddment

        /// in the list. This simple structure does that

        /// for us.

        /// </summary>

        protected struct Entry

        {

            public T Item;

            public int Oddment;

 

            public Entry(T item, int oddment)

            {

                this.Oddment = oddment;

                this.Item = item;

            }

        }

 

        /// <summary>

        /// Create an Oddment table using a precreated

        /// Random object, that will be used to decide the picks.

        /// Useful for repeatable results.

        /// </summary>

        /// <param name="rand">The random object to use</param>

        public OddmentTable(Random rand)

        {

            random = rand;

        }

 

        /// <summary>

        /// Default constructor will seed a random

        /// number generator with the current ticktime.

        /// </summary>

        public OddmentTable()

        {

            random = new Random(System.Environment.TickCount);

        }

 

        /// <summary>

        /// Add an Item and it's Oddment (chance of being picked)

        /// </summary>

        /// <param name="Item">Whatever the Oddment table was intialized to.</param>

        /// <param name="Oddment">The Oddment is the likely hood of getting it.

        /// It should be a non-zero positive number</param>

        public void Add(T item, int oddment)

        {

            Debug.Assert(oddment > 0,

                "The oddment number passed in was" + oddment +

                "\r\nIt should be a positive non-zero integer");

 

            entries.Add(new Entry(item, oddment));

            this.oddment += oddment;

        }

 

        /// <summary>

        /// Randomly pick an Item from the table, where

        /// the items are weighted by their oddments.

        /// </summary>

        /// <returns>The picked Item</returns>

        public T Pick()

        {

            int pickNo = random.Next(oddment);

 

            /// I want to go from 1 to n, not 0 to n - 1

            /// Odds of 0 shouldn't count for anything, in my mind anyway.

            pickNo++;

 

            // This will record the total of the oddments as

            // we tranverse through the table.

            int oddmentTotal = 0;

 

            // Run through the table, total up each Oddment

            // if the Oddment total is bigger than the pick number

            // then return that Item

            foreach (Entry entry in entries)

            {

                oddmentTotal += entry.Oddment;

 

                if (oddmentTotal >= pickNo)

                    return entry.Item;

            }

 

            return entries[entries.Count].Item;

        }

 

        /// <summary>

        /// Gets the number of elements contained in the Oddment table

        /// </summary>

        public int Count

        {

            get

            {

                return entries.Count;

            }

        }

 

        /// <summary>

        /// Remove the first instance of an item from the oddment table.

        /// </summary>

        /// <param name="item"></param>

        public void Remove(T item)

        {

            int i = 0;

 

            // Search through the enteries

            // until we get one with the same name.

            // There maybe a faster way to do this but I don't know how

            for (int j = 0; j < entries.Count; j++)

            {

                if (comparer.Equals(entries[j].Item, item))

                {

                    i = j;

                }

                else

                {

                    if (i == j)

                    {

                        //Remove nothing.

                        //Possibly better to throw exception.

                        return;

                    }

                }

            }

 

            int oldOddment = entries[i].Oddment;

            entries.RemoveAt(i);

            oddment -= oldOddment;

        }

 

 

 

    }

}

3 comments:

phragged said...

I really like your site, your putting up some really interesting stuff I wouldn't find elsewhere. Now to convince you I'm not auto spam :).

I think your numbers are reversed for your example based on rats and treasure. If the rats where at 20 and the treasure was at 167 then there would be 147 more treasure in oddment table than rats. Thus we would expect to see more treasure(which we do if we run your code for -
100,000 times
treasure - 89157
rats - 10843)
so you might want to switch your example text.

Also you could switch this loop
for (int i = 0; i < entries.Count; i++)
{
oddmentTotal += entries[i].Oddment;

if (oddmentTotal >= pickNo)
{
return entries[i].Item;
}
}
with something like this:
foreach (Entry entry in entries)
{
oddmentTotal += entry.Oddment;

if (oddmentTotal >= pickNo)
return entry.Item;
}

to make it more readable.
In the first loop it confused me because your looping through the total number of oddments(instead of the oddment items) and it works, but you never actually make it through entries.count number of oddments the way the code is structured.(which in turn was causing me some confusion in the purpose of the code).

With that being said, I really like the idea of an oddment table. Thanks for bringing it to my attention.

Dan said...

You're totally corrent on both counts :D I think the second one is a bug that just happens not to cause any major problems.

I'll corrent both places now.

Cheers for pointing them out!

Christopher Bennage said...

I was inspired to write something similiar after I read your post about generating randmon names.
I started off the same way, but I "unpacked" the entries into a new internal list.
For example, if the {rats,50} and {treasure,1} oddments are added, the class internally generates a list with 51 items and then chooses a random item from the unpacked list.
I know that's not efficient, but I was running into statistical errors the other way.

I'm also curious to know how you're handling character skills. I'm working on an RPG myself and I haven't been able to find any useful examples.
(I'm also glad to see someone else using C#/NUnit to create RPG's!)