Factorio Forums

Parallel processing is difficult for many reasons. To help facilitate understanding I'll call multi threaded processes "players". The basic idea is that if you think of a separate threaded process in the same way as two or three computers playing over the internet, it can help clarify the sort of problems you will run into. Namely I will assume that communication between processes is much like computers on a network. If you want data from a different process you must ASK for it, and if you want to make changes to another process' data you must WAIT for confirmation. You have to deal with lag and all sorts of hand shaking to make sure there is no kind of desync between separate threads. Every handshake wastes time and precious CPU as well as making a potential coding nightmare. So to give us the least trouble we want our threads I.E. players to do as LITTLE interacting as possible.

With that in mind here are some simple rules for separate players. Everything owned by a player only ever interacts with that player. Inserters will only pull from player owned belts, will only put into player owned assemblers, and will only share logistics with player owned networks. Belts will stop cold when hitting another player's belt and will not exchange contents in any way. Pipes are the same and will not interact between players in any way. Logistic bots and networks will only interact with structures associated with the same player. For all intents and purposes the factory of one player is completely blind and oblivious to any other player. We don't want Bill's inserters to be asking Joe "hey what's on your belt" and be waiting for Joe's belt to tell us "I have iron plates" and then Bill asks "I'm taking this iron plate plz?" and waiting for Joe to say "yeah sure I don't want it" and then Bill says "Thanks" and Joe says "NP". It is easier for Bill to say "Oh my inserter doesn't connect to anything I own. I can't do anything". This isolation of data lets our processes run freely independent of each other to reduce our headaches and maximize our parallel processing potential.

What remains are several ways separate processes may still be forced to interact:
1) Between players and terrain
1) Between players and power network
2) Between players and trains
3) Between players and combat/aliens
4) Between players and avatars
5) Between dedicated "bridges" to pass items from one player to another.
6) Between players and the video renderer

Each interaction is its own problem that has to be solved in some way.

== Terrain ==
We don't want two players occupying the same space in the game world. It's not actually dangerous for the code, because each player is functionally a parallel universe. Nothing from one universe ever sees or directly touches another. But it IS ugly to be stacking factories on itself. A mediating factor is required to make sure that one player's assets do not occupy the physical map space of another.

There may also be objects on the world surface that a player interacts with. This part could get very tricky to solve. An inserter may throw an item on the ground for another inserter to pick up, and we don't know which player the grounded gear belongs to. Player1 may drop gears on the ground and Player2 might build belts over it. Normally the items would continue down the belt, but player2 is blind to player1's assets so it wouldn't even know the gears are there. Should the items be given to the "world"? That would increase cross talk and we don't want that. A simple answer is to say "woah woah woah. Player1 has something, ANYTHING here. I can't touch this tile."

For the most part there is no reason for player1's factory to interact or weave into player2's factory. We generally want all parts of a spaghetti fortress to have access to itself and the game code is efficient enough to allow this. If we think of player2 as an "outpost" player, it's easier to understand that an outpost is physically separate from the main base. We can then create a physical map exclusion zone so that our players don't even interact through the world's data. Player1's chunks belong to player1 and everything on the ground belongs to him. Player2 can't see it, touch it or even place an inserter anywhere near it. Fewer interactions make parallel processing easier.

== Power Network ==
Linking power networks between players isn't too bad as there's only one single "resource" being coordinated between separate threads. The simple solution is to not allow separate player power networks to interact in any way. But we may want a huge central nuclear plant that feeds everything regardless of player count. In order for this to work let's use a separate "energy broker".

Each player calculates the power it has available and reports it to the broker. They then request power from the broker. The broker then decides how much power each player is either exporting or importing. Making the power transfer fully fluid and 2 way will involve some coordination between threads to sync power storage and consumers. I won't claim how easy or hard that will be. For the most part players will be satisfied with a large central power source that only exports to other players. For example player1 has a huge nuke plant and is exporting power to all of player2's outposts. That's not a huge burden to code.

