Search In
• More options...
Find results that contain...
Find results in...

# Pseudorandom #'s

## Recommended Posts

Most of the attacks and weapons in DOOM use random numbers to determine what kind of damage they do; for example zombie bullets do one to five times three damage points (dp). I've heard that the system to determine the damage multiplier is a pseudorandom number generator. Now, I'm not into programming and such, so my request to somebody with the knowledge is: could you please explain this system to me in laymen's terms?

I know (or think) that this system makes it impossible to do the same amount of damage many times in a row, for example, and that it prevents demo's from getting out of sync as a result of (true) random damage.

I want to understand this so I can take it into account when DOOMing. Thanks for the help.

This should be of help.

The "dp" are commonly called "hp", or hit points (of damage, in this case).

Oh yeah, I forgot about the DOOM Wiki.

So m_random.c is a list of random numbers between 0 and 255, and each time a random numbers is need, the game looks up the next number on that list.
Let's say a zombie bullet is fired. The game needs to know what multiplier to give (1 to 5), so it looks up m_random.c and finds the number 87 for example. How does it go from there? I'd think 0-50 means a multiplier of 1; 51-102 is a multiplier of 2 etc. In this case, the multiplier would be 2.

Am I correct?

The DOOM Wiki says:
The function M_ClearRandom resets both functions' indexes to zero. It is called during initialization of each new level so that demos will be the same each time they are played, and so that multiplayer games are synchronised.

This would mean that each level's first bullet (or any first attack) does the same damage. I've never noticed this before...

Yeah, I started wondering exactly how the random number is transformed into the required range after I linked that. That should be there in the wiki, as people will naturally wonder how it is. I'm guessing its proportional to the range and then rounded off according to some defined means. Half a point is rounded down, maybe? The Pistol is more likely to inflict 5 than 15 points of damage.

The predictability has been used for some short speed runs where the player knew a monster would turn a certain way if he did something consistently. I remember Sedlo talking about this in regard to some of his records, saying an Imp would almost always step a certain way, or stuff like that.

Here is how the damage multiplier is computed in procedure P_Gunshot in p_pspr.c:

damage = 5*(P_Random ()%3+1)

Also, after that TWO calls to P_Random are used to determine the hitting angle:

if (!accurate)angle += (P_Random()-P_Random())<<18;

The shotgun is implemented as 7 calls to P_Gunshot, and actually uses 21 random values, and only every two of them are used as damage multipliers.

The Super Shotgun has its own code, for some reason:

for (i=0 ; i<20 ; i++)
{
damage = 5*(P_Random ()%3+1);
angle = player->mo->angle;
angle += (P_Random()-P_Random())<<19;
P_LineAttack (player->mo,
angle,
MISSILERANGE,
bulletslope + ((P_Random()-P_Random())<<5), damage);
}

It actually uses 5 calls to P_Random() for each pellet, and introduces a lot of random vertical slope as well, which makes for a whooping 200 calls to P_Random() each time you shoot, nearly draining the random table !!!

I don't know if the statistics shown on the wiki were made in order to account for those extra usages of P_Random() (e.g. it may be actually impossible to get a row of seven 3x damage multipliers for a shotgun blast, and even more impossible to get twenty 3x multipliers for a SSG a super shotgun blast, but this can be checked).

Source ports with an enhanced (aka more refined) random system can still sync their own demos, because everything is still 100% deterministic.

I see, there are more things that require random numbers than just attacks, which explains why the first shot isn't necessarily the same every time.

If all monster movements use m_random.c, it would be very hard to keep track of how much damage the next fireball will do, but I'll bet there are people who can do it to a certain length. If you can predict each fireball's damage, you're truly a DOOM god!

@ Maes: Does it calculate the damage and angle for each pellet subsequently, or does it calculate 7 damage multiplier and then 7 angles?

Actually there are two separate random indexes to the same table, which can be called through M_Random() and P_Random. Some things use only M_Random, while others like the player attacks use only P_Random, so there's absolutely no chance of e.g. a monster moving while the player is shooting to change the outcome of his shot.

