## 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");

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;

}

}

}

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;
}

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.

balaam 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...