== Trains ==
If you can't trade resources between players, what's the point of running parallel processes? We need a way to move items between players. Trains move lots of stuff, they can't interact on the move, and they travel large physical distances that we can use to separate our players. They're perfect. Keeping data synced is as simple as ensuring a train only obeys one player at a time. The train goes to player2's ore outpost, fills up with player2's inserters, travels to player1's base and unloads into player1's chests. Our player interaction is a single bulk transaction as the train changes ownership from player2 to player1.

A train needs access to all the rail network data in order to do its job properly. It needs to know where all the stations are and how to get beween them. A train also needs to transfer data(items) between players. In that respect a train can't function very well if it has to ask other players where all its things are. It may be fruitful to have a "playertrain" that owns and manages all the train assets. A train player has very few interactions for its assorted assets. It merely needs to secure territory for its stuff (rails, signals) and know if a station is open or closed. Everything else important happens with the train itself.

There will be issues with combinators and circuit networks that interact with train signals. For example a train crosswalk uses gates and combinators to turn rail signals on and off. This sort of behavior can't be isolated in player data and needs to be directly communicated to trains. It may be an easy problem or it may be a hard one. I don't have any answers here, sorry.

== Combat/Turrets/Aliens ==
Players need access to all the data involving where biters are and what they are doing. Generally as long as one player's gun range can touch another player's gun range, then they HAVE to interact in some way. There is a potentially huge issue of mixed player turrets coordinating their attacks, and making sure biters have all the data they need to engage targets from different players. If we use exclusion zones around a player's stuff, most of these problems disappear. Turret lines won't be mixed because players can't build in each other's zones, so there is no need to cross talk between players. Players close to each other may cause potential desync if both turret lines fire on the same target. Stuff like that. It is also possible for force all combat and associated assets to obey player1, but that would screw player2 outposts that can no longer interact with their guns. There are some issues involved and I don't claim to know what they all are or all the ways to address them.

== Between players and avatars==
Yes, I use the word "players" to describe a parallel process, but this time I'm taking about the guy behind the keyboard. The user avatar must be able to interact with all the stuff in the world. I suspect this isn't very different from hosting your own network game and then connecting to it. Most interactions are going to involve grabbing something or placing something, and every one of those requests will have to be synced with whichever factory the player talks to. These requests won't be more than the player's APM, so it won't cause crazy overhead.

The personal roboport will have to be sync'd so it doesn't blow up between different factories and logistic networks may do funny things if the player crosses boundaries. There may be more things to worry about of course.


== Dedicated bridges ==
Sometimes we want players to interact directly with each other. Maybe your rocket factory is SO big that you have no choice but to cut it down the middle. Maybe you want to run a massive pipe or belt from a distant player2 outpost. A dedicated bridge to connect two players is needed. You only need 3 types of bridges- a belt for solid items, a pipe for liquid items, and a pole for electricity. In effect the bridge consumes items from one player's side and spawns them on the other.

Why a bridge item? As I said at the very top, every exchange between two processes is expensive on CPU. You don't want that code running for every single thing in the game. Chances are you only need a handful of bridges to make things work. Take a 16 wide belt for example, you want to split 8 belts for one factory and 8 belts for another factory. That's only 8 conveyor bridges to feed the second factory.

The train problem might be solved by using dedicated train bridges. Player1's train enters on player1's tracks, goes through a checkpoint, and is now player2's train on player2's tracks. Nothing else on the train network interacts between players. The checkpoint serves to connect train station information between the two players and also to hide any lag related glitches the train might have switching sides.

== video stuff ==
You got me. I don't know how that stuff works. I only know that many games dump video rendering on separate threads. Can multiple sets of data talk to the renderer, or will we be stuck with weird things like player1's stuff vanishes when player2 moves into view? I dunno. It requires study.

