Weighted random object selection

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In Quest For Pants, each dungeon level has random items strewn
throughout it. As it is now, the items are picked completely randomly
which means, in practice, that you end up with really good armour very
early on. As a result, if you can survive the first hundred turns,
you're invincable for the rest of the game.

This is Not Good.

I want to weight the object picking algorithm so that quality of the
stuff you find increases in proportion to the dungeon level you're
on. I don't want it to be _impossible_ to find a good item on the top
level, only unlikely.

So far, I've added a "cost" attribute to each object to determine its
value. I'm now in the process of coding up a routine to actually pick
items for a level, but I've gotten bogged down.

My code is ugly and kludgy and I have a feeling that there's a simple
and elegant way to do this that I'm not seeing. Anyone have any ideas
what it may be?


--Chris


--
Chris Reuter http://www.blit.ca
"Feel free, as long as you only quote it in long trotskyite diatribes about
the evils of objectivism."
--Charlie Stross, granting permission to be quoted in a .sig

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

On Mon, 9 May 2005, Chris Reuter wrote:
>
> I want to weight the object picking algorithm so that quality of the
> stuff you find increases in proportion to the dungeon level you're
> on. I don't want it to be _impossible_ to find a good item on the top
> level, only unlikely.

If you want to do it in full generality, you'll come up with
mathematical "distribution functions" (which could even be represented
in code by procedure-type "functions") for all your items, and then
when it comes time to spawn an item, do it according to those
distributions.
To use Timothy Pruett's example, you could say that Dirty Rags
generally appear on the first few levels of the dungeon, but exponentially
less often as you get deeper (so the player doesn't get irked by useless
drops). Drops of Plate Mail might cluster around level 10, with 95 percent
of Plate Mail drops encountered between levels 5 and 15. And so on.
Encode these distributions using two or three numbers each; for example,

Item: Plate Mail
Distribution: Normal(10, 5/3)

Item: Dirty Rag
Distribution: Exponential(4)

and then make sure your engine "knows" what normal and exponential
distributions look like.

When it comes time to drop an item, you just run through all the items
in the game and add up their likelihoods of appearing at this depth.
For example, any given Dirty Rag would have a 3-percent chance of
appearing at level 9 as opposed to some other level; a Plate Mail would
have a 16-percent chance of appearing at level 9. (I got these numbers
by plugging into the formulas defined by "Normal" and "Exponential"
distributions; Google for more information on the math.)

So if these were our only two items in the game, we'd drop a Dirty Rag
3/19 of the time, and a Plate Mail 16/19 of the time, on level 9.

Now, obviously you don't want to have to run through the entire item
list every time you spawn a random item! But luckily, all this can be
precomputed, during game load or even at compile time (if the item
distributions are fixed at compile time). Then you just have to do a
table lookup for each drop, and it's nice and fast.

As for how to select a random item from a list, with or without weights,
that's a FAQ, and I'm sure you can find it on your own in five minutes
if you don't know already.

-Arthur

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <WbydneBCK5qOI-LfRVn-3g@adelphia.com>,
Timothy Pruett <drakalor.tourist@gmail.com> wrote:
>Chris Reuter wrote:
>>
>> I want to weight the object picking algorithm so that quality of the
>> stuff you find increases in proportion to the dungeon level you're
>> on. I don't want it to be _impossible_ to find a good item on the top
>> level, only unlikely.

>I'd just weigh the value of the object against a probability that
>increases as the player goes deeper in the dungeon. Whenever it comes
>time to place a new item down, just grab a random item, and run a test
>on it, like (ItemValue <= DungeonLevelModifier * RandomPercentage).
>If the item passes the test, lay it down. If it fails, try again with
>a new random item.

Two problems:

1) What if there are few (or no) objects that can pass the test?
That it could take thousands of itterations just to generate one item.

2) As you mention in the snipped text, this doesn't reduce the
chance of low-quality items, so they end up crowding out the
high-quality items, which is something I want to avoid.

I've since gone ahead and tried something pretty simple:

AllObjectsSorted = list of all possible objects sorted by value

GenerateNewObject (currentDungeonLevel) {
s = AllObjectsSorted.size() / MaxDungeonLevels;
index = currentDungeonLevel d s; /* D&D-style dice notation. */
return AllObjectsSorted[index];
}

(Note that above, "X d Y" means "roll X dice with Y sides".)

The major problem with this is that the range of items associated with
a particular level isn't necessarily proportional to the level. If,
say, there's a long range of items with the same value, going down
some levels won't help you get better items.

On the other hand, I'm thinking that this kind of chaos may be a good
thing.


--Chris


--
Chris Reuter http://www.blit.ca
"If by 'misunderstood' you mean that his insane rantings are unintelligible as
he attacks you with a spork, yeah. You may be right."
--Get Fuzzy, 2003/12/14

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

[...]
> The major problem with this is that the range of items associated with
> a particular level isn't necessarily proportional to the level. If,
> say, there's a long range of items with the same value, going down
> some levels won't help you get better items.
[...]

Don't use the item's value.

Instead, in the item ID (I'm assuming you've assigned a unique numerical ID
to each item), make the first x digits be the ideal level location, and the
last y numbers the actual ID.

For example

00300156 could be the ID for one item, where the 003 is the level the item
is ideally found in, and 00156 is the item's unique ID.

An additional trick you can use to make this even better is keeping track of
the ranges of the levels (for example, an array whose index is the level and
whose stored value is the index in the master item array where that level
starts (or ends)).

For example, let's say your master item array (sorted) looks like this (for
a game with 3 dungeon levels):

i ID ItemName
[0] 00000001 Foo Sword
[1] 00000002 Bar Axe
[2] 00100003 Sharp Pointy Teeth
[3] 00100004 Chainmail
[4] 00200005 Holy Grail
[5] 00200006 Holy Hand Granade

Then you can have a level tracker array that looks like (for ending
indeces):

[0] 1
[1] 3
[2] 5

The whole point of this level tracker array is so you won't have to search
through your master item table every time you need to get the ranges for one
level.

Advantages to this approach:

* Faster for item generation -- as mentioned earlier, with the hit-or-miss
method you can take a long/infinite time if there are little/no items in the
array.
* Faster for item lookup -- Having a unique ID for item lookup is useful,
and binding the ideal dungeon level to this same ID means we don't have to
sort multiple ways.
* Less space/time -- As an addendum to the earlier points, you won't need to
resort the array by value like you had earlier (or make a copy of the
array).
* You have flexibility in what range of levels the item can come from, for
example, instead of generating a random item from that level only, you can
generate it from (lvl-3) to (lvl+3) (assuming a larger array/game, won't
work for my example, but bound checking is up to you .
* If you find tracking the ranges tedious by hand, you can write a routine
that builds this array for you (this only needs to be done at initial
loadtime, or you can even do it at compile time, grab the result, and
hardcode it for additional efficiency).


Hope I was of help! If anything is unclear, feel free to ask

--Nolithius