Also, Doom is traditionally "single threaded", so even if some event used the same P_Random() function "at the same time" with player events, it would actually have to be queued after said player event (e.g. shooting), so again, there's no chance of "stealing" or "skipping" certain sequences random values: when you shoot a SSG, 200 calls to P_Random() are made, and even is there are calls to P_Random outside the SSG function, the SSG function will ALWAYS use them in batches of 5, the SG in batches of 3, etc., with no exception.

Again, I don't know if the wiki damage tables were made by taking this into account: e.g. is there any reasonably possible sequence of batches of 3 random values actually giving you a 3x multiplier for 7 or 20 consecutive times (excluding the trivial case of wrapping around the whole table and ending up on the same random index each time the next pellet must be computed).

@Terra-jin: each time a shotgun or "inaccurate" pistol/CG pellet is fired, 3 CONSECUTIVE P_Random() values are used, and that cannot be disrupted by external calls. It computes first the damage (1 value), then the angle (2 values) and only THEN can any calls to external functions happen. The SSG uses two extra values for the vertical angle, as well (slope). So computation for a shotgun blast goes in the order:

7x ({DAMAGE, ANGLE,ANGLE}, EXTERNAL CALLS)

Notice that "External calls" means uses of the P_Random() function outside the "Shotgun function, and can be any random number of calls. What's important, is that each pellet always uses 3 consecutive values without being disrupted (that's why I enclosed 3 values into {} brackets). The whole thing is then repeated 7 times. The SSG is very similar.

If you prefer a more IT term, the computation of angle and damage for each pellet is "atomic", e.g., cannot be disrupted by external events. The SG or SSG shot as a whole is not atomic, however.

From what I read it seems that M_Random is for things that are not critical to synching the Players in MultiPlayer, such as the status bar face, when determining what way it looks when idle. If it's internally functional, P_Random is used, and if cosmetic (though perhaps functional to the user as input), M_Random.

myk said:

From what I read it seems that M_Random is for things that are not critical to synching the Players in MultiPlayer, such as the status bar face, when determining what way it looks when idle. If it's internally functional, P_Random is used, and if cosmetic (though perhaps functional to the user as input), M_Random.

This is correct. M_Random is only used for a few specific things that don't affect the game sync: ie. the screen melt effect, the status bar face animation and the intermission screen animations.

I always wondered why demos wouldn't go out of sync even though there are obviously lots of things being randomly determined.

BTW the '%' operator in C means "modulus". Modulus is an operator that returns the remainder in an integer division operation. For example, 3 divided by 2 == 1 remainder 1, so 3 mod 2 == 1. The result of a modulus operation will always be a number between 0 inclusive and the divisor exclusive (so in other words, X mod 2 returns Y such that 0 <= Y < 2).

You can thus use modulus to clamp a value into a given range :)

Now if a source port were to generate random number tables with certain seed values, all that would be needed to synchronize would be to send the seed value.

I don't know if the statistics shown on the wiki were made in order to account for those extra usages of P_Random()

No, they weren't, but that can be fixed.

If all monster movements use m_random.c, it would be very hard to keep track of how much damage the next fireball will do

Right. This is the main inaccuracy in the wiki's histograms, and it can't really be corrected because it depends sensitively on how many other monsters are awake.

so it looks up m_random.c and finds the number 87 for example. How does it go from there?