== To Infinity and Beyond ==
You've already gone through all this effort break factories down into units that can be parallelized. What if players were actual players, each running a factory from their home computer? The host may still share the bulk of the work handling things like pollution, trains, and biters. But other players might join in, build their mega factory, and try to spaghetti it together with another mega factory. Who knows what the possibilities might be?

== The end ==
If you made it this far, thanks for reading! If you skipped directly to the end thanks for TL;DRing! I don't actually know anything about parallel computing and basically pulled everything here out of my ass. If I'm right or wrong or made grievous errors that will plague humanity for years to come, sorry! I didn't mean it. But I hope I gave you guys some ideas about what might work and maybe get some serious discussion on how a parallel Factorio could work.

You can join this thread
viewtopic.php?f=5&t=39893
TL;DR
Factorio team knows about parallel processing

Honestly, those ideas are terrible and overcomplicated. If you feel like it, PacifyerGrey linked to a good topic to read.

quinor wrote:Honestly, those ideas are terrible and overcomplicated. If you feel like it, PacifyerGrey linked to a good topic to read.

Overcomplicated? But the vast majority of the ideas are about REDUCING the complexity involved. A successful asynchronous process doesn't actually know or need to care about what its partners are doing. Yes, you eventually have to establish contact and perform some kind of sync or bad things happen. If that sync has to happen millions of times a second, then guess what? You don't actually have a parallel system. It's just a very messy and wasteful single CPU process. The hardest part of parallel computing is how far you can go without being forced to sync. With a big factory block, every single entity inside that factory HAS to interact, sometimes in strange ways, every single frame. That makes parallel processing insanely hard. When you start separating factories into separate mini bases, you have a guarantee that entities between bases will not interact. If I'm understanding things correctly, that should make parallel processing very easy.

Now. Is there some reason this system would not work? There are probably better and more clever ways to code things or hide the raw mechanics from the player, but I am not a 20 year veteran programmer so humor me on this. From a broad perspective, is there any undeniable reason why an ore outpost MUST run in complete sync with a main base? Do the turrets 5 miles down the track HAVE to operate on the same code thread as the turrets at home? I did everything I could to point out everywhere the game engine would require special syncing to keep working. I wouldn't know if those problems are easy or impossible to solve or if they'd be such a mess the whole system is pointless, of course.

It seems to me that if an outpost is running one base and the spawn point is running an entirely different base, there's no actual data sharing or collisions between them. You can probably run them as two completely separate games and never know the difference. The only real data interaction happens through a very special system- trains.We know that that trains tend to interact with only ONE factory base at a time, otherwise you'd just use belts. We also know that trains will ONLY interact under special circumstances- they must be stationary and committed to their station. So it seems to me that the most complicated part of syncing two separate bases would be with trains.

bobucles wrote:Now. Is there some reason this system would not work? There are probably better and more clever ways to code things or hide the raw mechanics from the player, but I am not a 20 year veteran programmer so humor me on this. From a broad perspective, is there any undeniable reason why an ore outpost MUST run in complete sync with a main base? Do the turrets 5 miles down the track HAVE to operate on the same code thread as the turrets at home? I did everything I could to point out everywhere the game engine would require special syncing to keep working. I wouldn't know if those problems are easy or impossible to solve or if they'd be such a mess the whole system is pointless, of course.

Power usage and production statistics. A + B + C != B + A + C when it comes to floating point numbers.

A turret firing on one point of the map could result in it dying which changes the logistic network it's part of which activates a robot on the other side of the world.

Virtually *everything* in Factorio code is linked to other things in the simulation such that you can't process one without impacting the others. https://www.reddit.com/r/factorio/comme ... y/dhsw89j/

