lua-users home
lua-l archive

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


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