[Wesnoth-wiki-changes] PseudoRandomNumberGeneration

[wiki]

UserAgent: Mozilla/5.0 (Macintosh; U; PPC Mac OS X; en) AppleWebKit/125.4 
(KHTML, like Gecko) Safari/125.9
IP: 66.189.14.56
URI: http://wesnoth.slack.it/?PseudoRandomNumberGeneration
 - - - - -
 Elvish Pillager: I have finished my work on the Pseudorandom Number 
Generation! It's done! I found a lot of bugs on the way...
 I think I'll wait until the site is back up to go in depth.

 Also, I noticed that a Grand Knight with Holy Water led by a Grand Marshal 
during the day can kill a Skeletal Dragon in one hit, something that Túrin
 might want to do something about. (It's easy to slaughter the Skeletal Dragon 
without being attacked by the other undead.)
.
 Shadowfury333: What exactly is this for?

 BTW don't forget to make new topics. (Just type the name without spaces, 
instead use Capital letters to signify the first letter in each word)
.
 MadMax: Can you email me the code at address@hidden I'm interested to see how 
it's done.

 With the Grand Knight and the Marshal, turin can put some skeletons around it.

 "ILLLEGITIMUS NON CARBORUNDUM"
.
 Elvish Pillager: No need to bother with email, since this is a wiki. Behold:

 
################################################################################################
 ################Pseudo-Random Number Generation Engine For 
Multiplayer##########################
 
################################################################################################

 #Don't use this, it's for internal use by other macros
 #define GETNEXTNUMBER

 #multiplying xrand by 421
 {VARIABLE i 0}
 {VARIABLE_OP temp_factor to_variable xrand}
 [while]
 [variable]
 name=i
 less_than=420
 [/variable]
 [do]
 {VARIABLE_OP xrand add $temp_factor}
 {VARIABLE_OP i add 1}
 [/do]
 [/while]

 {VARIABLE_OP xrand add 2311}
 [while]
 [variable]
 name=xrand
 greater_than=32767
 [/variable]
 [do]
 {VARIABLE_OP xrand add -32768}
 [/do]
 [/while]
 #enddef

 [event]
 name=turn 2
        {VARIABLE xrand 0}
        [store_unit]
        [filter]
        [/filter]
        variable=units
        [/store_unit]
        {FOREACH units i}
                {VARIABLE_OP temp to_variable units[i].hitpoints}
                {VARIABLE_OP xrand add $temp}
        {NEXT i}
 {GETNEXTNUMBER}
 {GETNEXTNUMBER}
 {GETNEXTNUMBER}
 {GETNEXTNUMBER}
 {GETNEXTNUMBER}
 {GETNEXTNUMBER}
        {CLEAR_VARIABLE temp}
        {CLEAR_VARIABLE units}
 [/event]

 #Instead of {RANDOM 0..155}, use {PSEUDORANDOM 156}. This is the only way to 
use it.
 #You can use {VARIABLE_OP random add X} afterwards to get a higher range.
 #define PSEUDORANDOM NUMBER
 {GETNEXTNUMBER}
 {VARIABLE_OP random to_variable xrand}

 {VARIABLE_OP temp format ({NUMBER})}
 [if]
 [variable]
 name=temp
 less_than=33
 [/variable]
        [then]
        #making temp equal {NUMBER}x1024
        {VARIABLE i 0}
        {VARIABLE temp 0}
        [while]
        [variable]
        name=i
        less_than={NUMBER}
        [/variable]
        [do]
        {VARIABLE_OP temp add 1024}
        {VARIABLE_OP i add 1}
        [/do]
        [/while]
        
        {VARIABLE_OP temp2 to_variable temp}
        {VARIABLE_OP temp2 multiply -1}
        [while]
                [variable]
                name=temp
                less_than=$random
                [/variable]
                        [do]
                        {VARIABLE_OP random add $temp2}
                        [/do]
        [/while]
        [/then]
 [/if]

 [while]
 [or]
 [variable]
 name=random
 greater_than={NUMBER}
 [/variable]
 [/or]
 [or]
 [variable]
 name=random
 equals={NUMBER}
 [/variable]
 [/or]
 [do]
 {VARIABLE_OP random add -{NUMBER}}
 [/do]
 [/while]
 #enddef

 -----
 (It's been quite a bit of space and time, but this is still EP)
 The Story (It isn't told in order or completely, but it's still the story.)

 I got my pseudorandom number generation (to be referred to as PRNG) formula 
from a book by Knuth. It is as follows:
 Xn+1=(aXn + c) mod m
 That was difficult to do in code. I don't have multiplication[1] OR modulus in 
my arsenal, so I had to imitate them using while loops.
 Then, I had to choose good values for a, c, and m. Since the 'random' sequence 
always loops eventually, the duration of the loop is called the period In
 order to have a period of length m, the maximum, the numbers had to fill 
several conditions.
 That wasn't hard, but the numbers were at first way too small. I increased 
them. They did not fulfill my worries that the the process would be too slow,
 fortunately, though it's much MUCH slower than doing these operations in a 
standalone C application or whatever. Something like that could go through
 all 32768 possible values in less than a second.
 Anyway, I at first made the mistake of extracting values by regenerating the 
randomseed until it was below the requested value. (that was incredibly
 stupid. It means that there are only so many possible values, thus it wrecks 
the randomseed.) After that I used modulus extraction, which is still not the
 best, but at least it works.
 At one point, I ran across a strange problem: Generating pairs of values, I 
kept getting the same pairs! There was something wrong with my PRNG. It turns
 out that each number easily predicts the next number, until it hits the 
modulus. Therefore, I increased a and c so that it hit the modulus almost every 
time,
 while still conforming to the required conditions.
 Another problem was more frustrating but easier to solve once I found it: The 
values kept incrementing steadily instead of being random! I spent a long
 time puzzling over this before I realized that changing the multiplier wasn't 
having any effect. I investigated, and found a missing $.
 The last problem I encountered was a bug in Wesnoth. That bug is that 
variables remain in existence and retain their values between multiplayer games 
I
 circumvented this by clearing all my variables at the start of the game.

 Throughout most of this, I had a bugtester on the multiplayer server called 
Jammet. I thank you, Jammet, for your patience while I fixed incomprehensible
 bug after incomprehensible bug. Your help was very helpful.


 [1] there is also a bug in multiplication; apperently floating-point 
multiplication and subsequently casting floats to ints throws off their values 
on some
 operating systems.

||See Also||

* UserForum