need help finding a RNG method

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Hi im kinda getting back into the c++ scene after about a 3 year period
away from it and would appreciate some input on how to as easily as
possible impliment random number generation in c++. Please note i
havent coded in a long period of time and may need to have things
explained in a almost Dr. Suess way.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Catyalyst wrote:
> Hi im kinda getting back into the c++ scene after about a 3 year period
> away from it and would appreciate some input on how to as easily as
> possible impliment random number generation in c++. Please note i
> havent coded in a long period of time and may need to have things
> explained in a almost Dr. Suess way.

The Mersenne twister is a very good algorithm for roguelikes. not
random enough for encryptions and other applications requiring very
random numbers, but it should be fine for a roguelike.

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

Just take init_genrand(unsigned long s) and feed it the time when you
start the program, and use genrand_int32(void) % x to get a random
number between 0 and x. type cast it if you want an int. Happy coding!

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

"Catyalyst" <catalyst5505@gmail.com> writes:

> Hi im kinda getting back into the c++ scene after about a 3 year period
> away from it and would appreciate some input on how to as easily as
> possible impliment random number generation in c++.

In C++? Boost:

<http://www.boost.org>

Here's an example from their docs:

#include <boost/random.hpp>

boost::mt19937 rng; // produces randomness out of thin air
// see pseudo-random number generators

boost::uniform_int<> six(1,6) // distribution that maps to 1..6
// see random number distributions

boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
die(rng, six); // glues randomness with mapping

int x = die(); // simulate rolling a die

One minor oddity about the Boost RNG approach is that there are two parts you
have to deal with - a generator and a distribution. You can choose one of each
to produce exactly the kind of RNG you want.

There are many generators - The above uses Marsenne Twister, there are also
Lagged Fibonacci, Linear Congruential, and a bunch of others with names only
a math guru could understand. ;-)

There are many distributions too. The above Uniform Integer returns a non-
weighted distribution over a range of integers. There are distributions that
simulate a coin flip, points on a sphere, etc.

sherm--

--
Cocoa programming in Perl: http://camelbones.sourceforge.net
Hire me! My resume: http://www.dot-app.org

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At 14 Sep 2005 08:06:37 -0700,
Catyalyst wrote:

> Hi im kinda getting back into the c++ scene after about a 3 year period
> away from it and would appreciate some input on how to as easily as
> possible impliment random number generation in c++. Please note i
> havent coded in a long period of time and may need to have things
> explained in a almost Dr. Suess way.

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html


Note that you can't possibly write a random number generator without
using some kind of hardware source of entropy... The best you can do
is to make a pseudorandom number generator


