Factorio Forums

This is primarily for Factorio developers. I've noticed guys you are actively working on performance of very large maps, and wanted to check if you heard about https://en.wikipedia.org/wiki/Hashlife ?
I bet all of you are familiar with Conway's game of life, and, thinking about it, Factorio in many aspects is an heavily extended version of it. So I wondered if hashlife-like algorithm can be used on Factorio. It would allow enormous factories to be run with very little CPU load.
Of course there's no direct mapping, and electricity, mining and variable resource input rate will need to be taken into picture, but I believe there are ways to handle that.

Well, it's not about concurrent preprocessing like in hashlife. Factorio is designed from the ground-up to be deterministic with vast interdependency. This is the same reason why you cannot multithread Factorio that well. A drill on the otherside of the map would be affected by consuming something like sulfuric acid several thousand chunks away. Preprocessing segments would not help, since most of the contents of said segments would be dependent on other segments being processed beforehand, but that segment might need to be interdependent with the previous segment.

A hashtree relies on similar regions being prevalent throughout the lifetime of the simulation. This is usually the case with most game-of-life systems with oscillators and spaceships being reasonably easy to create (almost all configurations end up with these) and excluding the initial simulation frames where you usually get the highest mortality rate (that is, until it settles down), similar regions are usually dominant. It is also not the hashtree that gives the performance boost but the memoization of the area states. The hashtree just increases the performance of the memoization value accesses.

Thinking about most factories that I have seen, there is little of this self-repeating sections of the factory simulation. As they use floating points, this difference is exacerbated even further over a simplistic alive/dead boolean value. It would be cool if it could be done but I am sure the memory requirement would be insane.

The algorithm itself is not something that easily leans towards concurrent or multithreaded processing anymore than any other data structure does. Any indication that it would add additional complexity because of this is incorrect. Conway's game of life, just like Factorio, is designed from the ground up to be deterministic with vast interdependencies. One change on one side of the board can affect the other side of the board in the same way that mining ore from one part of the factory can affect other parts of the factory.

It is a cool association to make between the game of life hashtree and factorio (as I think it's possible to prove that they are the same game), but the information density in Factorio is the issue (game of life is far more sparse).