AWJ wrote:In an action game where cycles are precious, an advantage of a LFSR over a LCG is that all the bits in a LFSR are equally random. If you only ever need one or two bits at a time, you can get many random numbers out of each clocking of a LFSR.
clocked once per frame
While individual bits of an LFSR are equally random, they're not very independent of each other. If you sampled & 1 for one enemy and & 2 for another enemy, you may see correlated behaviours on successive frames as a "1" bit passes through one then the other. A lot of LFSR implementations are going to do the XOR only on one byte too, so the upper bytes become very
Similarly, if you're doing & 3 (two bits) you should clock it twice
, or if & 7 (three bits) you should clock it three times
. Failing to do so leads to very strong *2, *4, etc. correlations on successive tests.
For complete entropy you should clock it as many times as you read bits, but its somewhat asymptotic, 2 clocks is a lot better than 1 clock, but 7 clocks isn't that much better than 6. You can save time by doing less, if the quality isn't critical. (Also, there's no reason to clock it more times than bits read. It's as random as it's going to get at that point.)
Similarly, if you don't do PRNG tests every frame and try to vary their timing (and still clock it every frame), it breaks up a lot of the correlations that would otherwise appear. That can help too. If it's been 8 frames since you last did a PRNG test but you clocked it every frame, you've got a nice quality 8-bit number ready to use.
AWJ wrote:If two of the same enemy are in the same RNG-tapping state on the same frame then they'll always both choose the same behaviour
I've seen that in several games, and I've always thought of it as a serious flaw, not something people hardly notice.
I've often been annoyed at how unintentionally predictable RPG battles can become.
Anyhow, in a lot of cases, very poor quality PRNGs will seem sufficient. Clocking an LSFR once per frame may indeed be good enough sometimes, but it's often not immediately obvious how a poorly used PRNG is hurting things. Sometimes it takes a while to discover that in testing, but once discovered it becomes an easy to use exploit. Sometimes you don't realize why something plays out kinda crummy, and it's really just from poor PRNG use, but you can't tell because you're not comparing against a good PRNG.
I do like the LFSR generators, but my recommendation is to clock it once for every bit you need to read from it. Don't "optimize" before you begin by starting from the poorest entropy. Start with the good stuff, and optimize it only IF you need the extra cycles. Usually games do not need to make PRNG tests very frequently, and in such cases you'll gain almost nothing by using a poorer PRNG but there's a lot to lose. It's very likely efficient enough just to do it properly! You don't have to use some super slow cryptographically secure PRNG, there are plenty of simple ones that are reasonably fast and good quality.
In Zutano's example (OP) the entropy is controlled directly by the input parameter in X. If reading 3 bits, call it with X=3 and use the result & 7. That's basically perfect usage. Only use the lowest bits, and don't "share" the LFSR. Don't think about doing less work until PRNGs are
your performance problem.