If it seems a little too hard to understand let me present this scenario. Bill and Joe are both guys living in separate neighborhoods who enjoy chatting online. They each start up a single player game of factorio using the same map seed and start building their own factories. Bill asks Joe for some iron. Here's where the magic happens:
Did you see what happened? Even though Bill and Joe are playing on different computers,using different hardware, living in different states, they just moved resources from one factory to another. Only a few lines of text was exchanged, yet two factories running entirely different games of factorio managed to coordinate their resources. Does it make more sense why I reference these processes as separate players? Let's look at another example.
In this case three players have coordinated their assets to help Sarah build a rocket. Can you tell me which computer was running the game? If all these factories were working on one computer you'd probably lose some UPS, and in fact there is no way Sarah's toaster could have handled it. But through the efforts of her two friends she was able to piece everything together for her rocket. At no point did these separate tasks have to reside on the same thread, the same CPU, or even the same state. And yet very little effort was needed to give these players everything they needed to piece their efforts together into one giant rocket factory.

Virtually *everything* in Factorio code is linked to other things in the simulation such that you can't process one without impacting the others

And that's why I'm saying these factories have to be forcefully separate from each other. Every interaction requires effort, as shown between the cooperation of Joe and Bill and Sarah. But if they talk to each other very much and type REALLLLLLY fast, there's no reason they couldn't coordinate "cheats", trains, real estate, or even electricity while still running their own personal factories. You just don't want them asking each other every time an inserter wants to grab a belt or a laser wants to shoot. I don't think their fingers are strong enough for that.

So. how about now? Maybe it sounds a little bit more doable when you think of it this way?

@bobucles, in your example, the only messages sent seem to be: A slightly more realistic example could be: Note that different timing of Joe's and Sarah's messages to Bill could mean Bill's production (linked to these messages) exhausts shared accumulators, making Joe fail to defend against biters.

[repeatedly]
Everyone: Is it done yet? Do you have room yet? Is it done yet? Do you have room yet? Is it done yet? I need X this exact game tick RIGHT NOW or I'll die! Also, is it done yet?

Congratulations! This is exactly what we DO NOT WANT! When requests are directly intermingled, happening on an ongoing basis, and are basically a complete mess, what you have is NOT a successful parallel system. What you have described is a system where any entity needs arbitrary access to any other entity in the world. There MAY be some magic to avoid a coding catastrophe, and if you can find it feel free to collect your Nobel Prize.

But I'm not talking about a revolution in computing. I'm talking about something very simple. In fact it's as simple as putting your mouse cursor over the Factorio shortcut, highlighting it, and hitting the enter key twice. Through the power of brute force magic, I am now running two Factorio threads perfectly stable and perfectly in parallel.

Now that these threads are fully and completely independent, all I have to do is find ways to connect them back together. For example I can delete resources on my left monitor, and spawn resources on my right monitor. I can delete a train on the right, and spawn it on the left. I can run a cheating energy absorber on the left, and run a cheaty energy spawner on the right. If I want to transfer ownership between monitors I can snag a blueprint on the left, and copy-paste it on the right. Do you see it now? These factories have no IDEA that the other factory even exists. They aren't even allowed to touch the same RAM. Yet if I were to place the monitors side by side, would you know that the left factory wasn't actually connected to the right factory? Maybe not!

Is it a smart system? Of course not! I admit it's a hack, and It's as dirty a hack as they get. Will it scale up to dozens or hundreds of CPUs? I seriously doubt it, it may not even survive more than a handful of "players" struggling to grab their piece of the main map. But do we need a fully integrated nanothreader that can arbitrarily divide up factory processes into a thousand fully parallel, asynchronous threads? I don't think that will help! My computer only has 4 CPUs and it's hard to top 16 main cores on a system unless you REALLY want it.

In your example, *you* are the entity with full access to both threads, which is fine, as you are the thread manager.
Your actions are also significantly less frequent. Were they done 60 ups, there would be no difference to the current system.

So your proposal is to separate parts of factory, each of which would be easily parallelizable with full 60 ups, but can communicate with others at lower frequency, say 1 ups. Now, how do you deterministically decide how to divide them? If it's some arbitrary factory size limit, you'll have to deal with (possibly negative) player experience when e.g. all chests of their factory accept/produce items at full speed of 60 ups, but adding one more chest suddenly divide the factory into two parts, and some entities along the divide are now working with 1/60 efficiency.