I think *all* attack damage calculations use the low bits (the wiki article doesn't discuss this yet), so 5 * ((87 % 3) + 1) = 5.

Maes said:

The shotgun is implemented as 7 calls to P_Gunshot, and actually uses 21 random values, and only every two of them are used as damage multipliers.

So a shotgun is functionally just 7 pistol / chaingun bullets fired simultaneously? I guess I never knew that. I mean, I knew a shotgun "pellet" had the same damage as a bullet, but I didn't know they were created in literally the same manner.

The Super Shotgun has its own code, for some reason:

Well the above explains it, P_Gunshot is a very specific kind of bullet. You can see they bitshifted by 19 for the spread of the SSG as opposed to the 18 for the P_Gunshot, which I guess means the SSG has twice the spread of a regular shot.

Re: calls to P_Random not being consecutive for, say, the SSG - I can understand that any shots that connect result in a call to the monster's pain chance, but other than that, what else could possibly wedge itself into that tiny bit of time between loops through the for()?

Linguica said:

Re: calls to P_Random not being consecutive for, say, the SSG - I can understand that any shots that connect result in a call to the monster's pain chance, but other than that, what else could possibly wedge itself into that tiny bit of time between loops through the for()?

Each spawned bullet puff and blood drop uses three P_Random() calls.

The result of all these things is that actual damage calculations are very hard: even if the weapons themselves have a fairly predictable use of the P_Random() function, what happens after a pellet connects or misses plays a major role: e.g. each rocket in flight "consumes" a P_Random() call each tick to create a smoke puff, monsters may counter-attack etc. so the random tables on the wiki are rendered pretty much useless.

An "accurate" damage computation for each kind of weapon would require to compute all possible permutations/combinations of the table's values taking into account the e.g. 3-batch and 5-batch usage pattern of the SG and SSG. In other words, to account for ALL possible permutations or combinations (WITH REPETITION) of batches of consecutive calls starting at any random point of the table.

Any takers? :-p

```g_game.c(909):		 i = P_Random() % selections;
m_random.c(58):		 int P_Random (void)
m_random.h(37):		 int P_Random (void);
p_enemy.c(253):		 if (P_Random () < dist)
p_enemy.c(357):		 actor->movecount = P_Random()&15;
p_enemy.c(409):		 if (P_Random() > 200
p_enemy.c(451):		 if (P_Random()&1)
p_enemy.c(641):		 sound = sfx_posit1+P_Random()%3;
p_enemy.c(646):		 sound = sfx_bgsit1+P_Random()%2;
p_enemy.c(773):		 && P_Random () < 3)
p_enemy.c(796):		 actor->angle += (P_Random()-P_Random())<<21;
p_enemy.c(817):		 angle += (P_Random()-P_Random())<<20;
p_enemy.c(818):		 damage = ((P_Random()%5)+1)*3;
p_enemy.c(840):		 angle = bangle + ((P_Random()-P_Random())<<20);
p_enemy.c(841):		 damage = ((P_Random()%5)+1)*3;
p_enemy.c(861):		 angle = bangle + ((P_Random()-P_Random())<<20);
p_enemy.c(862):		 damage = ((P_Random()%5)+1)*3;
p_enemy.c(871):		 if (P_Random () < 40)
p_enemy.c(888):		 if (P_Random () < 10)
p_enemy.c(925):		 damage = (P_Random()%8+1)*3;
p_enemy.c(946):		 damage = ((P_Random()%10)+1)*4;
p_enemy.c(961):		 damage = (P_Random()%6+1)*10;
p_enemy.c(990):		 damage = (P_Random()%8+1)*10;
p_enemy.c(1041):	 th->tics -= P_Random()&3;
p_enemy.c(1113):	 damage = ((P_Random()%10)+1)*6;
p_enemy.c(1548):	 sound = sfx_podth1 + P_Random ()%3;
p_enemy.c(1553):	 sound = sfx_bgdth1 + P_Random ()%2;
p_enemy.c(1860):	 z = 128 + P_Random()*2*FRACUNIT;
p_enemy.c(1862):	 th->momz = P_Random()*512;
p_enemy.c(1866):	 th->tics -= P_Random()&7;
p_enemy.c(1883):	 x = mo->x + (P_Random () - P_Random ())*2048;
p_enemy.c(1885):	 z = 128 + P_Random()*2*FRACUNIT;
p_enemy.c(1887):	 th->momz = P_Random()*512;
p_enemy.c(1891):	 th->tics -= P_Random()&7;
p_enemy.c(1955):	 r = P_Random ();
p_inter.c(727):		 target->tics -= P_Random()&3;
p_inter.c(824):		 && (P_Random ()&1) )
p_inter.c(895):		 if ( (P_Random () < target->info->painchance)
p_lights.c(54):		 amount = (P_Random()&3)*16;
p_lights.c(107):	 flash->count = (P_Random()&flash->mintime)+1;
p_lights.c(112):	 flash->count = (P_Random()&flash->maxtime)+1;
p_lights.c(143):	 flash->count = (P_Random()&flash->maxtime)+1;
p_lights.c(207):	 flash->count = (P_Random()&7)+1;
p_map.c(278):		 damage = ((P_Random()%8)+1)*tmthing->info->damage;
p_map.c(324):		 damage = ((P_Random()%8)+1)*tmthing->info->damage;
p_map.c(1308):		 mo->momx = (P_Random() - P_Random ())<<12;
p_map.c(1309):		 mo->momy = (P_Random() - P_Random ())<<12;
p_mobj.c(97):		 mo->tics -= P_Random()&3;
p_mobj.c(468):		 if (P_Random () > 4)
p_mobj.c(507):		 mobj->lastlook = P_Random () % MAXPLAYERS;
p_mobj.c(789):		 mobj->tics = 1 + (P_Random () % mobj->tics);
p_mobj.c(820):		 z += ((P_Random()-P_Random())<<10);
p_mobj.c(824):		 th->tics -= P_Random()&3;
p_mobj.c(848):		 z += ((P_Random()-P_Random())<<10);
p_mobj.c(851):		 th->tics -= P_Random()&3;
p_mobj.c(871):		 th->tics -= P_Random()&3;
p_mobj.c(911):		 an += (P_Random()-P_Random())<<20;
p_plats.c(247):		 plat->status = P_Random()&1;
p_pspr.c(477):		 damage = (P_Random ()%10+1)<<1;
p_pspr.c(483):		 angle += (P_Random()-P_Random())<<18;
p_pspr.c(511):		 damage = 2*(P_Random ()%10+1);
p_pspr.c(513):		 angle += (P_Random()-P_Random())<<18;
p_pspr.c(634):		 damage = 5*(P_Random ()%3+1);
p_pspr.c(638):		 angle += (P_Random()-P_Random())<<18;
p_pspr.c(719):		 damage = 5*(P_Random ()%3+1);
p_pspr.c(721):		 angle += (P_Random()-P_Random())<<19;
p_pspr.c(725):		 bulletslope + ((P_Random()-P_Random())<<5), damage);
p_pspr.c(808):		 damage += (P_Random()&7) + 1;
p_spec.c(1042):		 || (P_Random()<5) )
```

Ok uh

```//
// P_SpawnPuff
//
extern fixed_t attackrange;

void
P_SpawnPuff
( fixed_t	x,
fixed_t	y,
fixed_t	z )
{
mobj_t*	th;

z += ((P_Random()-P_Random())<<10);

th = P_SpawnMobj (x,y,z, MT_PUFF);
th->momz = FRACUNIT;
th->tics -= P_Random()&3;

if (th->tics < 1)
th->tics = 1;

// don't make punches spark on the wall
if (attackrange == MELEERANGE)
P_SetMobjState (th, S_PUFF3);
}

//
// P_SpawnBlood
//
void
P_SpawnBlood
( fixed_t	x,
fixed_t	y,
fixed_t	z,
int		damage )
{
mobj_t*	th;

z += ((P_Random()-P_Random())<<10);
th = P_SpawnMobj (x,y,z, MT_BLOOD);
th->momz = FRACUNIT*2;
th->tics -= P_Random()&3;

if (th->tics < 1)
th->tics = 1;

if (damage <= 12 && damage >= 9)
P_SetMobjState (th,S_BLOOD2);
else if (damage < 9)
P_SetMobjState (th,S_BLOOD3);
}
```
Why the hell are these using P_Random instead of M_Random? So in multiplayer, all peers have to keep track of every time a bullet puff / blood splat is created anywhere on the level, regardless of how far away? That's pretty retarded.

yes it is, and it will lag up a game.

Linguica said:

Why the hell are these using P_Random instead of M_Random? So in multiplayer, all peers have to keep track of every time a bullet puff / blood splat is created anywhere on the level, regardless of how far away? That's pretty retarded.

Lol not just one, but at least 3 P_Randoms() for every stupid puff and blood splat X-D

Hmm...so that puffs and splats look exactly the same for everyone? Probably we discovered a new performance-sapping glitch for MP games :-) It's really pointless, as it's purely visual, and imagine how it drives even mildly laggy connections crazy, especially with modified super-speed chainguns and the such :-D

