ZDaemon Forum Index ZDaemon
Client/Server DOOM
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

ACS random is not random enough

 
Post new topic   Reply to topic    ZDaemon Forum Index -> Implemented Requests
View previous topic :: View next topic  
Author Message
Body-Guard
Unstoppable!


Joined: 08 Jan 2006
Location: Hungary

PostPosted: Wed Dec 10, 2014 9:41 pm    Post subject: ACS random is not random enough Reply with quote

The example wad is a rain spawner. The raindrops are spawned on random x and y coordinates inside a rectangle bounded by two mapspots (upper left corner & lower right corner).

type "puke 1" in the console to start the raining.

In zdaemon there is a large portion of the rectangle where never any raindrops are spawned.
If you test with zdoom 2, the raindrop spawning is aligned properly inside the rectangle.

http://destiny-server.no-ip.org/stuff/weather.zip
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
Sr69Mm-jC
Unstoppable!


Joined: 21 Jul 2011

PostPosted: Wed Dec 10, 2014 10:37 pm    Post subject: Reply with quote

That is not really a "bug". It's just Doom's P_Random being crap as it has always been.

Here's a fun thing for you to see.
https://dl.dropboxusercontent.com/u/68200676/weather2.wad

I increased the rain rate by 500 times and also added a deactivated Demon in the room. At first you'll see that there is a fixed set of 32 locations where the raindrops can spawn (which means very poor randomness). Now, press the switch to activate the demon. The demon is now calling P_Random too and that affects your rain (in a good way). Now if you alert the demon it starts to call P_Random more often which improves the rain randomness even further making it actually look nice now. Killing the demon would revert to the original "32 possible locations" behavior.

In a real game many things are using P_Random - having at least one monster on the map (even an inactive one) is enough. If that's not an option for you then you could make another 'background' script that simply calls Random() function (e.g. Random()%4 times every tic) - that will work although it's indeed not a clean solution.

Still, if you're not satisfied with the randomness ACS provides you could just write your own RNG. There are many possible algorithms out there and you also can conveniently use GetCVar("cv_gmtime") as a seed - that's how people have done it around here.

I'm afraid that altering the current RNG behavior will also alter the existing wads. Who knows in what kind of hacky ways modders have used the RNG? I mean, honestly, I personally can't be against improving that P_Random mess (at least for ACS) but I'm not sure if this isn't going to break and/or badly change some of the existing wads. I also wonder if ZDoom changed the whole P_Random function or only made the change for ACS. The latter is unlikely; and if it's the former then I wouldn't really expect ZDaemon to also implement a fundamental change like that.
Back to top
View user's profile Send private message
Body-Guard
Unstoppable!


Joined: 08 Jan 2006
Location: Hungary

PostPosted: Thu Dec 11, 2014 9:56 am    Post subject: Reply with quote

That is a nice showoff of random behavior Smile I don't think it is of any use to worry about compatibility, most maps/mods on zdaemon rarely use any complex ACS (or ACS at all), and if they do, I'm pretty sure they mean randomness when they use the random function. Who would rely on this exact behavior? The definition of random is to be as unpredictable as possible after all Smile And I'm pretty sure it would affect monster behavior in a good way, like for the lost soul or any standard chase movement.
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
Krawa
There is a limit


Joined: 23 Nov 2008
Location: #SDA

PostPosted: Thu Dec 11, 2014 10:20 pm    Post subject: Reply with quote

Yeah, random is tricky a bit.
Also check out Pending Requests - Improved Random for Open and Enter Scripts
There's also a workaround for Open and Enter scripts.
Back to top
View user's profile Send private message Visit poster's website
Sr69Mm-jC
Unstoppable!


Joined: 21 Jul 2011

PostPosted: Fri Dec 12, 2014 2:20 am    Post subject: Reply with quote

That's in fact a rather different problem there Krawa. Your topic is about seeding the RNG; this topic is about how RNG picks the next value. Both problems are indeed caused by how bad P_Random is though. Blame Id Smile