There are many issues with your solution to the problem, but really it comes down to just one that means your plan can never work the way factorio is designed. Because factorio uses a deterministic design it means that each player runs the entire simulation on their system. If you've ever played online realtime games, you'll have seen weird behaviors like players being able to shoot through a wall. This occurs in part, because each person can calculate the results of actions and send them back and the server (often) doesn't care if it doesn't quite match up. Largely this is because the effects of this desynchronization of the 2 realities doesn't have a long lasting impact. (Lag does weird things like that too, where the server and your computer says, "hey Bob is running towards me, I'm going to assume he is continuing along this course and pre-calculate, and then bob doesn't go that way and you get a little rubberbanding effect when the server starts to correct things back to reality).

Because Factorio is deterministic, everyone computes the whole thing, and because of that any person who fails to calculate the simulation identically gets desynched. We want this actually. If my game said it produced 10 more iron plates in the first 10 minutes of the game than yours, all of the sudden I made an entire building that as far as your system is concerned, couldn't have been made. (it would also let me cheat stuff in and just say "hey I made this" and your system couldn't disprove that I did, you have some implicit trust that my system is telling the truth.) Yes, you could add in a bunch of clever code to try and calculate stuff on both your game, my game, and the server and mathematically prove that what I'm sending is accurate, but now you've just added a crapton of complexity.

There *are* things that threading can solve, and the Factorio devs know this, they have even talked, at length, about their efforts in that area. (though it could be that it never happens because the hurdles are just too steep) But I can say, with some certainty, that your system can't work with the way MP was designed (and possibly not even the way SP was designed).