I hope that some future MP port will take this into account and use M_Random() for it, as it should be. Greatly enhanced multiplayer experience!

Other retarded uses of P_Random:

* Determining which alert / death sound is used
* Determining when a monster makes its roaming growl
* Placing the explosions after the boss brain dies (OK this one sort of makes sense I suppose)
* Flickering / flashing lights (so a lot of flickering lights in a level would make multiplayer absolutely drag?)
* What direction the blood splats fly when something is being crushed (honestly what the fuck)

Linguica said:

* What direction the blood splats fly when something is being crushed

Uh don't the blood splats always fall downward

Maes said:

imagine how it drives even mildly laggy connections crazy, especially with modified super-speed chainguns and the such :-D

Well correct me if I'm wrong, but isn't the whole point of (the original) Doom multiplayer code that every peer is simply sent what each player is up to during each tic, and the rest is completely deterministic? So it shouldn't really make a difference how often P_Random is called, it's not as if the game is sending a packet each time or anything.

I am sure client-server source ports have overhauled all this shit anyway.

Linguica said:

I am sure client-server source ports have overhauled all this shit anyway.

Well...in a synchronized comms model, it should be sufficient to sync clients at the end of each tic and submit a list of all actions performed during this tic (e.g. which actors fired, which ones moved and how much, which switches were hit etc.) AND, just in case, the current P_Random() index, which would enable to detect inconsistencies/out-of-sync situations and even fixing them, to some degree (e.g. with a "tic buffer").

