Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
September 17, 2019
arrowPress Releases







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Simulating a loaded dice in a constant time

Simulating a loaded dice in a constant time

April 9, 2012 | By Jaewon Jung

April 9, 2012 | By Jaewon Jung
Comments
    3 comments
More: Console/PC, Programming



[In this reprinted #altdevblogaday in-depth piece, Crytek's technical lead Jaewon Jung explains how to simulate loaded dice using the alias method algorithm, and shares his C++ implementation.]

A fair dice can be easily simulated with rand() function(or C++11 std::uniform_int_distribution) and integer modulo arithmetic. Then how about a loaded dice (a dice with a non-uniform probability for each face)?

No sweat. Just partition a normalized range of 0.0 to 1.0 according to each probability and bin the result of a random function to a corresponding subrange. But the search will require O(n) time complexity(here, n is the number of dice faces).

Can we do better? Sure. One can do a binary search or similar, then one can get a result of rolling a loaded dice within O(logn) time complexity. How about a constant time complexity? Can we achieve that?

Surprisingly (to me, at least), it's possible. There is an algorithm called 'alias method' which guarantees O(1) generation cost once an initialization step(i.e. preprocessing) of O(n) has been done.

This algorithm is from a paper called "A Linear Algorithm For Generating Random Numbers With a Given Distribution" by Michael Vose.


Original probability distribution(top) and aliased one(bottom)

Let's suppose a dice with four faces, each of which has a probability of 1/2, 1/3, 1/12 and 1/12. The probability distribution can be visualized as the top diagram above. The gist of the alias method is to transform the diagram to something like the bottom one. The essential point is that each column in the bottom diagram has at most two items.

By simulating a fair dice to select a column and then flipping a biased coin, which matches to the probability distribution of in the column, to select between the two, one can get the result. A new item added to the original one in that column is called an alias of it, so the name of the algorithm. Quite neat, isn't it?

I learned this algorithm from this excellent (though, rather long) article, Darts, Dice, and Coins: Sampling from a Discrete Distribution. So I highly recommend reading it for more kind & thorough explanation of the matter. Especially, you can check there how the alias table can be generated in a linear time.

The author of the article also provides a Java implementation of it here. Here is my C++ implementation, which is a basic porting of the Java implementation.

[This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]


Related Jobs

Daybreak Games
Daybreak Games — Austin, Texas, United States
[09.16.19]

Senior Engine Programmer
Daybreak Games
Daybreak Games — Austin, Texas, United States
[09.16.19]

Senior Server Programmer
Daybreak Games
Daybreak Games — Austin, Texas, United States
[09.16.19]

Senior Tools Programmer
Disbelief
Disbelief — Cambridge, Massachusetts, United States
[09.16.19]

Senior Programmer, Cambridge, MA









Loading Comments

loader image