This is exactly how the whole so-called randomness works in doom: https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/m_random.c
DoomWikia wrote:
The file m_random.c in the Doom source code contains a static table 256 bytes long containing numbers between 0 and 255 in a fixed, scrambled order. There is an index to this table which starts at zero. Each call to the function P_Random advances the index by one (wrapping around to zero after 255) and returns the table entry at that index.
Although the table is 256 bytes long, it does not contain all of the numbers between 0 and 255 inclusive. For example, 0 appears twice and 1 does not appear at all; 145 appears five times, more than any other number. Thus the values are not uniformly distributed, but in fact they are nearly so. The mean value is 128.852, whereas it would be 127.500 if all values were equally likely. All of this suggests that the table was generated using a conventional pseudorandom number generator of reasonable quality.

It is just as primitive as it gets really. ZDaemon has somewhat improved this (see 1.06 source code) but I am quite unable to understand what's going on there without looking deeper into the code. Here's a comment though:
ZDaemonCL/src/m_random.cpp wrote:
// 1/19/98 killough: Rewrote random number generator for better randomness,
// while at the same time maintaining demo sync and backward compatibility


I am unfortunately unable to find ZDoom's RNG (aside from some multiple RNG management functions) to see what exactly they replaced P_Random with. I'll repeat myself here though.. Changing ONLY the ACS P_Random behavior is impractical (or maybe not really possible at all), and doing what ZDoom folks did (that is, getting rid of P_Random entirely and replacing it with a better RNG) would be a disaster. Even if you ignore a significantly altered monster behavior (including things like which monsters IconOfSin spawns etc), this still at very least means completely different SSG damage calculations - the deathmatch players are going to rip the ZD staff apart Smile This is basically what happened in ZDoom: http://forum.zdoom.org/viewtopic.php?f=4&t=30201 Point is, this will affect a LOT of things across all gamemodes.

Honestly though, your best shot is to go ahead and port any of C++ RNGs out there to ACS and go with it. Like I said before (and like Krawa did in his own topic), GetCVar("cv_gmtime") would probably be your choice of seed. Or, you could do it rjrandom2-style where inputting the same seed would mean generating the same layout. It's up to you and what kind of wad you're doing. Here's some code, it's not written by me and it's not even tested by me yet but maybe it's worth checking. http://pastebin.com/PraAbwyC
Back to top
View user's profile Send private message
Body-Guard
Unstoppable!


Joined: 08 Jan 2006
Location: Hungary

PostPosted: Thu Apr 02, 2015 8:34 am    Post subject: Reply with quote

Guessing from the above, ACS's Random function just calls P_Random. It would be possible to write a custom random number generator just for ACS usage (because that is what we need actually, and a new RNG solely for this purpose alongside P_Random wouldn't hurt compatibility). Then on it is just a matter of calling this RNG instead of P_Random in the ACS function Random (min,max).
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
Kilgore
Air Cavalry


Joined: 17 Jun 2003
Location: Up the river

PostPosted: Tue Apr 14, 2015 9:45 pm    Post subject: Reply with quote

This looks like a request rather than a bug; it's gonna arrive soon Smile
Back to top
View user's profile Send private message Visit poster's website
Aeyesx
Dominating!


Joined: 13 Oct 2012

PostPosted: Wed Apr 15, 2015 5:34 am    Post subject: Reply with quote

That is cool, I can say from (z)deathrun that the random pickup is not really random sometimes picking up same n same players, zedek tried some Krawa's workarounds with improving random calling using active monster etc.

+1 its great that it get improved
Back to top
View user's profile Send private message Send e-mail
Body-Guard
Unstoppable!


Joined: 08 Jan 2006
Location: Hungary

PostPosted: Wed Apr 15, 2015 9:15 am    Post subject: Reply with quote

Awesome, thanks!
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
Kilgore
Air Cavalry


Joined: 17 Jun 2003
Location: Up the river

PostPosted: Sun Aug 02, 2015 4:11 am    Post subject: Reply with quote

The upcoming release (110b04) has new pseudo-random ACS functions; those should fix the problem you describe.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    ZDaemon Forum Index -> Implemented Requests All times are GMT + 1 Hour
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group