5 ms·
One Number Repeated Forever: RNG in NSMB (2020)
- _Microft 5y agoI am curious what went wrong during development here. Was it an accident? Did someone think that it would be a waste to throw away all these fine higher bits and just did anything with them? (It feels a bit like a self-designed crypto algorithm when someone adds complexity because that's sure better than not, isn't it?) They might not have been too familiar with linear congruential generators (LCG) because then they would have known that casting the result to an unsigned 32bit integer was not an accident but the modulus operation of the LCG (here: "mod 2^32"). See [0] for details. [0] https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator
- no_multitudes 5y agoI wonder if it could have been done to shut up some static analysis tool?
- bentcorner 5y agoThat's my guess too. They were probably using ranqd1, then someone turned on a new warning, then someone else had to figure out what to do with the warning without really understanding the change they were making. It'd be interesting to see if the same randomizer is used in other SMB games after NSMB and any ports.
- _Microft 5y agoI don't think this would make a warning go away. value + (value >> 32) is still a 64bit int value that gets then cast to a 32bit int.
- bentcorner 5y agoWhoops, good point. Uh.. maybe there's a cast in the original source and the bit shift was added at the same time?
- blackboxlogic 5y agoSpeculating: Perhaps a feature for automated regression testing? Start the game with the "cursed" seed, run your script of inputs and compare the outputs against the results of your last production release. Versus the normal RNG, where a game difference which touches the RNG would alter ALL following output, hiding later game differences.
- flatiron 5y agomy thought exactly, its a feature not a bug. a way for a unit test to possibly "play" the game with RNG effectively "disabled"
- pcwalton 5y agoThat's far too subtle. If a developer were going to add a debugging mode like that, they'd just add a flag that's checked in the function and makes it return a constant.
- _Microft 5y agoThat was my thought as well. Why bother with finding a fix point of your PRNG (and messing up its properties in the process) when one could use something like #ifdef ... return 4; instead.
- xyzzyz 5y agoIt would be much, much simpler and much more robust to just have a flag that when set, makes RNG returns the same number, instead of depending on some very obscure behavior of specific hard coded constants chosen.
- tinus_hn 5y agoThis was probably implemented in assembler, which makes it easy to make a mistake like this, and how are you going to check?
- pcwalton 5y agoI doubt this was implemented in assembler. It's not performance critical, and 32-bit ARM is a friendly enough target for a compiler that a human won't be able to improve upon the compiler's output anyway.
- NobodyNada 5y agoAssembler? That seems very unlikely, as this was a DS game released in 2006. Ever since the Nintendo 64 and GameBoy Advance, compilers have been good enough and the hardware has been more than powerful enough that games have been typically implemented in C.
- azundo 5y agoObligatory XKCD: https://xkcd.com/221/ https://xkcd.com/221/
- pavel_lishin 5y agoObligatory Dilbert: https://dilbert.com/strip/2001-10-25 https://dilbert.com/strip/2001-10-25
- blackboxlogic 5y agoAm I having a moment or is the math off? > Given a random starting seed, rand_nsmb will repeat an output after 1,820,529 calls, on average. > Longest cycle: 1 cycle of length 1,708,724
- steerablesafe 5y agoI think the solution is that not every seed value is part of a cycle, but they might lead to a cycle.
- danbruc 5y agoIf you look at all the listed cycles, their total length is 2,664,154 or only about 0.06% of all the 32 bit integers. So 99.94% of all the integers first follow some linear path before eventually entering into one of the cycles. Now depending on the exact structure of the graph - are there a few long paths or are there many short paths entering into the cycles and into a cycle of which length do the different paths enter - the average sequence length until the first repetition across all starting points can be very different including longer than the longest cycle in case there are relatively few but long paths entering into the cycles.
- coolreader18 5y agoI was able to guess that it was the Mario game (but I was unsure since this is HN not gamefaqs), but I'd think there are probably other acronyms that people here might jump to - I think the acronym should probably be expanded in the title.
- twic 5y agoI also initially guessed that the number was 1488.
- dang 5y agoPlease don't do this here.
- memco 5y agoThe article mentions that the seeding is sufficiently random so to make it unlikely to at the RNG will get fixed, but it would be cool to see more details about how you might be able to guarantee that seed so you can speed run or TAS the game.