On the other hand, a poorly designed asynchronous comms model will, indeed, need to send a small packet on EVERY event to EVERY client, though not for a pure P_Random call (P_Random is always called from other functions and events, never on its own).

Csonicgo said:

yes it is, and it will lag up a game.

What? No it won't.

Maes said:

Hmm...so that puffs and splats look exactly the same for everyone? Probably we discovered a new performance-sapping glitch for MP games :-) It's really pointless, as it's purely visual, and imagine how it drives even mildly laggy connections crazy, especially with modified super-speed chainguns and the such :-D

I hope that some future MP port will take this into account and use M_Random() for it, as it should be. Greatly enhanced multiplayer experience!

Calls to P_Random have no effect whatsoever on network latency or performance. That's why it's a pseudorandom number generator: it generates a predictable sequence of numbers. When you call P_Random(), there is no data exchanged over the network. It is assumed that because all peers are synchronised, they will all run through exactly the same game actions, and because the pseudorandom number generator is predictable, they will all generate the same sequence of numbers.

Linguica said:

Other retarded uses of P_Random:

* Determining which alert / death sound is used
* Determining when a monster makes its roaming growl

Imagine playing a multiplayer game where there are two PCs side by side with external speakers. You kill a monster, and hear a different sound effect on each PC.

* Placing the explosions after the boss brain dies (OK this one sort of makes sense I suppose)
* Flickering / flashing lights (so a lot of flickering lights in a level would make multiplayer absolutely drag?)
* What direction the blood splats fly when something is being crushed (honestly what the fuck)

Some of these come under the same category. If you have two players side by side in a game, they should see the same thing. You aren't likely to notice stuff like blood splats, and it probably doesn't matter; however, it's more a case of "what shouldn't use P_Random?" rather than "should this use P_Random?". The Doom synchronised multiplayer model is incredibly sensitive to desyncs and it makes sense to do exactly the same thing on each peer, even if you are using the random number generator for seemingly trivial things. I don't know for sure, but I wouldn't be surprised if something like the presence of an additional blood splat threw the entire game out of sync. You can see the same thing with the whole demo compatibility mess: maintaining demo compatibility with Vanilla Doom is a nightmare for source port authors, because a tiny difference in how memory is corrupted leads to a chain reaction that throws the entire demo out of sync.

Linguica said:

Why the hell are these using P_Random instead of M_Random? So in multiplayer, all peers have to keep track of every time a bullet puff / blood splat is created anywhere on the level, regardless of how far away? That's pretty retarded.

The game world is totally independent of the rendering engine: it always runs through exactly the same sequence of actions. It has no concept of the fact that the world itself is being rendered to the screen somewhere. This greatly simplifies things. In fact, it would probably be more CPU-intensive to do some kind of "check this is visible" test every time a blood splat is created than to just create it anyway and run it assuming it might be visible.

