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
