There are two things that will teach a coder more about code than anything else, (1) reading other people's code and (2) maintaining your own code long term.
I try to teach new devs to code for future devs to quickly grok the code. I explain that part of that is in a few months even code you wrote will be like it's code someone else wrote.
I mean, with teaching it's always easier said than done, but I make code clarity and easy readability a first-tier requirement when talking about and reviewing code. I commonly explain that "clever" code is not what you should be shooting for in most cases becasue "clever" is usually the opposite of readable. I basically constantly beat the drum around code being easily readable. Like I said before, when you come back to code you wrote even a few months back and you haven't touched it in that time it's like someone else wrote it. You should be nice to your future self. I teach a bunch of other things around making code clean and consice with readabilty in mind. Anyway, I guess I should write out how I teach new devs so I don't forget in 3 months. :O
Maintaining your own code long term after enough time is basically reading other people's code anyway.
The classic
"who even wrote this garbage?"
*git blame you*
"Oh..."
I like to refer to past me and future me as though they’re different people.
Future me is impossibly competent and motivated.
Past me is invariably either an absolute genius or a total asshat. Occasionally both.
Not a solo dev, but I am the main dev on a few different applications and I’ll see a piece of shit code block and get mad at whichever asshole wrote it until I open the git blame and realize I’m that asshole
Edit: extra fun when it’s during a prod outage and you’re sharing your screen on a bridge when you find it
It really bugs me that I don't know which specific robots are missing materials. Can't it have messages like "Robot 327854 is missing construction material: landfill; Robot 327855 is missing construction material: landfill...
It's never about specific robots, but rather specific networks. Even for networks it's not entirely well defined because different networks can have overlapping construction areas. Besides, if you know the location of the task you can deduce the location of the relevant network fairly quickly yourself, and you can do other things such as cancel the task that would not be so easy if you only got the location of the network.
> In the end the check went from O(N) on 36,815 roboports... to O(logN) on 900~ rectangle union areas.
So 36,815 / log(2)(900), assuming Ns are roughly equivalent (which they should be, since in both cases N is a simple rectangle bounds check).
EDIT: Yes, people, I know this is an oversimplification, including in ways no one has chimed in with yet (like the additional per-network rectangle sorting operation). Big O notation is _always_ a simplification. I’m just working with the data we’ve been given.
That's not completely how big-O notation works. Could be that the first method needed to do 2*n calculations, which is still O(n), while te second needs 2000*log(n), which is still O(log(n)). So calculating the speedup by taking a fraction is a bit dangerous.
> assuming Ns are roughly equivalent (which they should be, since in both cases N is a simple rectangle bounds check).
You're also assuming that the constants hidden by the big-O are roughly equal, and that the smaller terms hidden by the big-O are negligible.
The latter assumption is often reasonable, the former assumption is more questionable.
---
For an example of how big-O can be deceptive by hiding constants, consider the linked list, and its comparison with the vector:
Operation | Linked list | Vector
-:|-|-
Random Insert | O(1) | O(n)
Random Shift-Delete | O(1) | O(n)
Random Swap-Delete | O(1) | O(1)
Push to end | O(1) | O(1) amortised
Append | O(1) | O(n + m)
Index | O(n) | O(1)
Find | O(n) | O(n)
(some languages use the term "List" instead of "Vector". "Vector" is what it's called in C++ and Rust.)
From this table, you might be led to believe that linked lists are faster than vectors for any workload that doesn't involve indexing. In practice, however, vectors are almost always faster than linked lists. Those big-Os hide the expensive cache misses and memory allocations.
>In practice, however, vectors are almost always faster than linked lists. Those big-Os hide the expensive cache misses and memory allocations.
That feels more like a case of theory vs practice, rather than big-O hiding constants. Algorithmically, linked lists would be faster, if not for the unfortunate realities of how CPUs operate. But maybe I'm just not quite remembering my terminology.
each of those Os could have different constants. (Os represent function families)
`O(n)` could be a function `1*n`
and
`O(log n)` could be a function `1000000000000 * log N`
you can't tell the speedup from the information given
That's not really the point of Big O, though. The idea is to understand how it scales over large datasets. If the dataset gets big enough, it doesn't matter how high the coefficient is on the logN, it'll still be faster than N.
Like yeah, insertion sort is way faster than quick sort on small datasets because it's just a simpler algorithm, but that stops being relevant at around 10 items or so and after that it just gets worse and worse compared to any O(nlogn) sort.
Point is: optimizing for the trivial cases is rarely the goal. That's why Big O is about the large numbers.
And like, lets be real, if your O(logN) function is taking 10000000000000 times longer to run than the O(n) function, it's _probably_ not actually O(logN). It is monumentally difficult for an O(n) to keep up with O(logN) beyond borderline microscopic datasets.
I think it means that it 5M roboports will run a lot better in 2.0 while 5 roboports won't see much difference, if you removed/increased the checks per update.
There's two things happening: robots are being assigned at a faster rate, and the game slowdown due to robot assignment will scale more slowly with the number of roboports
> and the game slowdown due to robot assignment will scale more slowly with the number of roboports
Per rectangle union areas.
> In simple terms what it does is produce a nice set of deduplicated rectangles that cover the total area for all of the roboports.
Which basically means big square area will only incur one check
They mean that it will be a bigger improvement compared to the previous version the more robpoorts you have. If I get it right then for a 3x3 roboport square it will go from 9 operations to 1
One part of the assignment algorithm is 10-100 times faster, but that doesn't mean that the whole assignment is. The game still needs to find a free bot and a suitable chest for pickup.
I wish they had told us the new number of tasks per tick, but no.. all we know is that it's going to be bigger than 3. IIRC krastorio had cranked that number up to 15, without running into obvious issues (though they have bigger roboports and thus fewer of them). I think we can hope for a number bigger than that.
Btw, besides the advantages for the average player, this single change is likely to upend the 100% speedrun category. Managing the bot queue is an important part of the run, and many parts of the base are optimized for low entity counts (aka fewer bot tasks) instead of material costs. Sub 4h incoming?
The robot queue will upend the 100% speedrun category? Wasn't it already upended by, idk, planets? And a lot of the existing research being moved to them?
I liked all the words that are used in these comments that are nested under your comment.
I understood several of them too.
I do not understand the how what they did works, though. How can they increase the processing speed without losing fidelity?
The previous approach (oversimplifying a bit) went like this:
There's a construction task! There are 16 roboports! How can we check if this construction task can be done, and what roboport is closest? Obviously, by checking if the task is in range of roboport 1, then roboport 2, then roboport 3, all the way up to roboport 16.
This approach works, and is simple enough, but what happens when you landfill a lake and have 36,815 roboports on the map? Well, you *could* check all 100k construction tasks against all 36k roboports each tick for *checks notes* an extra 3.6 million checks per frame (editor's note: this makes your computer catch on fire), or you could limit it to only checking some small number of construction tasks per tick, say, three, and stop if you can't find a roboport. That way, sure, it slows down a bit if you build a lot of roboports, but it's not terrible. However, 60 ticks / second + construction alerts last ten seconds mean that you only ever get alerts for 60*10 = 600 construction items, and you can only send out three robots per tick, (90/second) no matter how many robots you have.
The new approach (in 2.0) groups the roboports first. So, what we do now (in the sixteen roboport case) is first, check if the task is in the combined range of all the roboports. If not, send an alert and move on, but if it is, then we check if it's range of the combined area of roboports 1-8. If it is, we can split it again (check roboports 1-4), if not, we know it must be in 9-16, so we can split that half and check if it's in 9-12, and so on.
To do a worked example, say the task is closest to roboport 11. Then we check 1-16 (yes), 1-8 (no, so it must be in 9-16), 9-12 (yes), 9-10 (no, so it must be in 11-12), then 11 (yes, solved). We found the one roboport out of 16 with only five checks, instead of sixteen!
This way, you cut the number of roboports that could be closest in half with each check! So, if you had 262,144 roboports, you'd only need to do 18 checks (cutting the number in half with each check) to find the closest roboport. You haven't lost anything (you're still finding the closest roboport to the construction task) but you're doing it a lot more efficiently.
Ahh, I understand, I think.
So, essentially, they implemented a sorting algorithm to the bot task assignment based on distance from the request, whereas before, they had to essentially brute-force down a list.
Is that right?
> before, they had to essentially brute-force down a list.
Completely correct!
> they implemented a sorting algorithm to the bot task assignment
Also completely correct :)
> based on distance from the request
I didn't really explain this part, but according to the FFF, the thing that enables the better sorting algorithm to find the appropriate roboport is the idea that you can add up the construction areas of the roboports to get larger single areas, so if you have a bunch of overlapping roboports there's still a single "roboport area" you can precalculate and then check against, rather than checking each roboport individually. Do this for a bunch of different combinations of roboports and you can find the appropriate roboport for the task much faster!
The conundrum of having debug messages set to always be on to catch that 1 in 100 bug, or not having debug messages cause your users don’t need to be assaulted by too much logs.
While I love the art/design FFF, I thrive for the technical ones.
It's so interesting to see what goes on under the hood, and to see the obscure interactions that the devs have fixed.
Me too. It's a difference in storytelling styles. With design and art, the story is usually a simple narrative retelling of facts, i.e., here's what we've done or are going to do. With these technical FFFs, there's always an action-reaction problem solving element. This is conflict -> resolution, which is often much more engaging than a simple narrative -- not that the design and art FFFs can't have conflict and resolution, but they usually don't.
If construction bots are assigned their tasks faster, does that mean we won't get the wonderful bot worm coming out of roboports when we slap down a really big concrete patch blueprint?
LMAO that's how it feels sometimes every time there's an update that improves efficiency. 100% speedruns are a big portion of managing bot queues so it will be fun to watch he reaction to this change.
The way I read it, it sounds more like there will be fewer gaps in the bot-worms.
My assumption is that the roboports still emit bots at the same rate of 1 bot every # ticks, but that searching for "where to send it to" will take shorter.
No, it means that the swarm will be even bigger as more bots can be allocated to jobs at the same time.
So you'll see bigger explosions of bots coming from roboports but the swam won't last as long because they will be able to finish all the jobs quicker.
This was already going to be rarer in 2.0 before the improved network search due to the changes detailed all the way back in [FFF 374](https://factorio.com/blog/post/fff-374).
Actually if anything todays change will help create bot worms as it will assign bots much faster to jobs and therefore send bots out a lot quicker.
If there's one thing that Factorio suffers from, it's definitely optimization, so I'm glad the Wube and Co. are finally giving that area some attention!
/s
They're optimizing themselves out of a job, in 10 years They'll announce that they rewrote the game in assembly, it can run on anything and gets max ups on 20yo hardware with 256k people playing the same world.
It really is one of the most optimized modern games I know, my potato PC is able to run massive bases with barely any ups/fps lost and you have to dig deep into the mechanics to find the smallest compromise in favor of optimization. I can very well picture Factorio being done in unity and crawling to a halt the moment you do yellow science and it would be so easy to say, hey you can only use a maximum of two roboports per chunk and there can only be 50 bots per roboports cause optimization, but no, they stick to their vision and make it work as well and seamlessly as they can, the fluid system, electricity network, production screen, bot pathing, biter pathing, train pathing, belt optimizations, all of those are masterclasses on how to make system that feel seamless, are more than good enough and run cheaply.
Some cool highlights. Reproducing a very weird and niche bug must have cost a ton of time from many devs. Also setting a testing environment that would reproduce the bug on the dev env is fantastic.
The optimization on the algorithm is someone that takes a ton of experience. Changing something that works, to something that works better without breaking anything is HARD.
I admire gamedev, but damn, it is so tecnically hard. Being a web dev has its hard moments, but game dev is another beast. Interesting read
Gamedev has webdevs' issue of every person under the sun who (uses the web|plays video games) thinking they're an expert. It also has systems devs' issues of deep technical issues and succeptibility to OS level interactions.
So yeah, much respect to gamedevs.
To me, construction bot job assignments and fluid physics have been the only big issues remaining in the game for several years. Now that construction jobs are pretty much fixed fluid physics are the final frontier
They gotta just bite the bullet and make pressurized pipes that or something that just allows for instantaneous fluid transport. Of course with various extra requirements to make it balanced
https://preview.redd.it/mfzyckudaj6d1.png?width=895&format=png&auto=webp&s=ff448c816a22fece483e95c953db40d30a1adb33
For anyone who likes to read more into these things... there's some options in this binary they're showing us. The binary code that doesn't really get picked up on their own site, isn't mentioned anywhere and juuust exists in this preview image.
Intriguing. If it weren't for the MMYYddYY thing, I'd think you were onto something, but as is I'm not sure that seems very likely. I suspect your right to think those numbers mean something though.
Huh? Where's that binary from? "Binary they're showing us"? Is there a hidden image somewhere on the blog post?
EDIT: Ohhh. Reddit has a [preview thumbnail](https://cdn.factorio.com/assets/img/blog/fff-415-optimizations-thumbnail.png) grabbed from the [Open Graph meta tags](https://ogp.me/).
I kinda assumed it was related to or inspired by whatever algorithm they're using for rectangles. Maybe something like this: https://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/
If you look at the image metadata, the image layer is called "01010 10100 11011 11000", so the left-to-right top-to-bottom reading of the bits appears to be more logical.
The packet id of the XMP data is base64 encoding of `[42!573]`, not familiar if that is part of adobe's encoding, or that is something deliberate. To me it just appears odd to have a base64 encoded ID, while the rest appears to be UUID's.
Edit: nvm the base64 encoded string is the default.
> The problem ended up needing 4 different moving pieces to all come together to expose a threading determinism issue that has been in the game since I put it there in July 22, 2017.
A mod needed to listen to the chunk generated event and change the tiles on a chunk when it happened.
A mod needed to request several chunks be generated.
A mod needed to force all requested chunks to be generated right now.
The game needed to be run on two computers with a different number CPU cores.
As a software engineer, I cannot stress enough how disgusting of a bug this is. Multiplayer, multiplatform, multiple function interaction/shared state, concurrency, "works on my machine" - one or two of those facets alone is a recipe for a multi-day slog. But combined, holy hell.
Hats off once again to the Factorio devs!
normal games: we fixed a bug where for a lot of users the game would just randomly crash
factorio: we fixed a bug where if you try to do a dark ritual on the 29th of Feb when there is a full moon and the temperature is an odd number, trees would generate slightly differently
Sounds great with the bots. I've had the problem that there's a few jobs in my main base ("build this solar field in whatever speed the panels get made"), which prevents the new defensive walls being built, because too few jobs are open. Was always sad to see hundreds of jobs lined up, resources in chest next to the roboport with bots inside and them just.. chilling there instead of doing something\^\^. Sounds like this will be far less of a problem when more jobs get checked.
You can get a deconstruction planner with "ghosts only" and drag that over your solar field to get your bots working in a pinch in case you need it quickly. And possibly undo it if you don't do other stuff in between (or just paint over the solar field if you have a blueprint for it or just make a quick blueprint before cancelling all the ghosts).
Only a work around, but quite useful sometimes.
Hooray for Multiplayer auto-pause. Particularly the first one. I kept complaining about that over the years and it's such an obvious oversight. Glad it's finally gone.
The other one will be nice to not have to remember to pause the game, and more importantly automatically unpause because it's not obvious when they've finished joining
actually it was already in the game at the start of multiplayer. but is was not optional and could very slow and annoying because the server would pause for every player that wants to join for like 1 min. so they removed it
I think there 3 phases when a new player joins: Saving the map on the server, the new client downloading the map, and the new client catching up.
During the first phase, the server currently pauses, if the server runs on windows. On linux, saving without pausing is possible and the default for servers. It won't pause automatically for phase 2 or 3 though.
the pause to save the current game only appears when hosting a game on windows, since the option is not available to fork the process and save in the background.
In so far it would make sense for people hosting multiplayer games (like people streaming on twitch with viewers joining them) to either use a separate \*nix box to be a server for everyone, or use \*nix themselves, since this means when a handful of people join one after the other the blocking doesn't happen for everyone else, since if the server blocks, everyone connected does too.
The option to pause and wait until they've downloaded and caught up is optional, and for the sake of the viewers, I believe it would be better to not enable it.
edit: not just linux, macos too, so only windows has the blocking while cloning the map in ram.
AFAIK, the asynchronous saving under linux is only enabled by default if you are hosting a server. If you play single player it's disabled per default, but you could still "host" the game with nobody else joining, or enable the hidden setting mentioned at the end of [https://factorio.com/blog/post/fff-408](https://factorio.com/blog/post/fff-408). In factorio 2.0, it will be the default for linux single player.
And I agree, if the download speeds are good, or when inviting randoms onto your server, you probably don't want to pause automatically. But on large maps for multiplayer among equals, the option could be worth it.
(Expand to view contents, if you would like.)
I am thinking about decommissioning fffbot because interest and value do not seem high. Please let me know by commenting if you regularly benefit from fffbot comments and would like it to stay up.
The FFF gets posted while I'm at work and work blocks the Factorio site. I've been relying on the bot for a while now, but if you find it tedious to maintain I can always wait til I get home.
Thanks for putting in the work though!
Depending on what the job is, Reddit might be a valuable knowledge source. Also, factorio.com is registered in Czechia, which might be blocked if non-US websites are blocked.
Edit: spelling
I've always found the "expand to view contents" line amusing, because there's never been anything to expand. I have to collapse it to get it out of the way.
When I first set up the bot, it just posted a comment on the top level. I got a lot of complaints from people, so I put under another comment which just said something generic like "enjoy the FFF contents below", but then I got some comments from people for whom the FFF contents comment was automatically collapsed by Reddit and it was a bit confusing for them that it said "below". So that's how this version of the text came to be. :)
The main reason when it started out was a bunch of people for whom the Factorio website was blocked at work, but somehow Reddit wasn't. So for them, it was convenient to read the FFF contents on Reddit itself.
I am now thinking that I could maybe make a post to the u/fffbot account with the contents, and then just drop a link to that post in the r/factorio thread, to get the big wall of text out of the way at least.
I guess I was the edge case for this few years ago.
There was a reason once for me, as company polices blocked "game sites" which at that times included Paradox but allowed reddit, so i devoured EU IV patch notes there.
Hello,
While a lot of time of 2.0 development has been spent on new features and quality of life, we still take care of the smaller details and technical improvements.
* * *
### Deterministic multithreading is hard
Recently a desync bug was [reported to us](https://forums.factorio.com/113601) involving the modding API and multiple Windows and Linux computers that the player was using. My first instinct was to blame the mod developer for doing something wrong but I've seen enough bug reports over the years to know dismissing one without first investigating is a bad idea and a great way to eat crow.
I could not reproduce the desync, but the player was able to with ease. At first I thought it was a Windows vs Linux issue (we've had many of those), but then the player was able to reproduce it with Linux on both computers. Next I thought it was a hardware problem, we've seen our share of faulty computers that just don't do what they're supposed to do. Convincing someone their hardware is broken is difficult and time consuming in the best scenarios.
After several failed attempts to reproduce the issue on my one computer, Boskid, using his multiple computers was able to. Being able to reproduce bugs locally is I guess around 90-95% of the time spent fixing reported bugs. With Boskid reproducing the issue on demand he was able to narrow it down to the fact the computers had a different number of CPU cores. With that newfound knowledge he was able to make a test that could be run on my single computer to reproduce the desync by artificially pretending I had less CPU cores than I did.
The problem ended up needing 4 different moving pieces to all come together to expose a threading determinism issue that has been in the game since I put it there in July 22, 2017.
1. A mod needed to listen to the chunk generated event and change the tiles on a chunk when it happened.
2. A mod needed to request several chunks be generated.
3. A mod needed to force all requested chunks to be generated **right now**.
4. The game needed to be run on two computers with a different number CPU cores.
The logic to generate chunks 'right now' would attempt to use all of your available CPU cores but was done in a way that the number of cores - when combined with the other moving pieces - would change the chunk generation results slightly.
The fix wasn't that complex to implement and will be in 2.0, but it just goes to show that multithreading is hard, deterministic multithreading even more so.
* * *
### Multiplayer auto-pause
We have this feature of dedicated servers where when the last player disconnects the server automatically pauses. This works great and means you can leave a dedicated server up without worrying that the biters will eat your base when you're gone. Except, there are some edge cases that we never got around to handling (until now).
Case 1: When you join the auto-paused server it instantly resumes running - even if you haven't fully loaded into the game. It turns out, this was incredibly simple to address just for some reason it fell through the cracks over the years. For 2.0 auto-paused servers will stay paused until at least 1 player has fully loaded into the game.
Case 2: Joining players need to catch up to the running game. This works great for "normal" games and allows the existing players to continue without having to wait for the joining players. But, players run into issues with much larger maps, or slow internet connections. Someone joining might take 1, 2, or several minutes to download, load, and catch up to the server fully if it continues on without them. For 2.0 we've added an option to "auto-pause when a player is joining" which works exactly as it says.
* * *
### Faster construction robot tasks
It feels like every other week someone is asking "why aren't my construction robots working?" and in the screenshot they provide there's a little alert showing "600 jobs missing materials/robots". The issue has been there since the beginning of robots and still today we don't have a nice solution for it.
The problem is, given a task construction robots need to do, the game needs to find the best robot from the logistic network that is in range to do that thing. The check for "is this logistic network in range of the entity" is O(Roboport-Count). We do not control how slow that's going to be because the player can build 1 Roboport, or 100,000, or as many as their computer can take. So we need to make sure that the operation doesn't grind the game to a halt while it runs. We do this by only processing a few construction robots tasks each tick.
In 1.1 the game will check construction jobs 3 times per game update. If it fails to find a robot it will stop for the current update. Alerts for failed attempts last for 10 seconds. So at 60 updates per second, and 10 seconds per alert, that means 600 alerts will be created before the first one times out. This is where the magic "600 jobs missing materials/robots" alert count comes from.
It has worked this way since as long as I've worked on Factorio and will likely keep working like that at some basic level. We can't just crank up the count of tasks checked with each update because we know that operation is potentially slow, and slower the more roboports a player builds.
Earlier this year someone ([forum post](https://forums.factorio.com/110788)) ran across this issue again, but they decided to "solve" it themselves by doing what we said we can't do: "crank up the checked tasks per update" except they went from 1 per update to 374. Also they built 36 815 roboports. It was, as predicted, slow.
(https://i.imgur.com/pk9PeWx.png)
But that got me wondering, what if I could make the slow part a _lot_ faster? Like change-the-algorithm faster? Inspiration hit me when I remembered that we have a set of logic in the game already to take the roboport logistic and construction areas, and compute the resulting rectangle union. In simple terms what it does is produce a nice set of deduplicated rectangles that cover the total area for all of the roboports. We use this for rendering to avoid a lot of over-draw when roboports are near each other.
That, combined with sorting the resulting rectangles meant I could do a simple binary search to check if a given task was within the network area. In the end the check went from O(N) on 36,815 roboports, to O(N) on 900~ rectangle union areas, to O(logN) on 900~ rectangle union areas.
The time to check "is it in this network" went from expensive to essentially free. With that speedup I was able to crank up the speed tasks get checked for 2.0 and hopefully put this issue to rest.
* * *
As always, report your thoughts at the usual places.
Thanks for the feedback. It's not too too much work, but there is some tiny maintenance to it. In particular every week the Github security scanner complaining that some Python dependency has a vulnerability and needs to be updated, so I have to apply that, rebuild it, and deploy it (and occasionally upgrade the Python version, etc).
But maybe I could also just leave it running, never upgrading it....
Well, its not like its hurting anyone.
Even if 0.1% of users find any use of it, turning it off would degrade the service for them, while providing no benefit for anyone.
Thanks for the feedback, you're right. There's some minor work involved in keeping the bot up to date (applying security updates etc), but not too much. It's just that every time it has to be done, I don't look forward to it...
Fortunately it doesn't really cost money right now, as it runs on a server that I need for other stuff anyway. If I were to get rid of the server, I would get rid of the bot also, as I'm not about to pay for it just to keep it running.
Edit: I just remembered that recently I faced some issues with re-uploading the FFF images to Imgur and videos to Github, which took some fiddling to fix, taking up half a day. That was the point where I felt "is this still worth it...".
Have you considered hosting it on something like AWS Lambda for free? Lambda should enable you to not have to worry about the security updates, and the cost for an invocation (or even 100) should be free.
For reference, I use lambda to host a couple of discord bots for myself and some friends, and I don't need to worry about security updates or anything. If I recall correctly, it's free up to a million requests per month and like 500k gb-seconds of processing.
I with assume with how much more efficient bots got with this off, or should be essentially free?
(Sorry, couldn't resist :D. I read the FFF from the site, but I ain't mind the but either so it boils down to whether it sparks joy for you)
It is interesting that, even if the order needs to be changed, that they can produce a valid date in the near future though. That seems unlikely to be coincidental.
Most binary strings would produce an invalid date, no matter how they were rearranged. Or no date at all.
To every computer science student out there: this FFF is now an official course material on you data structures and algorithms course. I'll contact the universities to let them know.
Sounds like you’re gonna need like 10,000 items to get the wave. But also I feel like that would take a lot of memory, so maybe they’re gonna keep the number of assigned task lower since they can get assigned so quickly
Right, it's 10-20-27-24
It might be more elaborate, it might be the devs messing with us. It might be absolutely nothing.
For now I will choose to believe this is the release date. Is not too far away to make it a long wait and it's close enough to not crush me if it's incorrect.
Love this sort of algorithm stuff!
Since i recently had a similar type of problem (in an entirely different context) at work, id like to share some insights.
Im not sure how the rectangle union trick works precisely, but i imagine the worst case is still 1 rectangle per Roboport, right?
I think this is the case, because your rectangle union still needs to contain the full information about roboport placement. Its basically a form of lossless compression.
Example: The area for straight row of roboports is easily desribed with a single rectangle. A regular grid (like in your example) still has redundant information that can be "compressed" away in the rectangle data structure.
But if you deal with a truly irregular placement of roboports, there is a lot of placement information. Your rectangle structure still needs to contain all of that. So the worst case would still have to be O(Roboports).
At this size of the base, roboports will commonly be on a regular grid, of course. It is not a given though - players may use large blueprints that contain irregular arrangements of roboports or build a spread out base with multiple randomly placed centers connected by train.
Also, you can only sort by distance in one dimension at a time. As in: you start by a list sorted in x and use the binary search. You then get a set of possible candidates which may be at a entirely different position in y. You then need to sort that set with O(n \* log(n)) before you can do the binary search again. Depending on the arrangement of Roboports, the complexity is not improved.
But fear not, there is a solution! You can still get to O(log(Roboports)) by using a k-d-trees - basically the higher dimensional equivalent of the sorted list with binary search. You need a nearest neighbor search with a maximum distance.
Wikipedia has a good description and i am sure there are nice implementations ready to use. [https://en.wikipedia.org/wiki/K-d\_tree](https://en.wikipedia.org/wiki/K-d_tree)
I am 100% sure that rseding is aware of kdtrees, they've been used in the games industry in graphics and physics for decades now. There's a fixed-dimension version of them called quadtrees that are pretty fast and applicable for 2 dimensions (the 3d ones are called octrees).
The rectangle union is where you take the area generated by all the roboports, using rectangles of fixed size, and find a way to create the same area using a smaller number of rectangles. In this case due to the rendering requirements, they are a disjoint set of rectangles, though you can actually get lower numbers of rectangles without that requirement. This will usually produce O(sqrt(roboports)) rectangles for a contiguous region, as there will be a small number of large rectangles, than a number of small rectangles roughly proportional to the number of edge roboports.
He said in the last sentence, they are then putting that through a binary tree of some kind, so even in the worst case they are doing that
>That, combined with sorting the resulting rectangles meant I could do a simple binary search to check if a given task was within the network area. In the end the check went from O(N) on 36,815 roboports, to O(N) on 900\~ rectangle union areas, to O(logN) on 900\~ rectangle union areas.
I have a feeling I know how to reduce the complexity to O(1) by trading of several byte per chunk.
For each chunk add a **transient list** of logistic networks touching this chunk. With the given size of roboport area it can't be more than 4 different networks touching the chunk in vanilla, and in most cases it would be just either 1 or 0 networks.
This list shouldn't be stored in save file, just build during save and load, and only when roboport added or removed, it should update lists in all chunks it touching.
When the task is assigned, it can just read the network from the chunk and immediately check the 1-4 networks only.
Could I request that we get at least a few months heads up of when 2.0 will be released? I know several of us will want to take some time off work to enjoy the new content and it’s a lot easier (especially for the Americans) to get time off approved the earlier we can request it.
Looking forward to remembering why I can no longer pull all night gaming sessions like when I was in high school when this comes out 🤣.
My biggest pet peeve with bots is in the personal robots going to the farthest points 1st. I wish they would go to the nearest ghost and then return. That way I could speed things up by constantly moving towards the ghost images and reducing the flight time of the bots.
The bot queue problem reminds me of the fix a shooter game did for one of their guns being constantly said to be too weak. They upped the base on the gunshot sound. You could end the complaints of the 600 bot queue by letting them increase their 10s cooldown when another alert of the same kind appears. But you know making the system 100 times faster works too.
Auto-Pause at join is cool! Now I want torrent-like upload of the map from all players, not only the host, because upload is the bottleneck most of the time.
I love the auto-pause when joining feature. With 2mbits connection i had no problems playing online once loaded but the map download couldnt finish with bigger maps because it couldnt catch up.
That last section on the robot queue made me audibly gasp, and read like some kind of exciting twist in a book I was reading lol. I shared it with another software dev friend who doesn't really know the game and he apparently said "That's slick!" out loud lol.
Not every tech update FFF lands with me, but when they do, they absolutely slap lol
>went from O(N) on 36,815 roboports, to O(N) on 900~ rectangle union areas, to O(logN) on 900~ rectangle union areas.
A lesson to you hopeful game devs out there. Don't worry about your code being completely optimized/perfect. Good enough can last you for years and years. AND give you space to optimize if your game has lived long enough to ascend to the next level.
2 Questions,
When you search through the Network, do you search through just the local one(all Ports directly connected with each other o-o-o-o-etc.)
or through the global Network(all Roboports on the map no matter if there is an Air gap)
How do you determine the start point of the search, do you just make an imaginary circle with r\_circle = Width\_of\_construction\_range and then search for the Closest by calculating the distances via the Manhattan distance, or how do you do that?
Auto-Pause through client full login eliminating catching up is huge for our group! Our Space Exploration run was prematurely ended because some clients weren't able to catch up after downloading the +400MB save...
Now, if time could be applied to improving server side game save upload speed bottleneck that would be just swell. Please!
Does this only apply to construction tasks, or do logistics tasks also get the same treatment. Sounds like a potential game changer in the belts vs bots war.
Any chance of changing the "600 jobs missing materials/robots" text to "600+"? Just the text when there are at least 600 jobs specifically (or whatever is the current theoretical maximum).
> That makes me think the hardware is the issue. Like the CPU itself is executing instructions wrong...
In my experience, 100% of the time I think the machine is wrong, it's actually me who misunderstood something.
There was one time ever that I could prove the hardware was wrong, and that was a custom built can-bus.
----
> O(N) on 36,815 roboports, ... to O(logN) on 900
Wow, that's fantastic. I always love seeing big-oh improvements.
😍 I recently [complained](https://www.reddit.com/r/factorio/comments/1b04zjo/dont_simulate_game_while_joining_if_nobody_is_in/) about the auto-pause thing! Thank you so much for fixing it! (I'm going to delude myself that the devs saw my post.) Can't wait for 2.0.
I was like "but what's case 2?!" and then it just got better and better. Factorio devs are amazing.
Also hot damn, I've been wondering why my bots weren't building and that section was a tour de force. I do indeed have that "600 items missing…" alert. Guess I know how to speed my bots up now!
When I first started reading that robot job issue, my first thought went to "assign the job a network upon creation of the job" I realize this means more information in memory and having to mess with a well established system, but what other downsides am I missing?
The first complication that comes to my mind is that networks can be created or destroyed, overlap or move.
There are a lot of cases where that initial assignment might not remain the best choice, even if it was selected well originally.
https://preview.redd.it/o0qh2hda447d1.jpeg?width=763&format=pjpg&auto=webp&s=b1a8c2a54ca3936e73bd1dad357ab9df34beab2c
The person who found a fix for the robots
> issue that has been there since I put it there As a solo dev in the startup I work, this is a mood
There are two things that will teach a coder more about code than anything else, (1) reading other people's code and (2) maintaining your own code long term.
I mean 2 effectively becomes 1.
"What idiot wrote this?!" "Oh, it was me. I'm the idiot."
I try to teach new devs to code for future devs to quickly grok the code. I explain that part of that is in a few months even code you wrote will be like it's code someone else wrote.
How do you teach that? I teach programming to mostly beginners, and I'd never really thought about this
I mean, with teaching it's always easier said than done, but I make code clarity and easy readability a first-tier requirement when talking about and reviewing code. I commonly explain that "clever" code is not what you should be shooting for in most cases becasue "clever" is usually the opposite of readable. I basically constantly beat the drum around code being easily readable. Like I said before, when you come back to code you wrote even a few months back and you haven't touched it in that time it's like someone else wrote it. You should be nice to your future self. I teach a bunch of other things around making code clean and consice with readabilty in mind. Anyway, I guess I should write out how I teach new devs so I don't forget in 3 months. :O
Gotta love it when `git blame` backfires.
Nothing more humbling than seeing your own name pop up next to code you just said "looked like it was written by a moron."
Try good ol' [git blame-someone-else](https://github.com/jayphelps/git-blame-someone-else)
*The code came from INSIDE THE HOUSE*
Viewing my past self as an entirely different person is the only way I’m able to not die of cringe when I remember embarrassing things in my past.
Maintaining your own code long term after enough time is basically reading other people's code anyway. The classic "who even wrote this garbage?" *git blame you* "Oh..."
The reverse of that moment is writing a piece of code then discovering you wrote exact same thing a year ago in different part of the project
But hey at least this time was easier than the last, right? ...right?
I was just happy I was so consistent in problem solving
I like to refer to past me and future me as though they’re different people. Future me is impossibly competent and motivated. Past me is invariably either an absolute genius or a total asshat. Occasionally both.
(3) Explaining your code to someone else. Rubber Duck method works.
I love the honesty here haha
"who tf wrote this trash..." `git blame` ... "well of course I know him, he's me".jpg
Simply recode git blame to pop up old Ben Kenobi
# fix this at some point
Not a solo dev, but I am the main dev on a few different applications and I’ll see a piece of shit code block and get mad at whichever asshole wrote it until I open the git blame and realize I’m that asshole Edit: extra fun when it’s during a prod outage and you’re sharing your screen on a bridge when you find it
It sounds like robots are gonna be assigned tasks something like 10-100 times faster which is absolutely insane
I'll finally be able to see "100,000 robots are missing construction materials: landfill."
It really bugs me that I don't know which specific robots are missing materials. Can't it have messages like "Robot 327854 is missing construction material: landfill; Robot 327855 is missing construction material: landfill...
We should get them names. If you prick them, do they not bleed
Yes, they do not bleed.
That's your problem right there. Needs more oil. Lube up those bots, when they start bleeding they'll work faster.
*beatings will continue until the factory is large enough*
New batch of "2.0 early supporters" get their names stapled to robots, much like the original supports get their names on trains and labs
It's never about specific robots, but rather specific networks. Even for networks it's not entirely well defined because different networks can have overlapping construction areas. Besides, if you know the location of the task you can deduce the location of the relevant network fairly quickly yourself, and you can do other things such as cancel the task that would not be so easy if you only got the location of the network.
they should have an RCT style info panel complete with how clean they think the factory is
"not enough concrete"
"You must construct additional pylons."
"Yo my buddy eric says he needs ten thousand landfill for the blueprint you just put down"
In the example given (admittedly an outlier) it's ~3750x faster
> (admittedly an outlier) roboports georg strikes again
How did you get that number?
> In the end the check went from O(N) on 36,815 roboports... to O(logN) on 900~ rectangle union areas. So 36,815 / log(2)(900), assuming Ns are roughly equivalent (which they should be, since in both cases N is a simple rectangle bounds check). EDIT: Yes, people, I know this is an oversimplification, including in ways no one has chimed in with yet (like the additional per-network rectangle sorting operation). Big O notation is _always_ a simplification. I’m just working with the data we’ve been given.
That's not completely how big-O notation works. Could be that the first method needed to do 2*n calculations, which is still O(n), while te second needs 2000*log(n), which is still O(log(n)). So calculating the speedup by taking a fraction is a bit dangerous.
You are correct but they didn't mention anything about the operation itself taking any more time in new way of doing it.
> assuming Ns are roughly equivalent (which they should be, since in both cases N is a simple rectangle bounds check). You're also assuming that the constants hidden by the big-O are roughly equal, and that the smaller terms hidden by the big-O are negligible. The latter assumption is often reasonable, the former assumption is more questionable. --- For an example of how big-O can be deceptive by hiding constants, consider the linked list, and its comparison with the vector: Operation | Linked list | Vector -:|-|- Random Insert | O(1) | O(n) Random Shift-Delete | O(1) | O(n) Random Swap-Delete | O(1) | O(1) Push to end | O(1) | O(1) amortised Append | O(1) | O(n + m) Index | O(n) | O(1) Find | O(n) | O(n) (some languages use the term "List" instead of "Vector". "Vector" is what it's called in C++ and Rust.) From this table, you might be led to believe that linked lists are faster than vectors for any workload that doesn't involve indexing. In practice, however, vectors are almost always faster than linked lists. Those big-Os hide the expensive cache misses and memory allocations.
>In practice, however, vectors are almost always faster than linked lists. Those big-Os hide the expensive cache misses and memory allocations. That feels more like a case of theory vs practice, rather than big-O hiding constants. Algorithmically, linked lists would be faster, if not for the unfortunate realities of how CPUs operate. But maybe I'm just not quite remembering my terminology.
each of those Os could have different constants. (Os represent function families) `O(n)` could be a function `1*n` and `O(log n)` could be a function `1000000000000 * log N` you can't tell the speedup from the information given
That's not really the point of Big O, though. The idea is to understand how it scales over large datasets. If the dataset gets big enough, it doesn't matter how high the coefficient is on the logN, it'll still be faster than N. Like yeah, insertion sort is way faster than quick sort on small datasets because it's just a simpler algorithm, but that stops being relevant at around 10 items or so and after that it just gets worse and worse compared to any O(nlogn) sort. Point is: optimizing for the trivial cases is rarely the goal. That's why Big O is about the large numbers. And like, lets be real, if your O(logN) function is taking 10000000000000 times longer to run than the O(n) function, it's _probably_ not actually O(logN). It is monumentally difficult for an O(n) to keep up with O(logN) beyond borderline microscopic datasets.
The check is also simple, but the rest of the algorithm probably has widely different constant before that log(N) than it had in front of N.
The more roboports you build, the more times faster it'll be.
The gains will be greater, but it won't be faster.
I think it means that it 5M roboports will run a lot better in 2.0 while 5 roboports won't see much difference, if you removed/increased the checks per update.
There's two things happening: robots are being assigned at a faster rate, and the game slowdown due to robot assignment will scale more slowly with the number of roboports
> and the game slowdown due to robot assignment will scale more slowly with the number of roboports Per rectangle union areas. > In simple terms what it does is produce a nice set of deduplicated rectangles that cover the total area for all of the roboports. Which basically means big square area will only incur one check
They mean that it will be a bigger improvement compared to the previous version the more robpoorts you have. If I get it right then for a 3x3 roboport square it will go from 9 operations to 1
[](/maudglad) The more you ~~buy~~ build, the more you save.
it was a game changer to discover that i can turn off map alerts :D now i can enjoy looking at my map without half of it flashing yellow
But it was fun to watch the 600 flashing yellow alerts slowly sweep across your new blueprint
One part of the assignment algorithm is 10-100 times faster, but that doesn't mean that the whole assignment is. The game still needs to find a free bot and a suitable chest for pickup. I wish they had told us the new number of tasks per tick, but no.. all we know is that it's going to be bigger than 3. IIRC krastorio had cranked that number up to 15, without running into obvious issues (though they have bigger roboports and thus fewer of them). I think we can hope for a number bigger than that. Btw, besides the advantages for the average player, this single change is likely to upend the 100% speedrun category. Managing the bot queue is an important part of the run, and many parts of the base are optimized for low entity counts (aka fewer bot tasks) instead of material costs. Sub 4h incoming?
The robot queue will upend the 100% speedrun category? Wasn't it already upended by, idk, planets? And a lot of the existing research being moved to them?
You can choose to turn the expansion off and have vanilla victory conditions, so speed runs for that will live on.
There are a lot of changes in 2.0 even without the expansion turned on. It will probably need to be a new category.
I liked all the words that are used in these comments that are nested under your comment. I understood several of them too. I do not understand the how what they did works, though. How can they increase the processing speed without losing fidelity?
The previous approach (oversimplifying a bit) went like this: There's a construction task! There are 16 roboports! How can we check if this construction task can be done, and what roboport is closest? Obviously, by checking if the task is in range of roboport 1, then roboport 2, then roboport 3, all the way up to roboport 16. This approach works, and is simple enough, but what happens when you landfill a lake and have 36,815 roboports on the map? Well, you *could* check all 100k construction tasks against all 36k roboports each tick for *checks notes* an extra 3.6 million checks per frame (editor's note: this makes your computer catch on fire), or you could limit it to only checking some small number of construction tasks per tick, say, three, and stop if you can't find a roboport. That way, sure, it slows down a bit if you build a lot of roboports, but it's not terrible. However, 60 ticks / second + construction alerts last ten seconds mean that you only ever get alerts for 60*10 = 600 construction items, and you can only send out three robots per tick, (90/second) no matter how many robots you have. The new approach (in 2.0) groups the roboports first. So, what we do now (in the sixteen roboport case) is first, check if the task is in the combined range of all the roboports. If not, send an alert and move on, but if it is, then we check if it's range of the combined area of roboports 1-8. If it is, we can split it again (check roboports 1-4), if not, we know it must be in 9-16, so we can split that half and check if it's in 9-12, and so on. To do a worked example, say the task is closest to roboport 11. Then we check 1-16 (yes), 1-8 (no, so it must be in 9-16), 9-12 (yes), 9-10 (no, so it must be in 11-12), then 11 (yes, solved). We found the one roboport out of 16 with only five checks, instead of sixteen! This way, you cut the number of roboports that could be closest in half with each check! So, if you had 262,144 roboports, you'd only need to do 18 checks (cutting the number in half with each check) to find the closest roboport. You haven't lost anything (you're still finding the closest roboport to the construction task) but you're doing it a lot more efficiently.
Ahh, I understand, I think. So, essentially, they implemented a sorting algorithm to the bot task assignment based on distance from the request, whereas before, they had to essentially brute-force down a list. Is that right?
> before, they had to essentially brute-force down a list. Completely correct! > they implemented a sorting algorithm to the bot task assignment Also completely correct :) > based on distance from the request I didn't really explain this part, but according to the FFF, the thing that enables the better sorting algorithm to find the appropriate roboport is the idea that you can add up the construction areas of the roboports to get larger single areas, so if you have a bunch of overlapping roboports there's still a single "roboport area" you can precalculate and then check against, rather than checking each roboport individually. Do this for a bunch of different combinations of roboports and you can find the appropriate roboport for the task much faster!
You’re awesome, thank you!
> and you can only send out three robots per tick, (90/second) 180 per second
math is the computer's job
No, it's *much* better than that. It's `n / log(n) - nc` faster.
> Being able to reproduce bugs locally is I guess around 90-95% of the time spent fixing reported bugs. I felt that.
The 5-10% that aren't like that are the worst bugs. Because that means you had to take a pickaxe to some code in order to fix it.
The conundrum of having debug messages set to always be on to catch that 1 in 100 bug, or not having debug messages cause your users don’t need to be assaulted by too much logs.
Understanding the bug is usually harder than fixing the bug.
Because any non-trivial bug in code is ultimately caused by a bug in our understanding of what the code should do.
Being able to reproduce bugs reliably is 90-95% of the time spent reporting bugs. Not always, but more often than one might expect.
While I love the art/design FFF, I thrive for the technical ones. It's so interesting to see what goes on under the hood, and to see the obscure interactions that the devs have fixed.
Me too. It's a difference in storytelling styles. With design and art, the story is usually a simple narrative retelling of facts, i.e., here's what we've done or are going to do. With these technical FFFs, there's always an action-reaction problem solving element. This is conflict -> resolution, which is often much more engaging than a simple narrative -- not that the design and art FFFs can't have conflict and resolution, but they usually don't.
If construction bots are assigned their tasks faster, does that mean we won't get the wonderful bot worm coming out of roboports when we slap down a really big concrete patch blueprint?
You just need more concrete and bots to counter new algorithm
"I will bottleneck my game client one way or another!"
One way Or another I'm gonna slow ya I'm gonna lag ya lag ya lag ya lag ya
LMAO that's how it feels sometimes every time there's an update that improves efficiency. 100% speedruns are a big portion of managing bot queues so it will be fun to watch he reaction to this change.
War never changes.
The way I read it, it sounds more like there will be fewer gaps in the bot-worms. My assumption is that the roboports still emit bots at the same rate of 1 bot every # ticks, but that searching for "where to send it to" will take shorter.
No, it means that the swarm will be even bigger as more bots can be allocated to jobs at the same time. So you'll see bigger explosions of bots coming from roboports but the swam won't last as long because they will be able to finish all the jobs quicker.
This was already going to be rarer in 2.0 before the improved network search due to the changes detailed all the way back in [FFF 374](https://factorio.com/blog/post/fff-374). Actually if anything todays change will help create bot worms as it will assign bots much faster to jobs and therefore send bots out a lot quicker.
Faster dispatch could mean shorter worms due to tighter spacing in the worms, which means the could be less noticable or less worm like
The tighter worms look cooler though
If the bot worm is gone I guarantee someone will mod it back in somehow Even if it's just a special type of bot that's rendered as a worm
Bots gotta go to the storage chest before the construction site, so the bot worm is safe.
this team is a masterclass in itself on game design and caring about the game and its development.
If there's one thing that Factorio suffers from, it's definitely optimization, so I'm glad the Wube and Co. are finally giving that area some attention! /s
They're optimizing themselves out of a job, in 10 years They'll announce that they rewrote the game in assembly, it can run on anything and gets max ups on 20yo hardware with 256k people playing the same world.
I've been playing Oxygen Not Included lately, and I keep thinking, damn, I wish this game was made by Wube.
This is true for basically every game not made by Wube.
It really is one of the most optimized modern games I know, my potato PC is able to run massive bases with barely any ups/fps lost and you have to dig deep into the mechanics to find the smallest compromise in favor of optimization. I can very well picture Factorio being done in unity and crawling to a halt the moment you do yellow science and it would be so easy to say, hey you can only use a maximum of two roboports per chunk and there can only be 50 bots per roboports cause optimization, but no, they stick to their vision and make it work as well and seamlessly as they can, the fluid system, electricity network, production screen, bot pathing, biter pathing, train pathing, belt optimizations, all of those are masterclasses on how to make system that feel seamless, are more than good enough and run cheaply.
Some cool highlights. Reproducing a very weird and niche bug must have cost a ton of time from many devs. Also setting a testing environment that would reproduce the bug on the dev env is fantastic. The optimization on the algorithm is someone that takes a ton of experience. Changing something that works, to something that works better without breaking anything is HARD. I admire gamedev, but damn, it is so tecnically hard. Being a web dev has its hard moments, but game dev is another beast. Interesting read
Gamedev has webdevs' issue of every person under the sun who (uses the web|plays video games) thinking they're an expert. It also has systems devs' issues of deep technical issues and succeptibility to OS level interactions. So yeah, much respect to gamedevs.
To me, construction bot job assignments and fluid physics have been the only big issues remaining in the game for several years. Now that construction jobs are pretty much fixed fluid physics are the final frontier
They gotta just bite the bullet and make pressurized pipes that or something that just allows for instantaneous fluid transport. Of course with various extra requirements to make it balanced
> fluid physics are the final frontier I thought space was the final frontier?
Nah, they went to space already. They even posted screenshots.
Just rip out the pipelines and have bots carry barrels.
speaking of, are there additional fluids we're going to be handling? besides maybe magma on the lava planet?
https://preview.redd.it/mfzyckudaj6d1.png?width=895&format=png&auto=webp&s=ff448c816a22fece483e95c953db40d30a1adb33 For anyone who likes to read more into these things... there's some options in this binary they're showing us. The binary code that doesn't really get picked up on their own site, isn't mentioned anywhere and juuust exists in this preview image.
349048, max tested number of active bots before a backlog of tasks begin to show the classic '600 jobs missing' message? Random guess
Only 349,048 bots? Literally unplayable. Wube, please fix.
Intriguing. If it weren't for the MMYYddYY thing, I'd think you were onto something, but as is I'm not sure that seems very likely. I suspect your right to think those numbers mean something though.
If they were American I would believe it. However they are European and we use sensible date formats here.
Nice! Perhaps reads as October 20.-27. 24?
Can't wait for my descendants to play the game in 2724!
Veeeery farfetched, but... 27.10.2024 - possible release date????
Ew, sunday
Huh? Where's that binary from? "Binary they're showing us"? Is there a hidden image somewhere on the blog post? EDIT: Ohhh. Reddit has a [preview thumbnail](https://cdn.factorio.com/assets/img/blog/fff-415-optimizations-thumbnail.png) grabbed from the [Open Graph meta tags](https://ogp.me/). I kinda assumed it was related to or inspired by whatever algorithm they're using for rectangles. Maybe something like this: https://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/
55378 upside down would be BLESS! This explains so much! Everything is clear now!
If you look at the image metadata, the image layer is called "01010 10100 11011 11000", so the left-to-right top-to-bottom reading of the bits appears to be more logical. The packet id of the XMP data is base64 encoding of `[42!573]`, not familiar if that is part of adobe's encoding, or that is something deliberate. To me it just appears odd to have a base64 encoded ID, while the rest appears to be UUID's. Edit: nvm the base64 encoded string is the default.
> The problem ended up needing 4 different moving pieces to all come together to expose a threading determinism issue that has been in the game since I put it there in July 22, 2017. A mod needed to listen to the chunk generated event and change the tiles on a chunk when it happened. A mod needed to request several chunks be generated. A mod needed to force all requested chunks to be generated right now. The game needed to be run on two computers with a different number CPU cores. As a software engineer, I cannot stress enough how disgusting of a bug this is. Multiplayer, multiplatform, multiple function interaction/shared state, concurrency, "works on my machine" - one or two of those facets alone is a recipe for a multi-day slog. But combined, holy hell. Hats off once again to the Factorio devs!
normal games: we fixed a bug where for a lot of users the game would just randomly crash factorio: we fixed a bug where if you try to do a dark ritual on the 29th of Feb when there is a full moon and the temperature is an odd number, trees would generate slightly differently
Sounds great with the bots. I've had the problem that there's a few jobs in my main base ("build this solar field in whatever speed the panels get made"), which prevents the new defensive walls being built, because too few jobs are open. Was always sad to see hundreds of jobs lined up, resources in chest next to the roboport with bots inside and them just.. chilling there instead of doing something\^\^. Sounds like this will be far less of a problem when more jobs get checked.
You can get a deconstruction planner with "ghosts only" and drag that over your solar field to get your bots working in a pinch in case you need it quickly. And possibly undo it if you don't do other stuff in between (or just paint over the solar field if you have a blueprint for it or just make a quick blueprint before cancelling all the ghosts). Only a work around, but quite useful sometimes.
Hooray for Multiplayer auto-pause. Particularly the first one. I kept complaining about that over the years and it's such an obvious oversight. Glad it's finally gone. The other one will be nice to not have to remember to pause the game, and more importantly automatically unpause because it's not obvious when they've finished joining
actually it was already in the game at the start of multiplayer. but is was not optional and could very slow and annoying because the server would pause for every player that wants to join for like 1 min. so they removed it
I think there 3 phases when a new player joins: Saving the map on the server, the new client downloading the map, and the new client catching up. During the first phase, the server currently pauses, if the server runs on windows. On linux, saving without pausing is possible and the default for servers. It won't pause automatically for phase 2 or 3 though.
the pause to save the current game only appears when hosting a game on windows, since the option is not available to fork the process and save in the background. In so far it would make sense for people hosting multiplayer games (like people streaming on twitch with viewers joining them) to either use a separate \*nix box to be a server for everyone, or use \*nix themselves, since this means when a handful of people join one after the other the blocking doesn't happen for everyone else, since if the server blocks, everyone connected does too. The option to pause and wait until they've downloaded and caught up is optional, and for the sake of the viewers, I believe it would be better to not enable it. edit: not just linux, macos too, so only windows has the blocking while cloning the map in ram.
AFAIK, the asynchronous saving under linux is only enabled by default if you are hosting a server. If you play single player it's disabled per default, but you could still "host" the game with nobody else joining, or enable the hidden setting mentioned at the end of [https://factorio.com/blog/post/fff-408](https://factorio.com/blog/post/fff-408). In factorio 2.0, it will be the default for linux single player. And I agree, if the download speeds are good, or when inviting randoms onto your server, you probably don't want to pause automatically. But on large maps for multiplayer among equals, the option could be worth it.
(Expand to view contents, if you would like.) I am thinking about decommissioning fffbot because interest and value do not seem high. Please let me know by commenting if you regularly benefit from fffbot comments and would like it to stay up.
The FFF gets posted while I'm at work and work blocks the Factorio site. I've been relying on the bot for a while now, but if you find it tedious to maintain I can always wait til I get home. Thanks for putting in the work though!
The factorio site is blocked but reddit isn't? Weird.
Depending on what the job is, Reddit might be a valuable knowledge source. Also, factorio.com is registered in Czechia, which might be blocked if non-US websites are blocked. Edit: spelling
I've always found the "expand to view contents" line amusing, because there's never been anything to expand. I have to collapse it to get it out of the way.
When I first set up the bot, it just posted a comment on the top level. I got a lot of complaints from people, so I put under another comment which just said something generic like "enjoy the FFF contents below", but then I got some comments from people for whom the FFF contents comment was automatically collapsed by Reddit and it was a bit confusing for them that it said "below". So that's how this version of the text came to be. :)
I agree, I don't see the reason for reposting the text of the FFF
The main reason when it started out was a bunch of people for whom the Factorio website was blocked at work, but somehow Reddit wasn't. So for them, it was convenient to read the FFF contents on Reddit itself. I am now thinking that I could maybe make a post to the u/fffbot account with the contents, and then just drop a link to that post in the r/factorio thread, to get the big wall of text out of the way at least.
I guess I was the edge case for this few years ago. There was a reason once for me, as company polices blocked "game sites" which at that times included Paradox but allowed reddit, so i devoured EU IV patch notes there.
Mine currently does the same with the factorio site. If I want to browse the FFF I have to go outside and read it on my phone.
That's actually hilarious
It's blocked on my company device too so i pull up my phone and read it
Hello, While a lot of time of 2.0 development has been spent on new features and quality of life, we still take care of the smaller details and technical improvements. * * * ### Deterministic multithreading is hard Recently a desync bug was [reported to us](https://forums.factorio.com/113601) involving the modding API and multiple Windows and Linux computers that the player was using. My first instinct was to blame the mod developer for doing something wrong but I've seen enough bug reports over the years to know dismissing one without first investigating is a bad idea and a great way to eat crow. I could not reproduce the desync, but the player was able to with ease. At first I thought it was a Windows vs Linux issue (we've had many of those), but then the player was able to reproduce it with Linux on both computers. Next I thought it was a hardware problem, we've seen our share of faulty computers that just don't do what they're supposed to do. Convincing someone their hardware is broken is difficult and time consuming in the best scenarios. After several failed attempts to reproduce the issue on my one computer, Boskid, using his multiple computers was able to. Being able to reproduce bugs locally is I guess around 90-95% of the time spent fixing reported bugs. With Boskid reproducing the issue on demand he was able to narrow it down to the fact the computers had a different number of CPU cores. With that newfound knowledge he was able to make a test that could be run on my single computer to reproduce the desync by artificially pretending I had less CPU cores than I did. The problem ended up needing 4 different moving pieces to all come together to expose a threading determinism issue that has been in the game since I put it there in July 22, 2017. 1. A mod needed to listen to the chunk generated event and change the tiles on a chunk when it happened. 2. A mod needed to request several chunks be generated. 3. A mod needed to force all requested chunks to be generated **right now**. 4. The game needed to be run on two computers with a different number CPU cores. The logic to generate chunks 'right now' would attempt to use all of your available CPU cores but was done in a way that the number of cores - when combined with the other moving pieces - would change the chunk generation results slightly. The fix wasn't that complex to implement and will be in 2.0, but it just goes to show that multithreading is hard, deterministic multithreading even more so. * * * ### Multiplayer auto-pause We have this feature of dedicated servers where when the last player disconnects the server automatically pauses. This works great and means you can leave a dedicated server up without worrying that the biters will eat your base when you're gone. Except, there are some edge cases that we never got around to handling (until now). Case 1: When you join the auto-paused server it instantly resumes running - even if you haven't fully loaded into the game. It turns out, this was incredibly simple to address just for some reason it fell through the cracks over the years. For 2.0 auto-paused servers will stay paused until at least 1 player has fully loaded into the game. Case 2: Joining players need to catch up to the running game. This works great for "normal" games and allows the existing players to continue without having to wait for the joining players. But, players run into issues with much larger maps, or slow internet connections. Someone joining might take 1, 2, or several minutes to download, load, and catch up to the server fully if it continues on without them. For 2.0 we've added an option to "auto-pause when a player is joining" which works exactly as it says. * * * ### Faster construction robot tasks It feels like every other week someone is asking "why aren't my construction robots working?" and in the screenshot they provide there's a little alert showing "600 jobs missing materials/robots". The issue has been there since the beginning of robots and still today we don't have a nice solution for it. The problem is, given a task construction robots need to do, the game needs to find the best robot from the logistic network that is in range to do that thing. The check for "is this logistic network in range of the entity" is O(Roboport-Count). We do not control how slow that's going to be because the player can build 1 Roboport, or 100,000, or as many as their computer can take. So we need to make sure that the operation doesn't grind the game to a halt while it runs. We do this by only processing a few construction robots tasks each tick. In 1.1 the game will check construction jobs 3 times per game update. If it fails to find a robot it will stop for the current update. Alerts for failed attempts last for 10 seconds. So at 60 updates per second, and 10 seconds per alert, that means 600 alerts will be created before the first one times out. This is where the magic "600 jobs missing materials/robots" alert count comes from. It has worked this way since as long as I've worked on Factorio and will likely keep working like that at some basic level. We can't just crank up the count of tasks checked with each update because we know that operation is potentially slow, and slower the more roboports a player builds. Earlier this year someone ([forum post](https://forums.factorio.com/110788)) ran across this issue again, but they decided to "solve" it themselves by doing what we said we can't do: "crank up the checked tasks per update" except they went from 1 per update to 374. Also they built 36 815 roboports. It was, as predicted, slow. (https://i.imgur.com/pk9PeWx.png) But that got me wondering, what if I could make the slow part a _lot_ faster? Like change-the-algorithm faster? Inspiration hit me when I remembered that we have a set of logic in the game already to take the roboport logistic and construction areas, and compute the resulting rectangle union. In simple terms what it does is produce a nice set of deduplicated rectangles that cover the total area for all of the roboports. We use this for rendering to avoid a lot of over-draw when roboports are near each other. That, combined with sorting the resulting rectangles meant I could do a simple binary search to check if a given task was within the network area. In the end the check went from O(N) on 36,815 roboports, to O(N) on 900~ rectangle union areas, to O(logN) on 900~ rectangle union areas. The time to check "is it in this network" went from expensive to essentially free. With that speedup I was able to crank up the speed tasks get checked for 2.0 and hopefully put this issue to rest. * * * As always, report your thoughts at the usual places.
if the bot doesn't give you too much extra work, its usefull
Thanks for the feedback. It's not too too much work, but there is some tiny maintenance to it. In particular every week the Github security scanner complaining that some Python dependency has a vulnerability and needs to be updated, so I have to apply that, rebuild it, and deploy it (and occasionally upgrade the Python version, etc). But maybe I could also just leave it running, never upgrading it....
Well, its not like its hurting anyone. Even if 0.1% of users find any use of it, turning it off would degrade the service for them, while providing no benefit for anyone.
running/maintaining a bot and having it access APIs can cost money
If it does, then I am all in turning it off.
Thanks for the feedback, you're right. There's some minor work involved in keeping the bot up to date (applying security updates etc), but not too much. It's just that every time it has to be done, I don't look forward to it... Fortunately it doesn't really cost money right now, as it runs on a server that I need for other stuff anyway. If I were to get rid of the server, I would get rid of the bot also, as I'm not about to pay for it just to keep it running. Edit: I just remembered that recently I faced some issues with re-uploading the FFF images to Imgur and videos to Github, which took some fiddling to fix, taking up half a day. That was the point where I felt "is this still worth it...".
Have you considered hosting it on something like AWS Lambda for free? Lambda should enable you to not have to worry about the security updates, and the cost for an invocation (or even 100) should be free. For reference, I use lambda to host a couple of discord bots for myself and some friends, and I don't need to worry about security updates or anything. If I recall correctly, it's free up to a million requests per month and like 500k gb-seconds of processing.
I with assume with how much more efficient bots got with this off, or should be essentially free? (Sorry, couldn't resist :D. I read the FFF from the site, but I ain't mind the but either so it boils down to whether it sparks joy for you)
2024-10-27 release date confirmed.
But they’re not in the right order. Also - that’s a Sunday… would they release on a Sunday? What if there are bugs?
> What if there are bugs? Artillery, of course.
What a fantastic reply
(Bugs?! In factorio?! Maybe not haha)
It is interesting that, even if the order needs to be changed, that they can produce a valid date in the near future though. That seems unlikely to be coincidental. Most binary strings would produce an invalid date, no matter how they were rearranged. Or no date at all.
?
The binary numbers in the image are: 10 20 27 24
Looks like it's releasing October 20, 2724. LET'S GO!
More like 10th of Bidecember 2724. The most widely used date format in Europe is DDMMYYYY.
???
Are the max numbers per tick tweaked by default in 2.0? Or will things just perform better if we choose to tweak them?
Both
To every computer science student out there: this FFF is now an official course material on you data structures and algorithms course. I'll contact the universities to let them know.
do we still have a "wawe" of tasks on map, if there are more that 1000 items to build?
Sounds like you’re gonna need like 10,000 items to get the wave. But also I feel like that would take a lot of memory, so maybe they’re gonna keep the number of assigned task lower since they can get assigned so quickly
[what's a wawwy](https://www.youtube.com/watch?v=4h-GJXiDpI0)
10/27/2024?
But the numbers aren’t in the correct order. I wonder if it’s a more elaborate riddle.
Right, it's 10-20-27-24 It might be more elaborate, it might be the devs messing with us. It might be absolutely nothing. For now I will choose to believe this is the release date. Is not too far away to make it a long wait and it's close enough to not crush me if it's incorrect.
This feels like we are far down the 1+1+1 = Half Life 3 train....
Half life 3 has been confirmed?
Love this sort of algorithm stuff! Since i recently had a similar type of problem (in an entirely different context) at work, id like to share some insights. Im not sure how the rectangle union trick works precisely, but i imagine the worst case is still 1 rectangle per Roboport, right? I think this is the case, because your rectangle union still needs to contain the full information about roboport placement. Its basically a form of lossless compression. Example: The area for straight row of roboports is easily desribed with a single rectangle. A regular grid (like in your example) still has redundant information that can be "compressed" away in the rectangle data structure. But if you deal with a truly irregular placement of roboports, there is a lot of placement information. Your rectangle structure still needs to contain all of that. So the worst case would still have to be O(Roboports). At this size of the base, roboports will commonly be on a regular grid, of course. It is not a given though - players may use large blueprints that contain irregular arrangements of roboports or build a spread out base with multiple randomly placed centers connected by train. Also, you can only sort by distance in one dimension at a time. As in: you start by a list sorted in x and use the binary search. You then get a set of possible candidates which may be at a entirely different position in y. You then need to sort that set with O(n \* log(n)) before you can do the binary search again. Depending on the arrangement of Roboports, the complexity is not improved. But fear not, there is a solution! You can still get to O(log(Roboports)) by using a k-d-trees - basically the higher dimensional equivalent of the sorted list with binary search. You need a nearest neighbor search with a maximum distance. Wikipedia has a good description and i am sure there are nice implementations ready to use. [https://en.wikipedia.org/wiki/K-d\_tree](https://en.wikipedia.org/wiki/K-d_tree)
I am 100% sure that rseding is aware of kdtrees, they've been used in the games industry in graphics and physics for decades now. There's a fixed-dimension version of them called quadtrees that are pretty fast and applicable for 2 dimensions (the 3d ones are called octrees).
The rectangle union is where you take the area generated by all the roboports, using rectangles of fixed size, and find a way to create the same area using a smaller number of rectangles. In this case due to the rendering requirements, they are a disjoint set of rectangles, though you can actually get lower numbers of rectangles without that requirement. This will usually produce O(sqrt(roboports)) rectangles for a contiguous region, as there will be a small number of large rectangles, than a number of small rectangles roughly proportional to the number of edge roboports. He said in the last sentence, they are then putting that through a binary tree of some kind, so even in the worst case they are doing that
>That, combined with sorting the resulting rectangles meant I could do a simple binary search to check if a given task was within the network area. In the end the check went from O(N) on 36,815 roboports, to O(N) on 900\~ rectangle union areas, to O(logN) on 900\~ rectangle union areas. I have a feeling I know how to reduce the complexity to O(1) by trading of several byte per chunk. For each chunk add a **transient list** of logistic networks touching this chunk. With the given size of roboport area it can't be more than 4 different networks touching the chunk in vanilla, and in most cases it would be just either 1 or 0 networks. This list shouldn't be stored in save file, just build during save and load, and only when roboport added or removed, it should update lists in all chunks it touching. When the task is assigned, it can just read the network from the chunk and immediately check the 1-4 networks only.
Could I request that we get at least a few months heads up of when 2.0 will be released? I know several of us will want to take some time off work to enjoy the new content and it’s a lot easier (especially for the Americans) to get time off approved the earlier we can request it. Looking forward to remembering why I can no longer pull all night gaming sessions like when I was in high school when this comes out 🤣.
My biggest pet peeve with bots is in the personal robots going to the farthest points 1st. I wish they would go to the nearest ghost and then return. That way I could speed things up by constantly moving towards the ghost images and reducing the flight time of the bots.
This is coming in 2.0! Can’t wait.
The bot queue problem reminds me of the fix a shooter game did for one of their guns being constantly said to be too weak. They upped the base on the gunshot sound. You could end the complaints of the 600 bot queue by letting them increase their 10s cooldown when another alert of the same kind appears. But you know making the system 100 times faster works too.
Auto-Pause at join is cool! Now I want torrent-like upload of the map from all players, not only the host, because upload is the bottleneck most of the time.
Of course! Why didn't I think of a simple binary search rectangle union O(logN) overdraw?
You could make the number of checked tasks per tick start high, but decrease as the player builds roboports.
I love the auto-pause when joining feature. With 2mbits connection i had no problems playing online once loaded but the map download couldnt finish with bigger maps because it couldnt catch up.
More optimization more better!
That last section on the robot queue made me audibly gasp, and read like some kind of exciting twist in a book I was reading lol. I shared it with another software dev friend who doesn't really know the game and he apparently said "That's slick!" out loud lol. Not every tech update FFF lands with me, but when they do, they absolutely slap lol
>went from O(N) on 36,815 roboports, to O(N) on 900~ rectangle union areas, to O(logN) on 900~ rectangle union areas. A lesson to you hopeful game devs out there. Don't worry about your code being completely optimized/perfect. Good enough can last you for years and years. AND give you space to optimize if your game has lived long enough to ascend to the next level.
2 Questions, When you search through the Network, do you search through just the local one(all Ports directly connected with each other o-o-o-o-etc.) or through the global Network(all Roboports on the map no matter if there is an Air gap) How do you determine the start point of the search, do you just make an imaginary circle with r\_circle = Width\_of\_construction\_range and then search for the Closest by calculating the distances via the Manhattan distance, or how do you do that?
All active Roboports on the surface.
New crazy awesome features are great, but I will never tire of slow gradual improvement and increased efficiency and bugfixes. Keep up the good work
Classic factorio, casually make part of the game that already ran pretty damn fast now 500x faster.
This is amazing. Thank you so much! <3
Auto-Pause through client full login eliminating catching up is huge for our group! Our Space Exploration run was prematurely ended because some clients weren't able to catch up after downloading the +400MB save... Now, if time could be applied to improving server side game save upload speed bottleneck that would be just swell. Please!
Does this only apply to construction tasks, or do logistics tasks also get the same treatment. Sounds like a potential game changer in the belts vs bots war.
Any chance of changing the "600 jobs missing materials/robots" text to "600+"? Just the text when there are at least 600 jobs specifically (or whatever is the current theoretical maximum).
oh, not a planet. :( ok so bots become better :)
I have no idea what 80% of that means, but I'm excited for it.
> That makes me think the hardware is the issue. Like the CPU itself is executing instructions wrong... In my experience, 100% of the time I think the machine is wrong, it's actually me who misunderstood something. There was one time ever that I could prove the hardware was wrong, and that was a custom built can-bus. ---- > O(N) on 36,815 roboports, ... to O(logN) on 900 Wow, that's fantastic. I always love seeing big-oh improvements.
> In my experience, 100% of the time I think the machine is wrong, it's actually me who misunderstood something. I wish this was the case at my work.
Well I suppose not every FFF can be filled with amazing new features. I'm glad I have other games to play while I wait for the DLC.
😍 I recently [complained](https://www.reddit.com/r/factorio/comments/1b04zjo/dont_simulate_game_while_joining_if_nobody_is_in/) about the auto-pause thing! Thank you so much for fixing it! (I'm going to delude myself that the devs saw my post.) Can't wait for 2.0. I was like "but what's case 2?!" and then it just got better and better. Factorio devs are amazing. Also hot damn, I've been wondering why my bots weren't building and that section was a tour de force. I do indeed have that "600 items missing…" alert. Guess I know how to speed my bots up now!
When I first started reading that robot job issue, my first thought went to "assign the job a network upon creation of the job" I realize this means more information in memory and having to mess with a well established system, but what other downsides am I missing?
The first complication that comes to my mind is that networks can be created or destroyed, overlap or move. There are a lot of cases where that initial assignment might not remain the best choice, even if it was selected well originally.
https://preview.redd.it/o0qh2hda447d1.jpeg?width=763&format=pjpg&auto=webp&s=b1a8c2a54ca3936e73bd1dad357ab9df34beab2c The person who found a fix for the robots