lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On 26/10/2012 19:22, spir wrote:
Hello,

This is more an algorithmic question than a Lua-related one, however I thought others may be interested, since it touches a recurring issue in game-programming, i guess.

The problem is, how to toss a choice in a set of discrete values, each having a relative probability (represented by an integer, sometimes a %age). To make things more concrete, say there are 3 choices a,b,c, which probability law (distribution) looks like this:

      X
    X X
    X X X
    -----
    a b c

What we want is toss according to these relative probabilities.

A simple solution is to make a "sampling set"
    {a,a, b,b,b, c}
and randomly toss in there.

However, this may be very costly due to the construction of the set-table. It's only good when tossing multiple times from the same set, which is not the general case. In my case, values are terrain codes for a map generator. I want each tile to be tossed according to user-given probabilities for each terrain, but above all taking into account types of already defined surrounding tiles, and weighted by a homogeneity factor (which multiplies cardinality of each terrain code of defined neighbour tiles). This means a sampling set should be constructed for each tile, and it can be big (0 <= homogeneity <= 100, meaning max size is 600 for a hex map). I could have a table of max size, and just override its items, then toss among actual number of codes. But this still seems a bit stupidly costly.

Another solution I thought at is to use a multiset, with cardinalities represents relative probabilities of codes:
    {{a,2}, {b,3}, {c,1}}
Actually, if codes are plain ordinals, then it can just be:
    {2, 3, 1}    -- sum = 6
I'd just toss random(6), then iterate on cardinalities (summing on the way) until I reach a value >= toss result.

This is the best I could find for now. But I still have the impression of missing an obvious point...
What do you think?

Thank you,
Denis




For faster tosses (O(log n) instead of O(n)), you may store the partial sums in an array and do a binary search of your random(sum) number.

In your example the array would be:

{0, 2, 5, 6}  -- (0, 2, 2+3, 2+3+1)

so if the random number is 3, which falls in the 2nd interval [2, 5[, the answer is the 2nd choice b.

Frédéric