The result of all these things is that actual damage calculations are very hard . . .

An "accurate" damage computation for each kind of weapon would require to compute all possible permutations/combinations of the table's values taking into account the e.g. 3-batch and 5-batch usage pattern of the SG and SSG. In other words, to account for ALL possible permutations or combinations (WITH REPETITION) of batches of consecutive calls starting at any random point of the table.

Any takers? :-p

You say that like it's a hopeless task. It doesn't sound like one to me, or at least it doesn't sound hopeless to improve the data currently displayed in the wiki. One just has to know how many extra random numbers are needed for each one that is actually used in P_DamageMobj or whatever. For example, the pistol needs two for dispersal, plus three for the blood splat, plus one for the pain chance, which makes a total of seven. (For "spraying" weapons like the SSG, it seems traditional to assume that every pellet connects, at least in documents predating the source release. If the player doesn't want to stand that close to the revenant that's his problem.  :>

Is pain chance actually checked for every pellet, or is it only called once per tic?

The "starting at any point of the table" is the easy part, in fact, because there are only 256 entries. I have done it using just the auto-fill function in a spreadsheet.

So far, we're simulating a player shooting at a monster embedded in a wall, with no flickering lights etc. and no other actors on the level. To go further than this and allow counterattacks, AFAICT, we would have to make a lot of assumptions about how the player moves around during the battle (at least as a statistical trend). More room for debate there I suspect.

The player can't move and no other monster can attack *during* the chain of function calls resulting from a player's weapon attack. I keep seeing a sort of non-programmer's conceptual mistake repeated here, and that's the idea that the AI in Doom is somehow multithreaded, as though each monster has its own execution stack and could somehow think while the player or other monsters were taking actions.

This isn't how Doom (or any other game I personally know of) works.

Doom gives each monster and the player a turn to "think" each gametic. Each object is serviced like this in a sequential order by running down the thinker list and calling the appropriate function for each one. During the time of thinking for a single monster, other monsters are in effect frozen. They may be forced into a new state due to being damaged or killed by the currently thinking object, but they cannot start an attack of their own at this point and suddenly steal the current object's thinking turn, or somehow interlace the execution of thinking functions. Only a multithreaded game which gave each AI its own thread could do such a thing. And it would be insanely complicated too.

Xeriphas1994 said:

Is pain chance actually checked for every pellet, or is it only called once per tic?

From my experience with the shotguns, it's per pellet.

Im just wondering, is there are limit to how many calls can be made during any one time?

EANB said:

Im just wondering, is there are limit to how many calls can be made during any one time?

The problem here is defining what you mean by "during any one time": certain actions consume a fixed amount of P_Random() calls (Gunshot, Shotgun shot etc.) but what will follow between one pellet and the others, there is no telling. If you meant "what if other methods/processes call P_Random() at the same time", that cannot happed in classic Doom engines: they are single threaded, and event handling is purely sequential, thus certain actions cannot "poke in" the middle of others. So there's only one call to P_Random at any given time, there's no issue of syncing multiple threads or anything like that.

E.g. shooting a shotgun will involve using 3 P_Random values per pellet, plus some other for pain chance and blood/puffs assuming they connect (in theory puffs should always be drawn, even if into "nothing"). Other things such as monster counterattacks and movement cannot "poke in" that sequence, the for loop of the shotgun firing will have to be completed, and each pellet will at most trigger one pain chance check and one puff/blood splat, nothing else.

What makes computing a very accurate table correctly is that that value of P_Random calls to "skip" between each pellet is randomly variable, however however for simplicity's sake we could assume that every pellet hits (we're trying to determine maximum damage, after all) so the usage pattern would be something like 7x(3-1-1) or whatever, and that would be entirely sequential. Of course, you'd have to obtain results for all possible 256 starting positions.

It's a minor refinement, but it could lead to e.g. a "maximum damage" configuration to be found impossible to obtain (e.g. finding 7 consecutive values in the P_Random table that would have a modulo of 3 equal to 2, thus giving 15 damage per pellet).