Threading/Multi-Core is *hard*. It took years after multi-core systems became available before games started doing parallel threading in a way that really started to use those extra cores. (and many still don't, if you see mutliple CPUs in use on your system from a game, there is a good chance the game is single threaded (ish), and the kernel/bios is balancing it across multiple cores to improve performance invisible to the game itself) Graphics rendering is another beast entirely.


That said, I'd say Factorio is already freaking impressive from a performance standpoint. I've seen MP games with > 300 people in them with it working *fairly* well. 25-50 player games are smooth as butter. I'm going to go out on a limb and say the factorio Devs have a pretty good handle on things and already have a good idea of the issues. The thread Rseding91 linked to basically sums all of this up.

I would just like to second the thought that multicore processing is hard, really hard.

Sure, trivial stuff can be done quite simply, but a game simulation is not trivial. You will be hard pressed to find a game with multithreaded updates. Doing different kinds of updates in different threads (for example physics vs pathfinding) maybe, but almost never splitting up the main simulation update.

For some reason I doubt bobucles is a programmer, or at least not one who has done mulithreading before.

Now, how do you deterministically decide how to divide them?

I don't have an automated answer for that. In fact such a system is pretty dependent on the threads being divided up manually, by the end user. The end user defines what parts of the factory they want being totally separate, and manually sets up the connection points between them. It's kind of a mess that way and it would be a pretty difficult concept to get across.

That's the purpose of the dedicated bridge, in fact. Its main purpose is to notify one thread that it has a contact point with another thread, and the main effort would only be synchronized through those points. Those connections would not be anything more complicated than some kind of synced network connection. Left monitor is giving X through a bridge, right monitor accepts X at the bridge. Seems simple enough.

Whether or not the exchange happens on the same frame isn't really relevant, because no other force is meddling in this exchange. If the other side doesn't accept the transfer then you have a simple stall at the bridge, where resources have to patiently wait to progress. There is no real error checking beyond that. It is assumed the connection point is between two honest threads so if the left side has a train full of ore it's assumed that they dug up the ore and loaded it in fairly. If the left side instead decides to cheat resources and dump them through the bridge, the right side has no real way to test against it. The right side has no business meddling in the left side's data, so it can't error check that kind of thing.

As a system between various computers online, it is definitely prone to disaster. If human B runs a cheat game you can't do anything about it, because you don't have his data to test against. if all the threads are on the same computer, we can be reasonably certain that they're all playing fair with each other. Therefore we can use the left monitor's big factory in one world, use bridges to connect key resources to the right monitor's big factory, and somehow end up with an asynchronous super factory.

I see the idea isn't gaining much traction, so I won't press the issue any further.

bobucles wrote:Whether or not the exchange happens on the same frame isn't really relevant, because no other force is meddling in this exchange.

As noted above by @iamwyza, which is based on viewtopic.php?f=5&t=39893 and https://www.factorio.com/blog/post/fff-188 I think, each player in a multiplayer game needs to simulate the whole factory in the exactly same way. So the result of simulation calculated in 1 thread has to be the same as in 2 or 4 threads. Thus if a factory is split into 4 parts eligible for parallelization, and the 1-thread implementation finishes the exchange in a specific tick/frame, the 2-thread and 4-thread implementation have to guarantee they finish it in the same specific tick/frame as well. There is no leeway for not caring whether one thread processed the goods another sent it.

This was a nice read, but I am going to be realistic and say this will never be implemented into basegame factorio. I have done my best on doing this as a mod with clusterio. It allows you to transfer items between worlds using dedicated chest bridges/combinator bridges.

Currently its not at all seamless and requires a bit of server setup and lots of clutter but it is in a working state. If anyone is interested in the project, I am available at #factorio on EsperNet IRC or using the github issue tracking system.

https://www.github.com/Danielv123/factorioClusterio

bobucles wrote:

Now, how do you deterministically decide how to divide them?

I don't have an automated answer for that. In fact such a system is pretty dependent on the threads being divided up manually, by the end user. The end user defines what parts of the factory they want being totally separate, and manually sets up the connection points between them. It's kind of a mess that way and it would be a pretty difficult concept to get across.

That's the purpose of the dedicated bridge, in fact. Its main purpose is to notify one thread that it has a contact point with another thread, and the main effort would only be synchronized through those points. Those connections would not be anything more complicated than some kind of synced network connection. Left monitor is giving X through a bridge, right monitor accepts X at the bridge. Seems simple enough.

Whether or not the exchange happens on the same frame isn't really relevant, because no other force is meddling in this exchange. If the other side doesn't accept the transfer then you have a simple stall at the bridge, where resources have to patiently wait to progress. There is no real error checking beyond that. It is assumed the connection point is between two honest threads so if the left side has a train full of ore it's assumed that they dug up the ore and loaded it in fairly. If the left side instead decides to cheat resources and dump them through the bridge, the right side has no real way to test against it. The right side has no business meddling in the left side's data, so it can't error check that kind of thing.

As a system between various computers online, it is definitely prone to disaster. If human B runs a cheat game you can't do anything about it, because you don't have his data to test against. if all the threads are on the same computer, we can be reasonably certain that they're all playing fair with each other. Therefore we can use the left monitor's big factory in one world, use bridges to connect key resources to the right monitor's big factory, and somehow end up with an asynchronous super factory.

I see the idea isn't gaining much traction, so I won't press the issue any further.

I'd think the main problem that you'd have with such a thread as that you view them as asynchronous when they should be most definitely not be. They'd absolutely need to synchronize their updating schedule, but beyond that if you could separate them you'd be able to increase the overall speed by using more cores.

Though I think a better example would go like this: picture two blocks. Each share exactly one side with the other, with some arbitrarily limited ways to connect. Say...only via train, as the blocks are arbitrarily far away from each other. Even better, have two one way tracks be the only connectors so we don't have to worry about race conditions. Each side does their update, then waits for the other to finish. Once they're done, they post a "transfer" if needed where bits of train appears in the other block. Theoretically, it'd probably work. (I'm betting there are other considerations to take into account, but nothing insurmountable). Each block is still limited by the slowest block's speed as they need to synch up, with no worries about synching issues for multiplayer.

It's also likely a waste of time and a headache to program. But supposedly doable.