--
Radomir `The Sheep' Dopieralski @**@_
(Oo) 3 Eh?
. . . ..v.vVvVVvVvv.v.. .

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

"Catyalyst" <catalyst5505@gmail.com> wrote:
>Hi im kinda getting back into the c++ scene after about a 3 year period
>away from it and would appreciate some input on how to as easily as
>possible impliment random number generation in c++. Please note i
>havent coded in a long period of time and may need to have things
>explained in a almost Dr. Suess way.

Many people in rgrd seem to advocate the Mersenne Twister, a remarkably
fast and potent RNG. I decided the code was too bulky for me to be
comfortable with, so I'm using the code that you can see as "rng.c" in
the Dungeon Bash source code, which I cribbed from an archived Usenet
post someone pointed to in rgrd a while back. It seems to provide Good
Enough results, and has quite a simple algorithm.

"main.c" in the Dungeon Bash source code has a few basic wrappers for
the RNG functions.
--
Martin Read - my opinions are my own. share them if you wish.
\_\/_/ http://www.chiark.greenend.org.uk/~mpread/dungeonbash/
\ / the sweeney's doing ninety cos they've got the word to go they've got a
\/ bunch of villains in a shed up at Heathrow -- Squeeze, "Cool For Cats"

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

hey thanks every one i really apprecaite all the help you all gave me
^_^ ive downloaded the boost libraries and might try to incorporate the
RNG there as i dont plan to get overly complicated to begin with, its
been forever since ive used the language just need to get my feet wet
again.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

> Please note I haven't coded in a long period of time and may
> need to have things explained in a almost Dr. Suess way.

In the town of C you can learn many things,
New ways to make numbers and new ways to make pings.

Random numbers are not very computational.
You need specialized hardware for that.

Try a routine like Linear Congruential.
It's like pulling a rabbit out of your hat.

Some are quite simple and others most sinister.
Lagged Fibonacci? Perhaps Marsenne Twister?

There are many pseudo random number routines in the land.
Many of them with names only a math guru could understand.

While you're searching for the code that will work,
be careful what you wish for, since you might find a jerk.
--
TAZ (Yeah, it's a slow day at work.)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Martin Read wrote:
> comfortable with, so I'm using the code that you can see as "rng.c" in
> the Dungeon Bash source code, which I cribbed from an archived Usenet
> post someone pointed to in rgrd a while back. It seems to provide Good
> Enough results, and has quite a simple algorithm.

I might check out that.. I'm using rand() at the moment. Some
people say it's bad, but I can't figure out why

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Krice wrote:
> Martin Read wrote:
> > comfortable with, so I'm using the code that you can see as "rng.c" in
> > the Dungeon Bash source code, which I cribbed from an archived Usenet
> > post someone pointed to in rgrd a while back. It seems to provide Good
> > Enough results, and has quite a simple algorithm.
>
> I might check out that.. I'm using rand() at the moment. Some
> people say it's bad, but I can't figure out why

On MSVC, RAND_MAX is 32768.

I shouldn't need to say more.

I was using rand() on the theory that "surely every compiler vendor
would have got this right by now" but the Windows version of POWDER had
*very* unusual item distributions until I threw it out. I was
foolishly assuming that RAND_MAX would be INT_MAX. Rather than change
that assumption, I threw out rand().
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

On 14 Sep 2005 08:06:37 -0700, "Catyalyst" <catalyst5505@gmail.com>
wrote:

>Hi im kinda getting back into the c++ scene after about a 3 year period
>away from it and would appreciate some input on how to as easily as
>possible impliment random number generation in c++. Please note i
>havent coded in a long period of time and may need to have things
>explained in a almost Dr. Suess way.

i use a MAQR model, so the only state I need is a 32bit signed
integer... and its implemented in about 10 lines of code.



- Stu : Email via http://public.xdi.org/=stu

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Jeff Lait wrote:
> On MSVC, RAND_MAX is 32768.
> I shouldn't need to say more.

Well, I don't know what that means

> *very* unusual item distributions until I threw it out.

Isn't that good, when random is unusual and doesn't show any
repeating behaviour?

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Soo much math my mind is hurting *frowns*

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Krice wrote:
> Jeff Lait wrote:
> > On MSVC, RAND_MAX is 32768.
> > I shouldn't need to say more.
>
> Well, I don't know what that means

Lets say you are lazy and use % to get your random values.

// Returns a value from [0...n), handling negative n
// and n == 0 so you don't crash with division by
// zero.
int
rand_choice(int n)
{
if (n < 0)
return -rand_choice(-n);
if (n <= 1)
return 0;
return rand() % n;
}

Then you do something crazy like:

if (rand_choice(100000) > 50000)
{
Do special thing
}

If RAND_MAX is 32767, rand_choice can never return a value higher than
32767, and that special thing will never be done.

I ran into this because I was building a cumalative probability table
to select from with the average weighting being 100*100, or 10,000.

> > *very* unusual item distributions until I threw it out.
>
> Isn't that good, when random is unusual and doesn't show any
> repeating behaviour?

Not when out of the hundred possible items, only ten ever get
generated.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Jeff Lait wrote:
> Then you do something crazy like:
> if (rand_choice(100000) > 50000)
> {
> Do special thing
> }

Can't you change that to (rand_choice(100)>50).

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Krice wrote:
> Jeff Lait wrote:
> > Then you do something crazy like:
> > if (rand_choice(100000) > 50000)
> > {
> > Do special thing
> > }
>
> Can't you change that to (rand_choice(100)>50).

No you cannot.

The test I wrote will pass for numbers 50,001 to 99,999. It will fail
for numbers 0 to 50,000. The probability of passing is thus 49,999 in
100,000. That probability is not the same as your example, which is 49
in 100.

49% != 49.999%. Your attack on a mere technicality has failed. Do not
pass go and do not collect 200 pedant points. :>
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

"Krice" <paulkp@mbnet.fi> writes:
> Jeff Lait wrote:
> > On MSVC, RAND_MAX is 32768.
> > I shouldn't need to say more.
>
> Well, I don't know what that means

If you call rand() you get a number between 0 and RAND_MAX (or
RAND_MAX-1, perhaps).

Most of the time, RAND_MAX is 2**31 (ish).

Effects of this:
Any chance below 1/32768 will either map to 0 or 1/32768, depending on
the precise algorithm. This could end up quite skewed.

Because rand() is cyclic and deterministic, your cycle time is only
32768. This can cause problems when doing sequential random
numbers. For example, say a humanoid creature has a 0.1% chance of being
generated with a random wand that it knows how to use.
There will be ~32 numbers that rand() could have produced that would
do that. Say that it then selects the wand type from 1d100 on this list:
1-10: light
11-20: darkness
....etc...
97: death ray
98: earthquakes
99: disintegration
100: ultimate doom

There are only ~32 numbers that could have led to the wand being
created. Since each of those numbers has a definite successor, there
are therefore only 32 possible outcomes of the d100 roll that can
actually happen (and the birthday paradox suggests that some of these
will be the same, which makes it even worse).

So it might be impossible to get a monster generated holding a wand of
earthquakes, or it might be a 3% chance rather than a 1% chance that
the wand is of ultimate doom, or other oddities.

So you'll get very odd situations occuring, possibly in a way that's
very bad for game balance, that never occurred when you compiled
against a better RNG.

There was a thread on rgrm not long back mentioning similar problems
with RAND_MAX on minGW being 32767.

--
Chris

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Chris Morris <c.i.morris@durham.ac.uk> wrote:
>Because rand() is cyclic and deterministic, your cycle time is only
>32768.

The C standard does not, as far as I know, stipulate any relationship
between rand()'s period and the size of RAND_MAX.

For example, in glibc, rand() points to an implementation of
Berkeley random(), which has a limit of (2^31 - 1) and a period of
16*((2^31)-1).
--
Martin Read - my opinions are my own. share them if you wish.
\_\/_/ http://www.chiark.greenend.org.uk/~mpread/dungeonbash/
\ / the sweeney's doing ninety cos they've got the word to go they've got a
\/ bunch of villains in a shed up at Heathrow -- Squeeze, "Cool For Cats"

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Chris Morris wrote:

> "Krice" <paulkp@mbnet.fi> writes:
>> Jeff Lait wrote:
>> > On MSVC, RAND_MAX is 32768.
>> > I shouldn't need to say more.
>>
>> Well, I don't know what that means
>
> If you call rand() you get a number between 0 and RAND_MAX (or
> RAND_MAX-1, perhaps).
>
> Most of the time, RAND_MAX is 2**31 (ish).
>
> Effects of this:
> Any chance below 1/32768 will either map to 0 or 1/32768, depending on
> the precise algorithm. This could end up quite skewed.
>
> Because rand() is cyclic and deterministic, your cycle time is only
> 32768.

Wrong. The cycle period is determined by the size of the internal state of
the RNG, not by the number of different possible results.

Of course, it doesn't mean it has to be different either. In that particular
case, maybe it is the same.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <87vf11cmnn.fsf@dinopsis.dur.ac.uk>, c.i.morris@durham.ac.uk
says...
> "Krice" <paulkp@mbnet.fi> writes:
> > Jeff Lait wrote:
> > > On MSVC, RAND_MAX is 32768.
> > > I shouldn't need to say more.

Nothing wrong with that, IMO.

> > Well, I don't know what that means
>
> If you call rand() you get a number between 0 and RAND_MAX (or
> RAND_MAX-1, perhaps).
>
> Most of the time, RAND_MAX is 2**31 (ish).
>
> Effects of this:
> Any chance below 1/32768 will either map to 0 or 1/32768, depending on
> the precise algorithm. This could end up quite skewed.

There are easy ways to avoid this.

> Because rand() is cyclic and deterministic, your cycle time is only
> 32768.

This isn't the case - MSVC uses a 32-bit internal seed. The reason it
returns a value from 0 to 32767 is that it returns only the 15 middle
bits of this seed. This is *good*. If it returned the complete seed
you would get artefacts such as numbers being alternately odd and even
etc.

In fact rand() is not bad for general use, though if you seed with the
system time you should call it a couple of times before using it.
However, for a roguelike it would indeed be preferable to use something
more sophisticated. For most games, you could happily stick with
MSVC's version of rand().

- Gerry Quinn

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Gerry Quinn <gerryq@deletethisindigo.ie> schrieb:

> This isn't the case - MSVC uses a 32-bit internal seed. The reason it
> returns a value from 0 to 32767 is that it returns only the 15 middle
> bits of this seed. This is *good*. If it returned the complete seed
> you would get artefacts such as numbers being alternately odd and even
> etc.

> In fact rand() is not bad for general use, though if you seed with the
> system time you should call it a couple of times before using it.
> However, for a roguelike it would indeed be preferable to use
> something more sophisticated. For most games, you could happily stick
> with MSVC's version of rand().

These statements completely ignore all of the problems that result from
using bad random number generators.

--
Jim Strathmeyer

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <o5ydnR_ZPvv-xLHeRVn-oQ@adelphia.com>,
strathWHATEVERIGETENOUGHSPAMANYWAYS@ipass.net says...
> Gerry Quinn <gerryq@deletethisindigo.ie> schrieb:
>
> > This isn't the case - MSVC uses a 32-bit internal seed. The reason it
> > returns a value from 0 to 32767 is that it returns only the 15 middle
> > bits of this seed. This is *good*. If it returned the complete seed
> > you would get artefacts such as numbers being alternately odd and even
> > etc.
>
> > In fact rand() is not bad for general use, though if you seed with the
> > system time you should call it a couple of times before using it.
> > However, for a roguelike it would indeed be preferable to use
> > something more sophisticated. For most games, you could happily stick
> > with MSVC's version of rand().
>
> These statements completely ignore all of the problems that result from
> using bad random number generators.

Because for many games, they can be ignored.

- Gerry Quinn

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Gerry Quinn <gerryq@deletethisindigo.ie> schrieb:
> In article <o5ydnR_ZPvv-xLHeRVn-oQ@adelphia.com>,
> strathWHATEVERIGETENOUGHSPAMANYWAYS@ipass.net says...
>> These statements completely ignore all of the problems that result
>> from using bad random number generators.

> Because for many games, they can be ignored.

Uh... which games?

--
Jim Strathmeyer

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Jim Strathmeyer wrote:
> Gerry Quinn <gerryq@deletethisindigo.ie> schrieb:
> > In article <o5ydnR_ZPvv-xLHeRVn-oQ@adelphia.com>,
> > strathWHATEVERIGETENOUGHSPAMANYWAYS@ipass.net says...
> >> These statements completely ignore all of the problems that result
> >> from using bad random number generators.
>
> > Because for many games, they can be ignored.
>
> Uh... which games?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
int guess;

srand(time());

printf("Guess a number from 1-10!\n");
scanf("%d", guess);

if (guess == (rand() % 10))
{
printf("You guessed right!\n");
return 1;
}
printf("Too bad, better luck next time.\n");
return 0;
}

(Before the pedants attack: no, I have not tried to compile this)
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <IPCdnaEMWfKlMrDeRVn-jQ@adelphia.com>,
strathWHATEVERIGETENOUGHSPAMANYWAYS@ipass.net says...
> Gerry Quinn <gerryq@deletethisindigo.ie> schrieb:
> > In article <o5ydnR_ZPvv-xLHeRVn-oQ@adelphia.com>,
> > strathWHATEVERIGETENOUGHSPAMANYWAYS@ipass.net says...
> >> These statements completely ignore all of the problems that result
> >> from using bad random number generators.
>
> > Because for many games, they can be ignored.
>
> Uh... which games?

Most games don't require sophisticated RNGs.

If you just have standard play areas, or not-too-complex random ones,
and certain enemies and/or objects appear at somewhat random times,
none being grossly uncommon, rand() will probably do fine.

And the above covers a LOT of computer games. Lines, Tetris, Space
Invaders derivatives, etc.

- Gerry Quinn

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At Mon, 19 Sep 2005 13:10:59 +0100,
Gerry Quinn wrote:

> In article <IPCdnaEMWfKlMrDeRVn-jQ@adelphia.com>,
> strathWHATEVERIGETENOUGHSPAMANYWAYS@ipass.net says...
>> Gerry Quinn <gerryq@deletethisindigo.ie> schrieb:
>> > In article <o5ydnR_ZPvv-xLHeRVn-oQ@adelphia.com>,
>> > strathWHATEVERIGETENOUGHSPAMANYWAYS@ipass.net says...
>> >> These statements completely ignore all of the problems that result
>> >> from using bad random number generators.
>>
>> > Because for many games, they can be ignored.
>>
>> Uh... which games?
>
> Most games don't require sophisticated RNGs.
>
> If you just have standard play areas, or not-too-complex random ones,
> and certain enemies and/or objects appear at somewhat random times,
> none being grossly uncommon, rand() will probably do fine.
>
> And the above covers a LOT of computer games. Lines, Tetris, Space
> Invaders derivatives, etc.

What this newsgroup is about, again?

--
Radomir `The Sheep' Dopieralski @**@_
($s) 3 Ching!
. . . ..v.vVvVVvVvv.v.. .