Announcement: Why not try our official idea generator for inspiration when making puzzles?


Caravel Forum : DROD Boards : Architecture : Chomp - and how to script an RNG
New Topic New Poll Post Reply
Poster Message
Remlin
Level: Master Delver
Rank Points: 181
Registered: 04-28-2005
IP: Logged

File: Chomp.hold (6.5 KB)
Downloaded 74 times.
License: Public Domain
icon Chomp - and how to script an RNG (+3)  
I thought some architects out there might be interested in seeing this -
Now that we have wonderful variables to work with, it's easier than ever to add random-looking behavior to a hold. In fact, there's no reason we can't implement a pseudo-random number generator.

Of course nothing will ever be truly random in DROD, but it can get pretty damn close. This is an implementation of the game of Chomp, and every time you leave and reenter the main room, it generates a new starting setup for you. (Chomp is a two player game, so grab a friend and take turns controlling Beethro, or play against yourself.)

WORD OF CAUTION: Use ctrl-f7 to see how the variables are changing at your own risk. For me, that's a recipe for a DROD crash. If someone can confirm that happening in 3.1, I'll post something in the Bugs forum.

Here's how the randomness is handled: One NPC, off in the corner, is scripted as follows:
Label "Waiting"
 Wait until var RandomRequest = 1
 Set var RandomSeed * 1664525
 Set var RandomSeed + 1013904223
 If ...
   Wait until var RandomSeed < 0
  Set var RandomSeed + 2147483647
  Set var RandomSeed + 1
 If End
 Set var RandomResult = RandomSeed
 Set var RandomResult / 1024
 Set var RandomResult % RandomRange
 Set var RandomRequest = 0
 Go to "Waiting"
This guy implements the RNG, which is a standard Linear Congruential Generator. The numbers I'm using are usually meant to generate numbers across the full range of unsigned 32 bit integers, but DROD uses signed integers so I'm only generating in the 0 to 2^31 range. (Hence the addition of 2^31 in the middle.) If I understand the math, the randomness is just as strong.

Whenever any other script wants to generate a random number, let's say 0,1,...20, it does it like so:
 Set var RandomRange = 21
 Set var RandomRequest = 1
 Wait until var RandomRequest = 0
 Set var MyResult = RandomResult
MyResult then stores the needed number.

But how do we generate the initial RandomSeed value? Computers usually use some randomish physical phenomenon, like the system time in milliseconds, and you can use randomish DROD phenomenon in the same way. For example, count the total number of moves the player took in some room x. That's what Chomp does - it uses the number of moves spent in the entrance. The end result is that anyone playing your hold will probably get different seed every time they play through.

Remember kids! Use randomness for good, and not for evil.

[Last edited by Remlin at 08-21-2007 05:11 AM]
08-21-2007 at 04:15 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged
icon Re: Chomp - and how to script an RNG (+2)  
First off, I don't recognise those numbers for the LCG. Or rather, I recognise that one half of the number comes from one LCG and the other comes from another LCG, but that's *really* not recommended unless you know what you're doing - if you're going to use an LCG, use both the same multiplier and addition constant given for a single LCG.

Secondly, most LCGs throw away the least significant digits, with *very* good reason: try your current script with a RandomRange of 2. You'll see a pattern within seconds. That's because when RandomSeed is odd, multiplying it by an odd number returns an odd number, and then adding an odd number returns an even number. And when RandomSeed is even, multiplying it by an odd number return an even number, and adding an odd number return an odd number. So you'll probably want to throw away the lower 16 bits or similar before using the result.

Thirdly, the use of Modulus on a random range tends towards bad choices. It *is* quick and easy, and works fair enough when the initial range of values is very high, but it will introduce more flaws and a bias towards lower values if the RandomRange is not a factor of the full range of results. As an extremely biased result, take a random number between 0 and 32767, and try transforming it into a usuable range between 0 and 9999. If you use % 10000, you'll end up with a chance of 4/32768 per number between 0 and 2767, but only a chance of 3/32768 per number between 2768 and 9999. Ideally, the way around this is to use multiply and divide instead, but you can run the risk of overflow if both the RandomRange and the basic result range you're drawing from is too high.

Apart from all that, the concept is good, and it's a useful thing to know, but you should be aware of some of the pitfalls in using them properly. (And considering a lot of major game companies commonly make these sort of mistakes....)

EDIT: Oh, and both 3.0.0 and 3.1 are both currently crashing for me whenever I try to enter in a 10-digit number to assign to a variable, so I can't get the actual *code* itself to run, I'm afraid. Not sure what's causing that.

