Older seed finders for Factorio speedrunning used to analyze map previews generated by the Factorio binary. This method was really slow, making a full scan of all maps in the game impossible in a reasonable time. Fast Factorio Seed Finder directly uses the map generation algorithms from the game, which allows for major optimizations, reducing run time by many orders of magnitude. Those algorithms were reverse engineered and Wube kindly agreed to let me share them.
If not used properly, this seed finder will be about as slow as all the other ones, so you should read this if you want to create your own seed finder.
For our purpose, the game's map generation pipeline can be broken down in 3 steps:
- Generate regular patches' position and radius. Note that is means patches are perfect circles, the irregular shape is added later. Regular patches are all the patches further than about 250 tiles from spawn and are not affected by water settings and map type. Also for any integer n, the seeds 2n and 2n+1 will generate the exact same regular patches (For example seeds 1000 and 1001 have the same patches, same for seeds 3404 and 3405). Later I'll be calling those pairs "twins".
- Generate starter patches' position and radius, again as perfect circles for now. These patches are (almost) all the patches that generate closer that 256 tiles from spawn. Just like regular patches they are not affect by map type. However they are effected by water settings, so changing water scale or coverage will change them in most cases and they are not the same for every twins. This step is about 10x slower than the first one.
- Finally the game does all of the noisy stuff, like giving patches their actual shape or generating water. This step is extremely slow, because it needs to run for every tile in the map. Water is affect by the seed, the water settings and the map type (called elevation type internally). Note that the seed finder cannot generate the noisy patch shapes for now because I don't think it is really useful.
When the game generates a preview, it has to run all 3 steps. This leads to 2 major slow downs for seed finding: First running the slower 2nd and 3rd steps may be unnecessary if the first one alone is enough to eliminate a map. Second, if we want to analyze all 4 billion seeds with all possible water settings and all 3 map types (or ~1.8 trillion maps) then the game will run the first step 1.8 trillion times, once for each map. However because it gives the exact same result for every twins, for every water settings and for every map types, we could run it just 2 billion times and have the same information.
So here is the main idea of this seed finder: First we run the first step once for one seed in each twins (that is 2 billion) times, eliminate as many seeds as possible with the information we have for now (that is perfectly circular regular patches). Then, for every remaining seeds, we add its twin and all map settings to the list and run the 2nd step. Finally we run the 3rd step 3 times per remaining maps, once for every map type. If our criteria allow to eliminate enough seeds in the 1st and 2nd steps, then we can check all 1.8 trillion maps in a reasonable time.
The seed finder I made for vanilla any% requires a very big back side (6 iron and 12 copper belts + some coal very close to the spawn) so it is able to eliminate almost every seeds in the first step and takes about 1 hour to do a 1.8 trillion maps full scan on my 7800x3d. On the other hand the botless any% seed finder is much slower because the back side criteria are much weaker. (about 18 hours)
- noise.hpp: Functions to generate the map.
- algorithm.hpp: Some useful algorithms to analyze patches.
- finder.hpp: A pipeline that manages outfile, threads, input arguments, etc. Takes in seed evaluation functions every steps.
- The patch noise is not supported and only the perfect circular patches can be generated.
- Only Nauvis is supported.
- Uranium ore is not supported.
- Fork this repository.
- Create a new directory in ./seed_finders/ and add that directory to the top CMakeLists.txt
- Copy the CMakeLists.txt from the example seed finder and change the executable name.
I highly recommend to check out the example seed finder which looks for maps with as little ore as possible in a 1024x1024 square around spawn.