Reversing Factorio's RNG
summary
The author demonstrates that Factorio's pseudo-random number generator (PRNG), based on the taus88 algorithm, is deterministic and can be reversed through linear algebra. By observing specific in-game events and applying matrix-vector multiplication over the Galois field GF(2), the internal state of the RNG can be reconstructed. This allows a player to predict future outcomes, such as item quality increases, effectively removing the randomness from the game's crafting process.
key points
- The game uses the taus88 generator, which consists of three independent linear feedback shift registers (LFSRs) whose outputs are XORed together.
- Because LFSRs are linear, their state transitions can be modeled as matrix products in GF(2), making the internal state recoverable if enough consecutive outputs are observed.
- To implement this in-game, the author uses the recycling of repair packs as an 'entropy generator' to extract the necessary bits of information from the RNG calls efficiently.
who should read it
Players of Factorio who are interested in reverse engineering, computer science, and the mathematical application of linear algebra to game mechanics.
discussion warm
consensus
Commenters generally admire the technical sophistication required to reverse-engineer RNG systems in games like Factorio and Stardew Valley. They agree that seemingly random events are predictable once the underlying mathematical system or seed is identified. The sentiment is one of fascination and respect for the dedication involved in these 'black magic' optimizations.
top insight
A contributor explains that the Nintendo Switch's RNG differs from the PC version of Stardew Valley, suggesting a specific three-step methodology to crack the multiplayer ID seed by testing against known implementations and analyzing geode contents. This provides a practical roadmap for applying reverse-engineering techniques to platforms with restricted save-file access.
Generated by an LLM from the article and thread. Check the sources before relying on it.