[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: random toss of discrete values with (integer) probability distribution
- From: spir <denis.spir@...>
- Date: Fri, 26 Oct 2012 19:22:34 +0200
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