10 ms·

What happens if you remove randomness from Doom?

450 points by pdw 11y ago

nullc 11y ago
It might be better to call this Low Probability Doom-- indeed, it's deterministic, but so would changing the random number generator to a counter. The impacts being discussed are mostly the effect of playing the unluckiest game of doom possible. :)
spiritplumber 11y ago
This is neat... since Doom is open source, why not make the binaries available for a quick romp? Also, try $80 as well as $00 and $FF? (Yeah, I'm lazy)
- mahouse 11y ago
  It's very easy to compile any port. I personally recommend you to try Chocolate Doom.
  - GhotiFish 11y ago
    yaay it compiled! Just grabbing an IWAD, I'm looking forward to trying this! Thanks for the suggestion
dfkf 11y ago
Videos of such experiments would be greatly appreciated.
- jmtd 11y ago
  Took me a while but here you go https://www.youtube.com/watch?v=SvfJoy1rjmo https://www.youtube.com/watch?v=SvfJoy1rjmo
pslam 11y ago
Even the "randomness" is deterministic. The fixed, repeating table is an optimization, but it's also completely necessary for multiplayer to work. Doom does things very differently to how more recent multiplayer FPS multiplayer works. Every player's host machine has identical state. That's not as superficial as things like score, who is alive/dead, etc - it's exact positions or all entities, their metadata... all the way down to the next number to be picked by the random number generator. This is updated every tick (30Hz? can't remember) and every machine needs to synchronize with every other within that tick, or the game slows down. If you've ever played Doom over a modem, you know what it's like when someone has bad settings which result in high latency - in this case, poor frame rate. The data sent between machines consists of the inputs - e.g rotation, movement, fire, talk - and not higher level constructions such as motion vectors. So it's entirely necessary that the "random" number generator is not so random at all. It's fairly hilarious to see the results of messing with it, though :) It does make me think that cheats (not that I ever cheated) were missing a trick. If they knew what the next number to be pulled from the random number generator was, they could, for example, delay firing a weapon by a frame or two, to get more damage. Probably other more interesting things I can't think of immediately. If there was ever a bot vs bot Doom competition, this is something you'd definitely want to consider.
- xamuel 11y ago
  >If they knew what the next number to be pulled from the random number generator was, they could, for example, delay firing a weapon by a frame or two, to get more damage. Probably other more interesting things I can't think of immediately. If there was ever a bot vs bot Doom competition, this is something you'd definitely want to consider. If you're interested in that kind of stuff, check out tasvideos.org, a community dedicated to beating old videogames as fast as possible using that type of knowledge. Since all videogame 'randomness' is really deterministic pseudo-randomness, the kind of RNG-knowing you described is ubiquitous In fact, by coincidence, it looks like someone just recently published a DOOM (second episode) run: http://tasvideos.org/2825M.html http://tasvideos.org/2825M.html
  - pslam 11y ago
    Wow! Yes, I am interested in that kind of thing. Also a coincidence: me and my brother used to do cooperative 2-player speeed-runs of Doom/Doom2 as part of a thing called "H2HMud". We had a setup which consisted of a fast 486, and a really slow 386. It ran really slowly - about 1/4 normal rate when you woke up a room full of entities. The 486, however, rendered every frame, which meant the person on the fast machine could happily pick every off pixel-perfect, while the slower machine player would do "support" stuff (flip switches). I wondered what the "limit" would be if you could slow it down arbitrarily, and re-stitch, and I guess that's what it looks like in the video you posted. Thanks!
  - anon4 11y ago
    My favourite example: http://tasvideos.org/1145M.html http://tasvideos.org/1145M.html completing a game in under 10 seconds by manipulating the RNG to spawn the final quest completion item under the player's initial spawn point.
- dchichkov 11y ago
  Yes. By the way this feature of Doom was allowing nice and symmetric multiplayer over slow modem or network lines. Only small client-side packets were send through the network (think keystrokes/mouse movement updates). As a different example Quake was designed using a client/server model with hugely asymmetric packet sizes (~40 bytes for client->server packet and ~800 bytes for the opposite direction). As a teenager at around 1996-1997 I once tried to re-factor Quake to use the same model as Doom - run server/client combo on both machines with servers synchronized using exact same random generator seeds / etc. Spend about two months on that, but it had proved to be very difficult - the sync between the servers was inevitably lost due to some indeterminism in the code that I couldn't uncover. Maximum that I was able to achieve was around two seconds running in sync. And I still don't know where the sync was getting lost ;) Learned a lot from that experience, big thank you to John Carmack (and the Id Software team) for writing that code as good and clean as he/(they) did...
doener 11y ago
>What happens if you remove randomness from Doom? tl;dr: Nothing intersting.
bentcorner 11y ago
It's interesting that such a simple implementation of randomness works so well, in particular enemy in-fighting and their decision to pursue or not. I'm sure when you're playing, you end up anthropomorphizing many of these decisions.
- anyfoo 11y ago
  Note that these decisions might still be "intelligent" (to a certain degree, i.e. not actually random but based on reasoning) without that hack. But there might be a small chance involved where the entity would do another thing than the algorithmically determined action, and depending on how the values are interpreted this then triggers, the overriding of the game AI now just happens every time.
kkl 11y ago
Beautiful. This article made me smile. I also like that the author gave a simple "how-to" at the end in case I wanted to try it myself (i do!).
twblalock 11y ago
I'm always impressed by the simple ingenuity of the Doom source code and the immersive environment it creates.
RussellDussel 11y ago
This instantly reminded me of the (true) story where people were able to cheat an online poker game because the site released its source to "prove" its fairness/randomness, showing that the deck was shuffled from a fixed state using a standard RNG with the time of day (in ms) as the seed. Of course this meant there were only 86,400,000 possible decks, people could generate all the possible decks ahead of time and as soon as cards would be revealed in the game they could easily match the hand being played to the limited set of possibilities. Essentially they had foresight of which cards were coming out. Furthermore, once a few decks were matched up you could vastly reduce the set of possibilities even further by working out the approximate time of day on the server.
- swang 11y ago
  This is PlanetPoker[0] The gist of it is their algorithm never chose the last card in the array to swap with, and the last card was never guaranteed to be the last card. They also committed the common mistake of implementing the "naive" shuffle, which is not equally distributed. [0] http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph...
- im3w1l 11y ago
  By the birthday property, this means that it is very likely to experience the exact same deck being played out more than once.
pcvarmint 11y ago
When I added friendly monsters and Wolf3D dogs to Doom, I tweaked the randomness to make the dog behavior more life-like. Friendly monsters go after enemy targets, but absent any targets, they follow you in semi-random motions, but they stay a comfortable distance away from you, except when getting onto a platform or other crowded space. Disclaimer: I'm the author of MBF.
- pcvarmint 11y ago
  Also, demo reproduction was a huge issue. We had to do all kinds of versioning to make sure that a demo which was recorded with one version of Doom/Boom/MBF/etc. was faithfully replayed with the current version. One tiny mistake, and the whole demo could go into a tailspin. This sometimes meant we had to preserve bugs like Lost Soul stuck-in-wall bugs.
  - pcvarmint 11y ago
    Oh, and randomness could have fixed the monster-stuck-in-doorjam bug, which is easily reproduced in E2M4 with the Baron by the blue key. The code assumed that if a monster was "in" a door sector and was blocked, then the door simply needed to be opened, and then the monster could continue in its current direction. Better would be to rotate the monster's direction randomly to help them to get out of the sticky situation. That was our fix in Boom.
PhasmaFelis 11y ago
> Monsters do not make different death noises at different times; only one is played for each category of monster. This, BTW, is a really interesting trick that Doom pulled. There's actually only a single death sound for each type of monster.* But for some monsters, the game plays it back at a random speed--also changing the frequency, like an audiotape on fast-forward--so it becomes a brief shriek, a drawn-out groan, or something in between. This gives an impressive variety of sounds without adding extra memory-heavy samples. Hardly anyone was aware of this as far as I can tell, which is a testament to how well it worked. I only noticed it when playing a goofy little mod that turned zombie sergeants into Energizer bunnies and played the "still going" clip when you killed them. The effect is obvious when there's actual speech involved. *Not counting the "splatter" sound when you gib any of the gibbable critters.
- PhasmaFelis 11y ago
  On further consideration, I think it only does this with imps and the various zombies, which are the only monsters that you're likely to mow down at a rate of several per second--it might have been specifically intended to stop zombie fragfests from sounding like an echo chamber.
  - jmtd 11y ago
    Hi, article author here: it was the pitch shifting behaviour in particular that I wanted to explore when I modified the random table. Early versions of doom (<1.4) did it, but they accidentally removed that feature with a rework of sound code in 1.4 and onwards (including all versions of doom 2). It was originally applied to all but two sound effects, with special casing for chainsaw sounds (less variance afaik). There were, however, three distinct zombie death noises, independent of pitch shifting.
    - PhasmaFelis 11y ago
      Interesting! Are the three zombie death sounds perhaps speed-shifted versions of the same original? My recollection (it's been a while) is that zombies made dramatically different sounds on death but--once I started looking for it--they all seemed to be speed-shifted versions of the same sound, while pitch-shifting in other sounds was subtle enough that I never noticed it. If pitch-shifting normally applied equally to most sounds, that implies that there was something else going on with the zombie noises I recall. Or maybe I'm completely confused because I haven't played it since the '90s. Might be time to give it another try...
zak_mc_kracken 11y ago
I'm intrigued by this: > I hex-edited the binary and replaced the random number lookup table with static values If you have a look up table that you randomly look up, doesn't that mean you already have a random source? In this case, why need a random look up table at all?
- JasuM 11y ago
  It reads the next number in the list, it's not a random lookup. See https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/m_random.c https://github.com/id-Software/DOOM/blob/master/linuxdoom-1....
  - justsid 11y ago
    Doesn’t that already make it deterministic though? It’s always the same sequence of “random” numbers, even before replacing the lookup table it should’ve been deterministic.
PhasmaFelis 11y ago
> The chance of monster in-fighting is never, or a certainty. The player is either mute, or cries in pain whenever he's hurt. This is interesting. I thought that both of those things were deterministic to begin with--monsters that get hit by other monsters will go after the offender until it's dead or something else hits them, and the player makes the "pained gasp" sound effect every time he's hit.
- shultays 11y ago
  OP is wrong about Doom's determinism I guess, it is already deterministic, random values are predefined. He just set them to constant, so his random is literaly "int random() {return 4;}", still deterministic but not 'random'
  - PhasmaFelis 11y ago
    Regular Doom may not be random in the mathematical sense, but it is as far as a player is concerned. In combat, pulls from the "random number" pool are happening fast enough that I don't believe it could be exploited in any meaningful way. What I meant was, I hadn't thought that infighting target choice and player pain-noise referred to the "random" pool at all. I thought they were 100% predictable in the original game. I wonder where the randomness actually comes in.
    - shultays 11y ago
      Timings of user input probably.
azinman2 11y ago
Wish there had been videos posted!
- jmtd 11y ago
  Yeah a video would be a good way to demonstrate this but it would take a lot of editing to do properly and I ran out of time last night and really wanted to get this out. I might post a follow up video later.
- jmtd 11y ago
  Took me a few days, but here's a video https://www.youtube.com/watch?v=SvfJoy1rjmo https://www.youtube.com/watch?v=SvfJoy1rjmo
madsravn 11y ago
> The chance of monster in-fighting is never, or a certainty. Still seem a little random, though
yuriks 11y ago
PRNG determinism is widely utilized in TAS (Tool-Assisted Speedrun, basically a game played using tools such as frame advance and save states to simulate a "omnipotent" player.) to manipulate games to achieve favourable outcomes. Usually the game code is reverse engineered and a Lua script is created that searches forward in the RNG outcomes to find the ones you want, it is then up to the runner to execute actions in the game that give you that state. One example of this technique which I particularly like is the "100% Souls" run of Aria of Sorrow, where the normally very grindy process of getting enemy soul drops is trivialized by making sure that every enemy will drop a soul the first time it's killed: https://www.youtube.com/watch?v=DfkJpzBoJ-M https://www.youtube.com/watch?v=DfkJpzBoJ-M

450 points by pdw 11y ago

nullc 11y ago

It might be better to call this Low Probability Doom-- indeed, it's deterministic, but so would changing the random number generator to a counter. The impacts being discussed are mostly the effect of playing the unluckiest game of doom possible. :)

spiritplumber 11y ago

This is neat... since Doom is open source, why not make the binaries available for a quick romp? Also, try $80 as well as $00 and $FF? (Yeah, I'm lazy)

mahouse 11y ago
It's very easy to compile any port. I personally recommend you to try Chocolate Doom.
- GhotiFish 11y ago
  yaay it compiled! Just grabbing an IWAD, I'm looking forward to trying this! Thanks for the suggestion

dfkf 11y ago

Videos of such experiments would be greatly appreciated.

jmtd 11y ago
Took me a while but here you go https://www.youtube.com/watch?v=SvfJoy1rjmo https://www.youtube.com/watch?v=SvfJoy1rjmo

pslam 11y ago

Even the "randomness" is deterministic. The fixed, repeating table is an optimization, but it's also completely necessary for multiplayer to work. Doom does things very differently to how more recent multiplayer FPS multiplayer works. Every player's host machine has identical state. That's not as superficial as things like score, who is alive/dead, etc - it's exact positions or all entities, their metadata... all the way down to the next number to be picked by the random number generator. This is updated every tick (30Hz? can't remember) and every machine needs to synchronize with every other within that tick, or the game slows down. If you've ever played Doom over a modem, you know what it's like when someone has bad settings which result in high latency - in this case, poor frame rate. The data sent between machines consists of the inputs - e.g rotation, movement, fire, talk - and not higher level constructions such as motion vectors. So it's entirely necessary that the "random" number generator is not so random at all. It's fairly hilarious to see the results of messing with it, though :) It does make me think that cheats (not that I ever cheated) were missing a trick. If they knew what the next number to be pulled from the random number generator was, they could, for example, delay firing a weapon by a frame or two, to get more damage. Probably other more interesting things I can't think of immediately. If there was ever a bot vs bot Doom competition, this is something you'd definitely want to consider.

xamuel 11y ago
>If they knew what the next number to be pulled from the random number generator was, they could, for example, delay firing a weapon by a frame or two, to get more damage. Probably other more interesting things I can't think of immediately. If there was ever a bot vs bot Doom competition, this is something you'd definitely want to consider. If you're interested in that kind of stuff, check out tasvideos.org, a community dedicated to beating old videogames as fast as possible using that type of knowledge. Since all videogame 'randomness' is really deterministic pseudo-randomness, the kind of RNG-knowing you described is ubiquitous In fact, by coincidence, it looks like someone just recently published a DOOM (second episode) run: http://tasvideos.org/2825M.html http://tasvideos.org/2825M.html
- pslam 11y ago
  Wow! Yes, I am interested in that kind of thing. Also a coincidence: me and my brother used to do cooperative 2-player speeed-runs of Doom/Doom2 as part of a thing called "H2HMud". We had a setup which consisted of a fast 486, and a really slow 386. It ran really slowly - about 1/4 normal rate when you woke up a room full of entities. The 486, however, rendered every frame, which meant the person on the fast machine could happily pick every off pixel-perfect, while the slower machine player would do "support" stuff (flip switches). I wondered what the "limit" would be if you could slow it down arbitrarily, and re-stitch, and I guess that's what it looks like in the video you posted. Thanks!
- anon4 11y ago
  My favourite example: http://tasvideos.org/1145M.html http://tasvideos.org/1145M.html completing a game in under 10 seconds by manipulating the RNG to spawn the final quest completion item under the player's initial spawn point.
dchichkov 11y ago
Yes. By the way this feature of Doom was allowing nice and symmetric multiplayer over slow modem or network lines. Only small client-side packets were send through the network (think keystrokes/mouse movement updates). As a different example Quake was designed using a client/server model with hugely asymmetric packet sizes (~40 bytes for client->server packet and ~800 bytes for the opposite direction). As a teenager at around 1996-1997 I once tried to re-factor Quake to use the same model as Doom - run server/client combo on both machines with servers synchronized using exact same random generator seeds / etc. Spend about two months on that, but it had proved to be very difficult - the sync between the servers was inevitably lost due to some indeterminism in the code that I couldn't uncover. Maximum that I was able to achieve was around two seconds running in sync. And I still don't know where the sync was getting lost ;) Learned a lot from that experience, big thank you to John Carmack (and the Id Software team) for writing that code as good and clean as he/(they) did...

doener 11y ago

>What happens if you remove randomness from Doom? tl;dr: Nothing intersting.

bentcorner 11y ago

It's interesting that such a simple implementation of randomness works so well, in particular enemy in-fighting and their decision to pursue or not. I'm sure when you're playing, you end up anthropomorphizing many of these decisions.

anyfoo 11y ago
Note that these decisions might still be "intelligent" (to a certain degree, i.e. not actually random but based on reasoning) without that hack. But there might be a small chance involved where the entity would do another thing than the algorithmically determined action, and depending on how the values are interpreted this then triggers, the overriding of the game AI now just happens every time.

kkl 11y ago

Beautiful. This article made me smile. I also like that the author gave a simple "how-to" at the end in case I wanted to try it myself (i do!).

twblalock 11y ago

I'm always impressed by the simple ingenuity of the Doom source code and the immersive environment it creates.

RussellDussel 11y ago

This instantly reminded me of the (true) story where people were able to cheat an online poker game because the site released its source to "prove" its fairness/randomness, showing that the deck was shuffled from a fixed state using a standard RNG with the time of day (in ms) as the seed. Of course this meant there were only 86,400,000 possible decks, people could generate all the possible decks ahead of time and as soon as cards would be revealed in the game they could easily match the hand being played to the limited set of possibilities. Essentially they had foresight of which cards were coming out. Furthermore, once a few decks were matched up you could vastly reduce the set of possibilities even further by working out the approximate time of day on the server.

swang 11y ago
This is PlanetPoker[0] The gist of it is their algorithm never chose the last card in the array to swap with, and the last card was never guaranteed to be the last card. They also committed the common mistake of implementing the "naive" shuffle, which is not equally distributed. [0] http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph...
im3w1l 11y ago
By the birthday property, this means that it is very likely to experience the exact same deck being played out more than once.

pcvarmint 11y ago

When I added friendly monsters and Wolf3D dogs to Doom, I tweaked the randomness to make the dog behavior more life-like. Friendly monsters go after enemy targets, but absent any targets, they follow you in semi-random motions, but they stay a comfortable distance away from you, except when getting onto a platform or other crowded space. Disclaimer: I'm the author of MBF.

pcvarmint 11y ago
Also, demo reproduction was a huge issue. We had to do all kinds of versioning to make sure that a demo which was recorded with one version of Doom/Boom/MBF/etc. was faithfully replayed with the current version. One tiny mistake, and the whole demo could go into a tailspin. This sometimes meant we had to preserve bugs like Lost Soul stuck-in-wall bugs.
- pcvarmint 11y ago
  Oh, and randomness could have fixed the monster-stuck-in-doorjam bug, which is easily reproduced in E2M4 with the Baron by the blue key. The code assumed that if a monster was "in" a door sector and was blocked, then the door simply needed to be opened, and then the monster could continue in its current direction. Better would be to rotate the monster's direction randomly to help them to get out of the sticky situation. That was our fix in Boom.

PhasmaFelis 11y ago

> Monsters do not make different death noises at different times; only one is played for each category of monster. This, BTW, is a really interesting trick that Doom pulled. There's actually only a single death sound for each type of monster.* But for some monsters, the game plays it back at a random speed--also changing the frequency, like an audiotape on fast-forward--so it becomes a brief shriek, a drawn-out groan, or something in between. This gives an impressive variety of sounds without adding extra memory-heavy samples. Hardly anyone was aware of this as far as I can tell, which is a testament to how well it worked. I only noticed it when playing a goofy little mod that turned zombie sergeants into Energizer bunnies and played the "still going" clip when you killed them. The effect is obvious when there's actual speech involved. *Not counting the "splatter" sound when you gib any of the gibbable critters.

PhasmaFelis 11y ago
On further consideration, I think it only does this with imps and the various zombies, which are the only monsters that you're likely to mow down at a rate of several per second--it might have been specifically intended to stop zombie fragfests from sounding like an echo chamber.
- jmtd 11y ago
  Hi, article author here: it was the pitch shifting behaviour in particular that I wanted to explore when I modified the random table. Early versions of doom (<1.4) did it, but they accidentally removed that feature with a rework of sound code in 1.4 and onwards (including all versions of doom 2). It was originally applied to all but two sound effects, with special casing for chainsaw sounds (less variance afaik). There were, however, three distinct zombie death noises, independent of pitch shifting.
  - PhasmaFelis 11y ago
    Interesting! Are the three zombie death sounds perhaps speed-shifted versions of the same original? My recollection (it's been a while) is that zombies made dramatically different sounds on death but--once I started looking for it--they all seemed to be speed-shifted versions of the same sound, while pitch-shifting in other sounds was subtle enough that I never noticed it. If pitch-shifting normally applied equally to most sounds, that implies that there was something else going on with the zombie noises I recall. Or maybe I'm completely confused because I haven't played it since the '90s. Might be time to give it another try...

zak_mc_kracken 11y ago

I'm intrigued by this: > I hex-edited the binary and replaced the random number lookup table with static values If you have a look up table that you randomly look up, doesn't that mean you already have a random source? In this case, why need a random look up table at all?

JasuM 11y ago
It reads the next number in the list, it's not a random lookup. See https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/m_random.c https://github.com/id-Software/DOOM/blob/master/linuxdoom-1....
- justsid 11y ago
  Doesn’t that already make it deterministic though? It’s always the same sequence of “random” numbers, even before replacing the lookup table it should’ve been deterministic.

PhasmaFelis 11y ago

> The chance of monster in-fighting is never, or a certainty. The player is either mute, or cries in pain whenever he's hurt. This is interesting. I thought that both of those things were deterministic to begin with--monsters that get hit by other monsters will go after the offender until it's dead or something else hits them, and the player makes the "pained gasp" sound effect every time he's hit.

shultays 11y ago
OP is wrong about Doom's determinism I guess, it is already deterministic, random values are predefined. He just set them to constant, so his random is literaly "int random() {return 4;}", still deterministic but not 'random'
- PhasmaFelis 11y ago
  Regular Doom may not be random in the mathematical sense, but it is as far as a player is concerned. In combat, pulls from the "random number" pool are happening fast enough that I don't believe it could be exploited in any meaningful way. What I meant was, I hadn't thought that infighting target choice and player pain-noise referred to the "random" pool at all. I thought they were 100% predictable in the original game. I wonder where the randomness actually comes in.
  - shultays 11y ago
    Timings of user input probably.

azinman2 11y ago

Wish there had been videos posted!

jmtd 11y ago
Yeah a video would be a good way to demonstrate this but it would take a lot of editing to do properly and I ran out of time last night and really wanted to get this out. I might post a follow up video later.
jmtd 11y ago
Took me a few days, but here's a video https://www.youtube.com/watch?v=SvfJoy1rjmo https://www.youtube.com/watch?v=SvfJoy1rjmo

madsravn 11y ago

> The chance of monster in-fighting is never, or a certainty. Still seem a little random, though

yuriks 11y ago

PRNG determinism is widely utilized in TAS (Tool-Assisted Speedrun, basically a game played using tools such as frame advance and save states to simulate a "omnipotent" player.) to manipulate games to achieve favourable outcomes. Usually the game code is reverse engineered and a Lua script is created that searches forward in the RNG outcomes to find the ones you want, it is then up to the runner to execute actions in the game that give you that state. One example of this technique which I particularly like is the "100% Souls" run of Aria of Sorrow, where the normally very grindy process of getting enemy soul drops is trivialized by making sure that every enemy will drop a soul the first time it's killed: https://www.youtube.com/watch?v=DfkJpzBoJ-M https://www.youtube.com/watch?v=DfkJpzBoJ-M