[Last edited by TFMurphy at 08-21-2007 04:52 AM]
08-21-2007 at 04:37 AM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Remlin
Level: Master Delver
Rank Points: 181
Registered: 04-28-2005
IP: Logged
icon Re: Chomp - and how to script an RNG (+1)  
Hey, thanks for the advice TFMurphy. You're right, I'd accidentally copied the constants from two different LCGs. Fixed now.

I also added a divide by 1024 to throw away some bits. Does that seem better? (Of course, don't try generating a random number greater than a million now.)

I'm aware that doing a straight modulus doesn't give an even distribution over the possible results, but I figured, meh. Nobody's going to be asking for a number in a range large enough for it to be noticeable.
08-21-2007 at 05:16 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged
icon Re: Chomp - and how to script an RNG (+1)  
Remlin wrote:
Hey, thanks for the advice TFMurphy. You're right, I'd accidentally copied the constants from two different LCGs. Fixed now.

<nod> I'm not sure of how *good* that particular LCG is, but it's better to go with already analyzed functions, and simply change to a different LCG if need be.

Remlin wrote:
I also added a divide by 1024 to throw away some bits. Does that seem better? (Of course, don't try generating a random number greater than a million now.)

Well, it means you need 2048 numbers now before a modulo 2 will start repeating. Of course, that isn't that bad for DROD scripting: it's more of an issue in applications that'll go through random numbers far faster.

Really, the more of the lower bits you throw away, the better - this is also why scaling is highly recommended for these types of LCGs rather than using modulus. General practice for requiring higher numbers than the range is to simply call the random number twice and apply the two numbers together correctly... but that can take a bit of juggling to do properly. It's probably best to leave that up to whoever uses the script... although I'd hope they wouldn't need a full random range up to a million.

Remlin wrote:
I'm aware that doing a straight modulus doesn't give an even distribution over the possible results, but I figured, meh. Nobody's going to be asking for a number in a range large enough for it to be noticeable.

I've always found it's best to be cautious and mention these things. And given that I've seen all three of these problems in published commercial games, I believed it well worth mentioning. (I'm happy to see that DROD seems to sidestep these... well, except for possibly the Mac version from what I see of the code, but that's just modulus issue and I don't know the range on the generator it's using there)
08-21-2007 at 05:28 AM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
mrimer
Level: Legendary Smitemaster
Avatar
Rank Points: 5147
Registered: 02-04-2003
IP: Logged
icon Re: Chomp - and how to script an RNG (0)  
Hey, neat! I don't think we'll ever see a roll random number script command in DROD, but this helps to do the job in its place.

____________________________
Gandalf? Yes... That's what they used to call me.
Gandalf the Grey. That was my name.
I am Gandalf the White.
And I come back to you now at the turn of the tide.
08-21-2007 at 05:19 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
RoboBob3000
Level: Smitemaster
Avatar
Rank Points: 1980
Registered: 10-23-2003
IP: Logged
icon Re: Chomp - and how to script an RNG (0)  
As long as nobody makes a high-scorable room with this, this is an excellent addition to an architect's arsenal!

____________________________
http://beepsandbloops.wordpress.com/
08-22-2007 at 03:41 AM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Timo006
Level: Smitemaster
Avatar
Rank Points: 526
Registered: 07-19-2006
IP: Logged
icon Re: Chomp - and how to script an RNG (0)  
Another way which uses small numbers:


Set Var Original = 202
Label: "1"
Set Var TempA = Original
Set Var TempA / 11
Set Var Original % 11 (use this as the random number)
Wait for ...
Set Var Original * 100
Set Var Original + TempA
go to "1"

in this example, the random number cannot go higher than 10.

Also, You can change the original number and the number you use to divide.

____________________________
Drod Number: 3034; 8th person to see the Second Sky
08-22-2007 at 04:42 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged
icon Re: Chomp - and how to script an RNG (+2)  
You do realise that making any PRNG is a lot harder than just picking any old numbers to add, divide and multiply by, right?

In this case, the numbers you picked create a period of 39: which means it only takes 39 numbers before the whole thing repeats. On top of that, there's a clear bias to certain numbers: 0, 2 and 8 all have over twice the chance of being picked than 1 or 5. And finally, 0 to 10 is a range of 11 numbers, which isn't a particularly helpful range: it can't be easily converted to make a percentage chance work or to any of the normal dice throws that architects are more familiar with.

I'm not going to formally analyse the sequence further than that (it takes more than just a roughly equal distribution of numbers to make even a halfway decent generator), but you do need to know what you're doing before just creating any old equation and hope it'll spit out usable random numbers.
08-22-2007 at 04:57 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Rabscuttle
Level: Smitemaster
Avatar
Rank Points: 2502
Registered: 09-10-2004
IP: Logged
icon Re: Chomp - and how to script an RNG (+1)  
08-23-2007 at 03:53 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : DROD Boards : Architecture : Chomp - and how to script an RNG
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.