Object Generation - Tables vs Fractions
su
table when generating random items?
> Roguelike article follows:
(I release this into the public domain for anyone to use in their
roguelike game development article collection or FAQ, 11/25/2005 -
Steve U.).
Object Generation - Tables vs Fractions
(NOTE: Use fixed width font to get this to line up correctly.)
Roguelike games must generate items randomly for gameplay
variety and game balance.
Game variety means that the player will not see the exact same
items in each game, in the same order and same quantity. This helps
to keep a good game replay factor.
Game balance means that the more powerful items are less likely
to be found by the player because they will unbalance the game in ways
such as making the player much stronger than the monsters he will
face in the game.
Therefore, the generalization of this requirement is that some
items should be more common and some items should be much less likely
to be found. Furthermore, the more common items are generally weaker
and the rarer items are stronger.
This article compares item generation using percentage tables to item
generation using fractions.
This can be generalized to treasure generation, monster generation and
room generation (i.e., treasure vault rooms should be hard to find).
Tables - Percentage Tables for Item Generation
A percentage table is a table giving the various percent chance of
an item being generated.
For example, roguelike game X has 10 potions generated
with the following percentages:
potion | percent | name
number | chance |
_______|_________|__________________
0 | 20 | healing
1 | 20 | speed
2 | 20 | confusion
3 | 10 | sleep
4 | 10 | detect food
5 | 5 | detect objects
6 | 5 | detect monsters
7 | 5 | poison
8 | 3 | gain strength
9 | 2 | gain level
______________________________
10 | 100 | sum totals
Generating a potion using the table would be:
bool generate_potion(POTION_STRUCTURE &p)
{
x = random number from 0 to 99
total = 0
counter = 0; /*first element in table*/
while (counter < 10)
{
total = total + potion_table[counter].percent_chance
if (total > x)
{
p = potion_table[counter];
return (TRUE); /*potion found*/
}
counter = counter + 1
}
return(FALSE) /*error, no potion found*/
}
The percentage table has the advantages of clearly showing the
percent chance each item may be generated.
It has the disadvantage of being a slower than
fractions because it is a linear search of the
entire table. This can be important in tables with
hundreds of entries. The speed is usually not important
because tables are generally small and also because
there are quite efficient methods of searching a table.
(Faster search methods are not covered here).
Fractions for Item Generation
The fractional approach is to generate items using
successive random numbers. Each random number
subdivides the set of items possibly generated into a
smaller group.
Using fractions for potion generation using the same
percentages as above gives the following algorithm.
x = random number from 0 to 4
potion_found = -1
if (x <= 2)
potion_found = x /*healing, speed or confusion - 60% of the time
(3 * 20%)*/
else
{
if (x == 3)
{
if ((random number from 0 to 1) == 1)
potion_found = x /*sleep - 10% of the time*/
else
potion_found = x + 1 /*detect food - 10% of the time*/
}
else /*x == 4*/
{
x = random number from 0 to 3
if (x <= 2)
potion_found = 6 + x /*detect food, objects, monsters - 15%
of the time (3 * 5%)*/
else
{ /*x == 3*/
if ((random number from 0 to 4) <= 2)
potion_found = 9 /*gain strength - 3% of the time*/
else
potion_found = 10 /*gain level - 2% of the time*/
}
}
}
The main advantage of using fractions is that
they are faster than a table search. The main
disadvantage of using fractions is that calculating
the actual percentage occurance of each item being
generated may be difficult and introduce
unwanted errors.
One such unwanted error, such as generating
potions of gain level 30 percent of the time, would
unbalance the game since the player would advance
in level much faster and almost always be much
more powerful than a monster he fights.
The Big Picture: Gamewide Item Probability
One factor to consider is that object, treasure,
monster and trap generation need to be balanced
for good gameplay.
This means that there may be multiple levels of
calculations done before an item, object, etc is
generated.
For example, the game developer may want
wands to be harder to find than armor.
One way of doing this would be to have a large
table listing every possible armor, weapon, scroll,
and potion in the game along with the percent
chance of it being generated. This would be
difficult to determine what chance each class of
item has of being generated.
Another way would be to have two tables, one for
item class and one for individual items. Generating
an item would follow these steps
int generate_random_item()
{
item = -1
item_class = generate_random_item_class() /*uses item class table*/
if (item_class == FOOD)
item = generate_random_food() /*uses food table*/
else if (item == POTION)
item = generate_random_potion() /*uses potion table*/
else if (item == SCROLL)
item = generate_random_scroll() /*uses scroll table*/
else if (item == WEAPON)
item = generate_random_weapon() /*uses weapon table*/
else item = generate_random_armor() /*uses armor table*/
return(item)
}
The multiple table approach works well when you
need to segregate items into groups of how powerful
the item is. You may want to make the most powerful
weapons, armor, scrolls and potions all occur 1
percent of the time. You would then have the item
class table have the categories:
percent | item class
chance |
______________________
30 | scroll
19 | armor
20 | weapon
30 | potion
1 | SPECIAL
An advanced topic not covered here is using a item
class table that just contains an index into a
global item table. The global item table would contain
each item in the game in a single table. The item
class table would break the global item table into
subsets based on each item class.
Future Direction One: Extensibility
One area impacting roguelike game development is that during
development the list of items in the game changes from one
game version to the next.
An item generation using fractions approach may be harder to
adjust for new items added along with old items removed from
the game since not every item should have the same percentage
chance of being generated.
An item generation using percentage table is easier to add new
items to as well as remove items from.
One modification of the table approach will greatly simplify
this change. Instead of generating numbers from 0 to 99 to pick
an item from the table, generate numbers from 0 to 999 and
adjust the table to allow for numbers from 0 to 999. This gives
much finer precision to adjust the chance any given item is
generated.
For example, a powerful potion such as "Genocide Monster"
should be very rare. In that case, the table entry for it would
be 1 on a scale of 0 to 999. This would give the percent
chance of it being generated to be 1 out of 1000 or 0.1 percent.
Future Direction Two: Compactness, Maintainability, Simplification
One of the problems faced with roguelike games is that
they typically include a large number of items, monsters,
traps and room types. This becomes difficult to understand
and difficult to progress the game development as more and
more things are added.
One approach to limiting internal game complexity is to
store every item into one large table and also to store all
things associated with an item in a single entry in the table.
A game with 100 items where each item has a symbol,
name, color, weight, item type, and other fields would then
have an array of structures of the following format.
structure GAME_ITEM
{
char symbol;
char name[100];
enum COLOR_TYPES color;
unsigned int weight
... (other fields)
}
This is much simpler to manage since all things
associated with one item are together and not separated
into multiple tables.
Real World Example: Mike's Adventure Game
Mike's Adventure Game (MAG) uses fractions to
generate items. Below is a greatly simplified version of
the algorithm. Calculating the probabilities is not too
difficult but can be error prone. Consider how to add
a new scroll that occurs 1.5 times as frequently as
your average scroll. Or for gameplay balance, consider
adding a scroll that should occur 1/100th as frequently
as the average scroll since it is very powerful and
therefore greatly affects gameplay balance.
int getoff(int type) /*type is the type of object to generate*/
{
/*NOTE: rnd(X) returns a random number from 0 to (X-1)*/
switch (type)
{
case FOOD: return(random food) /*equal probability for all
foods*/
case WAND: return(random wand) /*equal probability for all
wands*/
case RING: return(random ring) /*equal probability for all
rings*/
case POTION:
i = random potion number out of 21 different potions
if (i == HEROISM || i == RAISELEV)
{
if (rnd(2) != 0)
{ /*convert to other more common potion type*/
if (rnd(2) != 0)
return (HEALING)
else
return (RESTORESTR)
return i;
case SCROLL:
i = random scroll number out of 21 different scrolls
convert = FALSE
if (rnd(10) == 0)
convert = TRUE
else
{
if (i == GENOCIDE || i == HOLDMON)
{
if (rnd(2) != 0)
convert = TRUE
}
}
if (convert == TRUE)
{ /*convert to more common scroll*/
if (rnd(2) != 0)
return(IDENTIFY)
else
return(MAGICMAPPING)
}
return i;
}
}
(I release this into the public domain for anyone to
use in their roguelike game development article
collection or FAQ, 11/25/2005 - Steve U.).
Motivation: In the process of writing a FAQ for the
roguelike game "Mike's Adventure Game" I had to trace
lots and lots of "if then else" fraction based code to
determine the percent chance of a given item being
generated. This was significantly more time
consuming than I expected. The code was well written
but figuring out the actual probabilities was a long
process. This article is to spark discussion on which
method is better and possible to generalize item
generation or multi-table generation into a much
simpler and less error prone method.
(end of article)
Christophe Cavalaria
Not sure it is slower because of the randomness. Since the table is sorted
with high probability items first, it'll be very uncommon to do a full
table search. It'll happen exactly 2% of the times it's used ;)
I know you said that better algorithms for table search aren't to be
discussed here, but I must remark that the fraction system is just a hand
crafted binary search tree which needs one random number by level. If you
create a binary search tree out of the first table, you get all the
advatages of the table search with even more speed than the fraction system
( less random number generation ). Also, the table system is more of a data
driven design which is a *good* thing.
Ray Dillinger
Nice comparison of successive fraction tables and percentage
tables, but you're missing what is, IMO, a better option than
either: Oddment tables.
Also, you're missing an important fact about the interaction of
your random number generator with successive fraction tables;
briefly, if your random number sequences display characteristic
orders or intra-number dependencies, you're going to wind up
with probabilities that are *NOT* in fact what your code would
imply.
Here's how oddment tables work; You have a table with all your
stuff in it, like a percentage table. However, instead of
assigning everything a percentage, you assign everything an
oddment - some integer greater than zero. And every time you
add something to the table (or when you index it, if it's a
static table) you add its oddment to the total. Now whenever
you want to generate something, you generate a random number
ranging from 0 to the total number of oddments in the table,
giving each oddment an equal probability of being rolled.
Indexing is mildly important; you don't really want to do a
linear search. But in a pinch, you can get away with just
sorting common items to the front and optimizing the common
cases.
The beauty of an oddment table is that you can still have items
with different classes have different rarities. You just make
their oddment the product of a constant by-class and a constant
for their own rarity. F'r example,
#define ARMOR_PROB 33
#define WAND_PROB 20
#define ARTIFACT_PROB 1
addtotable(gentable, @wand, (WAND_PROB * wand.rarity));
addtotable(gentable, @armor, (ARMOR_PROB * armor.rarity));
etc...
gives you an overall factor for wand probability that you
can adjust relative to armor probability, changing the entire
table at once just as for a successive fraction table.
The probability calculation for any given item is
straightforward, it's resistant to bias by the RNG, and
as with any table, given some indexing it's a constant time
lookup.
Other advantages include maintainability, in that when you
add an item, it's automatic that the probability of all other
items is decreased proportionally; you don't have to "carve
out a space" for it.
Bear
Raghar
news:1132970073.8...@z14g2000cwz.googlegroups.com:
> Q: Is it better, easier and less error prone to use a percent
> table when generating random items?
>
>> Roguelike article follows:
>
> (I release this into the public domain for anyone to use in
> their roguelike game development article collection or FAQ,
> 11/25/2005 - Steve U.).
>
> Object Generation - Tables vs Fractions
>
I rather use culture/place/environment based results, and Markov
chains.
I also use proper random numbers, and use one random number for its
full potential.
It could be fun to combine it together when you are creating random
equipment for NPC. Experience of NPC, from he is from...
Note in your article you used percentages, it's generally bad idea.
If you would use 3, 3+5,3+5+3,3+5+3+2 as chances of eash item and do
roll 0-3+5+3+2-1 inclusive you are in much better situation. (One
reason is these numbers does have often some meaning, and conversion
to percentages would cause a lot of problems.) Also no percentages,
no need for renormalization.
Brendan Guild
> I also use proper random numbers, and use one random number for its
> full potential.
I'd be interested in some elaboration on this. What is a 'proper random
number'? It sounds like a real random number; i.e. not a pseudo-random
number as can be generated by a computer. If it is not that, then what is
it?
How do you use each random number to its full potential? Is there some
benefit to using each random number more completely and needing fewer of
them instead of using more random numbers?
Michal Brzozowski
I think it should be noted that a simple binary search can be
used to take the complexity of the search down to O(logn).
You just have to store the sum of probabilities, like this
potion | percent | name
number | chance |
_______|_________|__________________
0 | 20 | healing
1 | 40 | speed
2 | 60 | confusion
3 | 70 | sleep
4 | 80 | detect food
5 | 85 | detect objects
6 | 90 | detect monsters
7 | 95 | poison
8 | 98 | gain strength
9 | 100 | gain level
______________________________
10 | 100 | sum totals
bool generate_potion(POTION_STRUCTURE &p)
{
x = random number from 0 to 99
jump = number_of_elements/4;
counter = number_of_elements/2; /*middle element*/
while ((potion_table[counter]<x || potion_table[counter-1] >x) &&
jump>0 )
{
if (potion_table[counter]<x)
counter+=jump;
if (counter>0 && potion_table[counter-1]>x)
counter-=jump;
jump=jump/2;
}
p=potion_table[counter];
}
The above code might not work as intended, I don't take any
responsibility :)
ga...@dsdata.it
Michal Brzozowski wrote:
> I think it should be noted that a simple binary search can be
> used to take the complexity of the search down to O(logn).
> You just have to store the sum of probabilities, like this
[...]
It should also be noted that the index required by a binary search can
be computed automatically, making definitions of stuff as simple as
possible (just give one unnormalized probability, with no need to sort
definitions or compute sums).
Long and brittle functions full of magic numbers and irrelevant
classifications and decision trees like the one in the original post
have no reason to be used.
Lorenzo Gatti
Christophe
One way to do it easily ( ie : without having to use those pesky tree
structures ) is :
For each line in the table, compute the sum of the probabilities above it :
potion | percent | total | name
number | chance | chance |
_______|_________|________|_________
0 | 20 | 0 | healing
1 | 20 | 20 | speed
2 | 20 | 40 | confusion
3 | 10 | 60 | sleep
4 | 10 | 70 | detect food
5 | 5 | 80 | detect objects
6 | 5 | 85 | detect monsters
7 | 5 | 90 | poison
8 | 3 | 95 | gain strength
9 | 2 | 98 | gain level
10 | 0 | 100 | end of table marker
_________________________________________
Total probability : 100
nbObjects = 10
PS : don't sort by probability since it'll give you a worse case than
with a random sort and you don't need the total probability to reach 100
Now, select at random a number between 0 and 99 included. This is the
item you want to create. Now to find it all you need is a dichotomic
search ( in Python ) :
r = randint(0,99)
a = 0
b = nbObjects-1
while a <> b:
c = (a+b)//2
if total_chance[c] < r:
a = c
elif total_chance[c] > r:
b = c
else:
return c
return a
Now, let's imagine that for a reason or another, you need the item to be
selected between line 2 and 7 included ( and starting at 0 ). Easy to
do, just change 3 initialisation lines to that :
a = 2
b = 7
if a > 0:
r = randint(chance[a-1],chance[b])
else:
r = randint(0,chance[b])
Here the full example code for future reference. Should be easy enouth
to convert it in another language.
import random
class item_generator(object):
def __init__(self, chance_list):
self.chance_list = chance_list
s = 0
self.total_chance = [0]*len(chance_list)
for i,c in enumerate(chance_list):
self.total_chance[i] = s
s += c
self.total_chance[-1] = s
def generate_item(self):
return self.generate_item_between_range(0, len(self.chance_list)-2)
def generate_item_between_range(self, a, b):
assert a >= 0 and a < len(self.total_chance)
assert b >= 0 and b < len(self.total_chance)
assert a <= b
b += 1
r = random.randint(self.total_chance[a],self.total_chance[b]-1)
while b-a > 1:
c = (a+b)//2
if self.total_chance[c] < r:
a = c
elif self.total_chance[c] > r:
b = c
else:
return c
return a
chance = [20,20,20,10,10,5,5,5,3,2,0]
ig = item_generator(chance)
print ig.generate_item()
print ig.generate_item_between_range(2,4)
This post and everything inside it is free to use in any way you please
so if you want to cut and past the code, by all means do it ;)
konijn_
Idea stolen from Tyrant :
Potion | percent | name
number | chance |
_______|_________|__________________
0 | 3 | gain strength
1 | 5 | poison
2 | 10 | detect food
3 | 20 | healing
4 | 20 | speed
5 | 20 | confusion
6 | 10 | sleep
7 | 5 | detect objects
8 | 5 | detect monsters
9 | 2 | gain level
______________________________
10 | 100 | sum totals
Notice, how these could be accessed by a bell curve.
Generating a potion using the table would be:
bool generate_potion(POTION_STRUCTURE &p)
{
p = potion_table[ getanicebellcurvenumber( 0 , 10 ) ];
}
Wouldnt that be much easier ??
T.
David Damerell
>su wrote:
>>For example, roguelike game X has 10 potions generated
>>with the following percentages:
item creation code, is a bit mad.]
>I think it should be noted that a simple binary search can be
>used to take the complexity of the search down to O(logn).
Faster than that; have an array of size equal to the total of all your
probabilities filled with pointers to the relevant object type.
--
David Damerell <dame...@chiark.greenend.org.uk> flcl?
Today is Second Sunday, November - a weekend.
jimrandomh
>
> Notice, how these could be accessed by a bell curve.
>
> Generating a potion using the table would be:
>
> bool generate_potion(POTION_STRUCTURE &p)
> {
> p = potion_table[ getanicebellcurvenumber( 0 , 10 ) ];
> }
>
> Wouldnt that be much easier ??
No, it wouldn't be easier, because that's not quite a bell curve. And
as you add more potion types, not only will it look less bell curve-
like, it's very hard to predict how the addition of any single new
potion type will affect the appearance of the others.
For example, suppose you want to add potions of extra healing without
messing up the game balance. What you would do is make potions of extra
healing appear, say, 5% of the time, and make potions of regular
healing appear 5% less of the time, so that no other items are
affected. If you used some convoluted scheme like this, you might find
out that you accidentally made potions of gain strength rarer and the
game was a lot harder because of it.
--
CalcRogue: TI-89, TI-92+, PalmOS, Windows and Linux:
calcrogue.jimrandomh.org/
Remove the "NOSPAM" from my e-mail address to contact me.
konijn_
> "konijn_" <kon...@gmail.com> wrote:
> > <Major snip>
> >
> > Idea stolen from Tyrant :
> <snip table>
> >
> > Notice, how these could be accessed by a bell curve.
> >
> > Generating a potion using the table would be:
> >
> > bool generate_potion(POTION_STRUCTURE &p)
> > {
> > p = potion_table[ getanicebellcurvenumber( 0 , 10 ) ];
> > }
> >
> > Wouldnt that be much easier ??
>
> No, it wouldn't be easier, because that's not quite a bell curve. And
> as you add more potion types, not only will it look less bell curve-
> like, it's very hard to predict how the addition of any single new
> potion type will affect the appearance of the others.
? Common potions will be common , rare potions will be rare, uncommon
potions will be uncommon etc.
> For example, suppose you want to add potions of extra healing without
> messing up the game balance. What you would do is make potions of extra
> healing appear, say, 5% of the time, and make potions of regular
> healing appear 5% less of the time, so that no other items are
> affected.
I think a curve still allows healing potions to be placed farther from
the center and the addition of a extra healing potion at the outer end.
>If you used some convoluted scheme like this, you might find
> out that you accidentally made potions of gain strength rarer and the
> game was a lot harder because of it.
I fail to see how this is convoluted. Common items in the center, rare
items on the edges.
A one-liner to determine the potion. Maybe too simplistic, but
convoluted ...
konijn_
> "konijn_" <kon...@gmail.com> wrote:
> > <Major snip>
> >
> > Idea stolen from Tyrant :
> <snip table>
> >
> > Notice, how these could be accessed by a bell curve.
> >
> > Generating a potion using the table would be:
> >
> > bool generate_potion(POTION_STRUCTURE &p)
> > {
> > p = potion_table[ getanicebellcurvenumber( 0 , 10 ) ];
> > }
> >
> > Wouldnt that be much easier ??
>
> No, it wouldn't be easier, because that's not quite a bell curve. And
> as you add more potion types, not only will it look less bell curve-
> like, it's very hard to predict how the addition of any single new
> potion type will affect the appearance of the others.
? Common potions will be common , rare potions will be rare, uncommon
potions will be uncommon etc.
> For example, suppose you want to add potions of extra healing without
> messing up the game balance. What you would do is make potions of extra
> healing appear, say, 5% of the time, and make potions of regular
> healing appear 5% less of the time, so that no other items are
> affected.
I think a curve still allows healing potions to be placed farther from
the center and the addition of a extra healing potion at the outer end.
>If you used some convoluted scheme like this, you might find
> out that you accidentally made potions of gain strength rarer and the
> game was a lot harder because of it.
I fail to see how this is convoluted. Common items in the center, rare
items on the edges.
A one-liner to determine the potion. Maybe too simplistic, but
convoluted ...
>
Krice
> ? Common potions will be common , rare potions will be rare, uncommon
> potions will be uncommon etc.
That reminds me.. I don't use percent values per item at all. Instead
I have an abstract value like "rare" or "common" in item data. Then
I have selected some amount for rare items, like 5 and create 0-5
items from rare item list.
Raghar
news:Xns971A926DBF...@64.59.144.76:
I would like to try to write a small article about it. So it would
be a while before answer.
Shortly yes there is benefit, if your RNG is not completely broken.