Friday Facts #260 - New fluid system

Regular reports on Factorio development.
meganothing
Fast Inserter
Fast Inserter
Posts: 126
Joined: Thu Sep 15, 2016 3:04 pm

Re: Friday Facts #260 - New fluid system

Post by meganothing » Wed Sep 19, 2018 3:50 pm

Pyroatheist wrote:
Wed Sep 19, 2018 5:31 am
Minor and Major fluid losses will not be accounted for
Correct me if I'm wrong, but this practically means I could connect 100 inlets at place A and make a single pipe line to a distant place B where 100 outlets are connected together. And this single long pipe line would not limit the transfer in any way because your simulation assumes that only the source (in this case 100 times what a single inlet can deliver) limits volumetric flow rate.

Not that other ideas are necessarily better, I'm just trying to find out where each idea has its limitations.

Pyroatheist
Burner Inserter
Burner Inserter
Posts: 5
Joined: Wed Sep 19, 2018 3:04 am

Re: Friday Facts #260 - New fluid system

Post by Pyroatheist » Wed Sep 19, 2018 4:18 pm

meganothing wrote:
Wed Sep 19, 2018 3:50 pm
Pyroatheist wrote:
Wed Sep 19, 2018 5:31 am
Minor and Major fluid losses will not be accounted for
Correct me if I'm wrong, but this practically means I could connect 100 inlets at place A and make a single pipe line to a distant place B where 100 outlets are connected together. And this single long pipe line would not limit the transfer in any way because your simulation assumes that only the source (in this case 100 times what a single inlet can deliver) limits volumetric flow rate.

Not that other ideas are necessarily better, I'm just trying to find out where each idea has its limitations.
That's correct, but could be easily added back into the simulation if necessary. I made that assumption to simplify the overall computational load, but if major losses turn out to be important to keep the simulation honest, as it were, that can be added.

Major losses take the form of a pressure loss that scales based on volumetric flow rate, pipe length, pipe diameter, and the viscosity of the fluid. We've already got most of these, so the only new factor would be fluid viscosity. Viscosity would go alongside density as "parameters you can fiddle with to change how well you can flow the fluid".

Using head loss also introduces a bit of complexity in that each outlet is trying to scale based on both the junction proportion and the head loss. In a real system, the "junction proportion", is handled by minor losses, but in this system a workable solution would be as follows:

Run a unique flow equation for each individual outlet that includes major loss, then scale it by the junction proportion to get the flow rate. Major loss factors in as a reduction in pressure, resulting in a lower flow rate. If you set major losses to 0, you'll have the same simulation that we started with where the outputs are simply directly scaled from the maximum flow rate. As major losses increase, each outlet will start to see its output flow drop.

The one additional check that this requires is making sure that the total flow rate doesn't exceed what the source can provide. This is probably best handled by simply putting a tank at the inlet (and outlets). The tank drains at the flow rate pulled by the outlets combined, and once empty the flow rate drops to 0, leaving the remaining fluid stranded in the pipes instead of emptying them. This is how a real pipe system functions, as you can't pump or extract that fluid until you push more through.

pleegwat
Fast Inserter
Fast Inserter
Posts: 107
Joined: Fri May 19, 2017 7:31 pm

Re: Friday Facts #260 - New fluid system

Post by pleegwat » Wed Sep 19, 2018 4:57 pm

On the one hand, I think the aquaduct/open channel approach fits the game better than a pressurized pipe system. Pressurized pipes end up too close to the electrical system for my liking. That may be realistic, but is it fun?

On the other hand, I think behaviour should match visualization. Current visualization is of pressurised pipes, except because they are not always full they can't be pressurized pipes. If TheYeast's model or something like it is picked, then I think the visualization should change as well to one that has open-to-air channels instead of closed pipes.

Matthias_Wlkp
Long Handed Inserter
Long Handed Inserter
Posts: 96
Joined: Mon Oct 10, 2016 11:28 pm

Re: Friday Facts #260 - New fluid system

Post by Matthias_Wlkp » Wed Sep 19, 2018 5:24 pm

I still don't get, what is the benefit of a more realistic model for pipes. It seems that it drains a lot of resources for something that will be noticeable only, if it doesn't work...

In the end, everybody will build systems, that will resemble electrical circuits - fluid input >= output, so the pipes are always 100% full, otherwise, pipes are empty.

quinor
Filter Inserter
Filter Inserter
Posts: 372
Joined: Thu Mar 07, 2013 3:07 pm

Re: Friday Facts #260 - New fluid system

Post by quinor » Wed Sep 19, 2018 6:40 pm

Hey guys, programmer with a bit of physics background who's into simulation here. Let me propose yet another fluid model. Yeah, yet another. It works though in a similar (but a bit different) fashion than the TheYeast's model. The super technical and strict description below, also on github together with CLI python simulator: https://github.com/quinor/fluidsim/blob ... iption.txt

Code: Select all

THE MODEL


parameters:

I - inertia, 0.9
A - acceleration, 5


edge parameters
    V_ij - velocity (desired flow per tick) between node i and j
        V_ij = -V_ji
    F_ij - actual flow in current tick


node parameters
    basic
        C_i - capacity
        T_i - current volume
        P_i - pressure (like in current system)
    auxiliary (computed for the needs of the algorithm)
        Vin_i, Vout_i - summaric in/out velocities of a node
        Sin_i, Sout_i - satisfaction for incoming and outcoming flow (what fraction of Vin/Vout can be satisfied)


in each tick:
    # update the velocities
    for each connection i, j:
        V_ij := V_ij * I + sgn(P_j-P_i) * A

    # compute auxiliary values
    for each i:
        Vin_i = sum_j max(0, V_ji)
        Vout_i = sum_j max(0, V_ij)

        Sin_i = min(Vin_i, C_i-T_i) / Vin_i
        Sout_i = min(Vout_i, T_i) / Vout_i

    # apply flow
    for each connection i, j such that Fij > 0:
        V_ij := min(Sout_i, Sin_j) * V_ij
        T_i -= V_ij
        T_j += V_ij

    # handle other stuff, ie. pumps or fluid-handling machines

algogenetienne
Burner Inserter
Burner Inserter
Posts: 6
Joined: Tue Sep 18, 2018 5:41 pm

Mathematical Optimization for a fluid system

Post by algogenetienne » Wed Sep 19, 2018 7:39 pm

Hi

I am into mathematical optimization and I always feel a little sad when I see an engineer come up with a complicated algorithm for a problem to which a whole mathematical field is dedicated. There is a huge amount of time lost because of the lack of communication between engineers and researchers. I would like to avoid that here.

Flow model is the way to go. It's how such problems are done in practice. And it is indeed a simple problem (school project simple in fact), provided you use the right tools. Entity based simulation can not simulate efficiently a fluid network. A fluid network is a graph, with n oriented edges (pipe section of any length) and m vertices (oil plants, pumps, tanks, pipe junctions....).

Let x be the flow in each edge, an n long vector. The flow can be negative, if the fluid is flowing against the edge orientation.
Let d be the pressure in each vertex, an m long vector.

1st Kirshoff law (= non accumulation of fluid in vertices) states that the flow coming in + the flow leaving a given node is null.
Let A be a n*m matrix (one line = one edge, one column = one vertex). If we put a +1 where an edge enters a vertex, and a -1 where an edge exits a vertex, the above condition in a circuits with no inputs or outputs is Ax = 0. In practice, there are nodes that create or consume fluid so we put that in a vector b. bj > 0 implies that the jth vertex consumes fluid (plant), bj < 0 implies that the jth vertex creates fluid (pump). Now the condition is Ax = b.

Then we want to take into consideration the loss of pressure around the pipes
With Colebrooks formula, we have the following matrix formula to know the pressure at each node.
trans(p)A + r*x*|x| = 0
With r an n long vector. ri is the resistance of ith edge; the resistance is proportional to length. * is the multiplication coefficient by coefficient so r*x*|x| is an m long vector.
Basically, it means that the amount of pressure lost in an edge depends on its length and the squared flow.

In Factorio, we know the inputs, so the bi are fixated in pumps. Let's assume the demands are satiated too
We fully know the value of b : bj is the maximum consumption of a factory, or the output of a pump, or 0 if it's a pipe junction.
The stable state of the network is the one that minimize pressure loss, so it's the solution of the following problem :

min (x . r*x*|x|) - (pt, xt)
under constraints Ax = b

with pt the pressure in tanks, which is known because it only depends on the amount of fluid in it and rt the flow coming out of tanks (we take fluid out of tanks with higher pressure in priority)

With a bit of tinkering with Ax =b, it's possible to have only x as the only variable and remove the constraint. The problem can then easily and efficiently be solved by Newton's method.

That's the general idea to have the stable flow in a perfectly balanced network. The stable flow is the one you will get in real life, providing the demands and production do not change "too fast" (compared to the total fluid inertia in the circuit)
It does not depend on the number of pipe, only on the number of edges and vertices of the network. A 50 pipe long section is as costly as a 1 pipe long one. And because you have the variable x, you know the flow in each section.


There is a bit more work when production and demand do not match and tanks are full or empty. One has to compute the consumption of each individual plant or the output of each individual pump based on local pressure.
Moreover, the problem I have just described doesn't offer any gameplay. It will give a functional network no matter the configuration, making 10000 gallons going through a single pipe every second if need be. But it is a functional base upon which to expand later on. There is quite a lot of literature on constrained optimization so it is possible to come up with an algorithm that will work even if pipes can not contain more than a given volume (even if this constraint does not make much sense IMO, it would be more realistic to have fluid loss on pipes where pressure is too high and efficiency loss in plants where pressure is too low)


So please consider using an optimization system instead of something you have made from scratch. The theory is surely more complicated to grasp, but it certifies the whole thing won't end in fire. At the very least, you will have a research community to ask in case of difficulties.
Last edited by algogenetienne on Wed Sep 19, 2018 9:50 pm, edited 1 time in total.

Pyroatheist
Burner Inserter
Burner Inserter
Posts: 5
Joined: Wed Sep 19, 2018 3:04 am

Re: Mathematical Optimization for a fluid system

Post by Pyroatheist » Wed Sep 19, 2018 7:55 pm

algogenetienne wrote:
Wed Sep 19, 2018 7:39 pm
Hi

I am into mathematical optimization and I always feel a little off when I see an engineer come up with a complicated algorithm for a problem to which a whole mathematical field is dedicated. There is a huge amount of time lost because of the lack of communication between engineers and researchers. I would like to avoid that here.

Flow model is the way to go. It's how such problems are done in practice. And it is indeed a simple problem (school project simple in fact), provided you use the right tools. Entity based simulation can not simulate efficiently a fluid network. A fluid network is a graph, with n oriented edges (pipe section of any length) and m vertices (oil plants, pumps, tanks, pipe junctions....).

Let x be the flow in each edge, an n long vector. The flow can be negative, if the fluid is flowing against the edge orientation.
Let d be the pressure in each vertex, an m long vector.

1st Kirshoff law (= non accumulation of fluid in vertices) states that the flow coming in + the flow leaving a given node is null.
Let A be a n*m matrix (one line = one edge, one column = one vertex). If we put a +1 where an edge enters a vertex, and a -1 where an edge exits a vertex, the above condition in a circuits with no inputs or outputs is Ax = 0. In practice, there are nodes that create or consume fluid so we put that in a vector b. bj > 0 implies that the jth vertex consumes fluid (plant), bj < 0 implies that the jth vertex creates fluid (pump). Now the condition is Ax = b.

Then we want to take into consideration the loss of pressure around the pipes
With Colebrooks formula, we have the following matrix formula to know the pressure at each node.
trans(p)A + r*x*|x| = 0
With r an n long vector. ri is the resistance of ith edge; the resistance is proportional to length. * is the multiplication coefficient by coefficient so r*x*|x| is an m long vector.
Basically, it means that the amount of pressure lost in an edge depends on its length and the squared flow.

In Factorio, we know the inputs, so the bi are fixated in pumps. Let's assume the demands are satiated too
We fully know the value of b : bj is the maximum consumption of a factory, or the output of a pump, or 0 if it's a pipe junction.
The stable state of the network is the one that minimize pressure loss, so it's the solution of the following problem :

min (x . r*x*|x|) - (pt, xt)
under constraints Ax = b

with pt the pressure in tanks, which is known because it only depends on the amount of fluid in it and rt the flow coming out of tanks (we take fluid out of tanks with higher pressure in priority)

With a bit of tinkering with Ax =b, it's possible to have only x as the only variable and remove the constraint. The problem can then easily and efficiently be solved by Newton's method.

That's the general idea to have the stable flow in a perfectly balanced network.
It does not depend on the number of pipe, only on the number of edges and vertices of the network. A 50 pipe long section is as costly as a 1 pipe long one. And because you have the variable x, you know the flow in each section.


There is a bit more work when production and demand do not match and tanks are full or empty. One has to compute the consumption of each individual plant or the output of each individual pump based on local pressure.
Moreover, the problem I have just described doesn't offer any gameplay. It will give a functional network no matter the configuration, making 10000 gallons going through a single pipe every second if need be. But it is a simple base on which adding other feature later on. And there is quite a lot of literature on constrained optimization so it is possible to come up with an algorithm that will work even if pipes can not contain more than a given volume.


So please consider using an optimization system instead of something you have made from scratch. The theory is surely more complicated to grasp, but it certifies the whole thing won't end in fire. At the very least, you will have a research community to ask in case of difficulties.
This is pretty elegant. If you combine the methods here with the physical flow parameters in my implementation (like limiting flow based on maximum pressure/pipe area and linking resistance to the major losses), it might be a very effective implementation.

algogenetienne
Burner Inserter
Burner Inserter
Posts: 6
Joined: Tue Sep 18, 2018 5:41 pm

Re: Mathematical Optimization for a fluid system

Post by algogenetienne » Wed Sep 19, 2018 9:39 pm

Pyroatheist wrote:
Wed Sep 19, 2018 7:55 pm


This is pretty elegant. If you combine the methods here with the physical flow parameters in my implementation (like limiting flow based on maximum pressure/pipe area and linking resistance to the major losses), it might be a very effective implementation.
Having the fluid physically localized in the graph is quite dangerous I think, it can lead to simulation instability. Especially with each tick corresponding to a fixed delay.

Classic problem to test your program: if the delay between two game iterations is dt and the distance between two nodes is D, what happens if the fluid velocity is greater than D/dt ?

It is hard to prove that a simulation works. It is quite complicated maths. One often has to restrict the thing he is simulating in some way.
I believe that if you do not prove that it the system will work in every case, then it will break someone's factory. I'm quite a Dijkstra person.

meganothing
Fast Inserter
Fast Inserter
Posts: 126
Joined: Thu Sep 15, 2016 3:04 pm

Re: Mathematical Optimization for a fluid system

Post by meganothing » Thu Sep 20, 2018 12:17 am

algogenetienne wrote:
Wed Sep 19, 2018 7:39 pm
...
What is the difference between this and one of the proposed electrical network solutions based on kirchhoffs law? At least without additional constraints it sounds quite similar
Matthias_Wlkp wrote:
Wed Sep 19, 2018 5:24 pm
I still don't get, what is the benefit of a more realistic model for pipes. It seems that it drains a lot of resources for something that will be noticeable only, if it doesn't work...

In the end, everybody will build systems, that will resemble electrical circuits - fluid input >= output, so the pipes are always 100% full, otherwise, pipes are empty.
But fluid input > output should ideally not be enough to ensure all outputs are filled. And as bad as the current system is, it does that right at least.

astroshak
Burner Inserter
Burner Inserter
Posts: 18
Joined: Thu May 10, 2018 9:59 am

Re: Mathematical Optimization for a fluid system

Post by astroshak » Thu Sep 20, 2018 2:23 am

meganothing wrote:
Thu Sep 20, 2018 12:17 am
But fluid input > output should ideally not be enough to ensure all outputs are filled. And as bad as the current system is, it does that right at least.
I disagree. I think there is a condition that, if met, ensures that the outputs do not get all that they can :

Output demand is greater than pipe flowrate.

As long as that is NOT true, and the pipes are full, then yes, fluid input being greater than fluid output should mean that all outputs are filled. Try to push more fluid through than the pipes can handle, and you’re limited to the capacity of the pipes to carry whatever speed they carry. Demand more than the system is capable of delivering (aka demand > capacity) then of course outputs would be starved.

Its fairly simple, and I’m sure (without reading through all the formulaic stuff that was giving me a headache) that the big brains posting previous posts have already accounted for this, but the flow rate is merely the volume of the fluid within the pipe multiplied by the speed at which it is flowing.

In some ways its no different from belts, in that if you’re using yellow belts, you’ve limited your capacity to move stuff, and using a red belt has a higher limit. If you try to stuff more stuff onto the belt than the belt can carry, your inverter and Assembly Machine back up. If you try to stuff more fluid into a pipe than it can handle flow-wise, your pump will back up.

Similarly, if you have a yellow belt feeding 300 AM3’s w/ full speed beacons, the first few machines will gobble everything up and the rest will be starved. You’ll find a similar problem if you demand more from a pipe than it can handle flow-wise.

But as long as the pipe can handle the flow? By all means, YES, fluid input > demand should mean all demands are met.

By the way, in the real world, watermains (in the US, I’ve no knowledge of elsewhere but I can’t see them being too different, unless other countries use a different underlying philosophies) start out larger near sources, and get smaller as they go out from the plant in the distribution system. This ensures sufficient flow and pressure. You can get millions of gallons per day through larger pipes, but smaller pipes have much smaller flow capacities for a given system pressure. That’s why fire suppression systems are usually a larger diameter pipe than the drinking water systems for the same building or complex. What does this mean for Factorio? Different pipes could easily have different flow capacities, and if ever such should happen, I hope that the capacity would be indicated somewhere.

revy
Manual Inserter
Manual Inserter
Posts: 1
Joined: Thu Sep 20, 2018 3:34 am

Re: Friday Facts #260 - New fluid system

Post by revy » Thu Sep 20, 2018 4:03 am

Reading this reminds me of load flow analysis in the power grid. It's similar to the method you're describing at where you lump all the lines between nodes into a single entity with an equivalent impedance (or admittance which is 1/impedance). The fluid equivalent of voltage is pressure and the equivalent of current is flow. In this type of analysis you would have certain things that you know (pressure at a group of locations "A" and flow at some other group of locations "B") and you have certain things that you don't know (flow at "A", pressure at "B"). You would then calculate the admittance/impedance matrix and invert it and multiply the vector of stuff you know by the inverse of the admittance/impedance matrix to find out the info you don't know. Matrix inversion is a well understood process which has many direct and indirect algorithms well established. You would only need to re-calculate the matrix inverse when the network changed and you would only need to re-solve the system of equations when the inputs changed (e.g. a flow on an oil-well decreased or a pump starts loading/unloading a fluid wagon).

https://en.wikipedia.org/wiki/Nodal_admittance_matrix
https://en.wikipedia.org/wiki/Zbus

Modeling in this way neglects the system dynamics (at each time step you calculate the voltage/current of all nodes and the values are instantly updated). If you wanted to preserve dynamics (i.e. pipes take a finite amount of time to fill) you would need to do a state-state representation of the system. This would increase the complexity, and would definitely allow for some whacky dynamic things to happen (flow oscillations), but you could do exactly what you say, treat sections of pipe between nodes as a single entity to reduce the complexity. Also like the above method the state-space matrices only change when the network itself changes.

https://en.wikipedia.org/wiki/State-spa ... esentation

Good luck!!

mrvn
Smart Inserter
Smart Inserter
Posts: 2579
Joined: Mon Sep 05, 2016 9:10 am

Re: Mathematical Optimization for a fluid system

Post by mrvn » Thu Sep 20, 2018 8:59 am

algogenetienne wrote:
Wed Sep 19, 2018 7:39 pm
...
Then we want to take into consideration the loss of pressure around the pipes
With Colebrooks formula, we have the following matrix formula to know the pressure at each node.
trans(p)A + r*x*|x| = 0
With r an n long vector. ri is the resistance of ith edge; the resistance is proportional to length. * is the multiplication coefficient by coefficient so r*x*|x| is an m long vector.
Basically, it means that the amount of pressure lost in an edge depends on its length and the squared flow.

In Factorio, we know the inputs, so the bi are fixated in pumps. Let's assume the demands are satiated too
We fully know the value of b : bj is the maximum consumption of a factory, or the output of a pump, or 0 if it's a pipe junction.
The stable state of the network is the one that minimize pressure loss, so it's the solution of the following problem :

min (x . r*x*|x|) - (pt, xt)
under constraints Ax = b

with pt the pressure in tanks, which is known because it only depends on the amount of fluid in it and rt the flow coming out of tanks (we take fluid out of tanks with higher pressure in priority)

With a bit of tinkering with Ax =b, it's possible to have only x as the only variable and remove the constraint. The problem can then easily and efficiently be solved by Newton's method.
...
While this sounds simple I think it is completely impractical computation wise. First the matrix A will often be huge. A simple oil refinery easily has 100 nodes in the graph. For a nuclear power plant I wouldn't be surprised to see 1000-100000 nodes. So doing even one newton iteration on this will be costly.

Next none of the sources or drains are constant. They produce or consume a set volume in a single tick and then pause. So there never is balance point to reach. Every tick needs to evaluate everything again and again. On top of that you have pumps that drain everything available on one side and output it on the other. Worse with circuit controls. Turning off a pump basically cuts an edge in the graph.

Trying to find an optimal flow across a pipe network is a pipe dream. It changes too much to make sense.

Lastmerlin
Long Handed Inserter
Long Handed Inserter
Posts: 55
Joined: Thu Jun 16, 2016 11:02 am

Re: Friday Facts #260 - New fluid system

Post by Lastmerlin » Thu Sep 20, 2018 9:40 am

What is described here is the difference between an implicit (solve it all with a big equation system) and an explicit (small local updates) solution of the system. Implicit sounds good, because you get the whole solution at once, and its globally correct - but i believe its not the right decision here.

First: Implicit it superior for steady state solution. Thats why all those who propose it like to pretend that factorio pipes are mostly steady state. I do not believe that.
Second: The big drawback of explicit is the small timestep size. This does not really matter here, because you need to do small timesteps anyway.
As already estimated: By using any implicit algorithm, equation systems of more than 10000 unknowns can easily arise. This does not sound a lot, but if you try so solve it every step, it really hurts.

Finally: Whatever system gets chosen, one of my main concerns is again: Better opportunity for modding improved pipes. Several have mentioned Bobs/Angels and how the fluid system gets a nightmare there. This is mainly due to the fact, that none of the dozens of new pipes introduced there is really good. Given the fact that bob is an excellend modder I conclude that there are just no good parameters available for tuning right now. Please have a look at this.

McDuff
Fast Inserter
Fast Inserter
Posts: 123
Joined: Sun Jan 11, 2015 11:09 am

Re: Friday Facts #260 - New fluid system

Post by McDuff » Thu Sep 20, 2018 10:59 am

Lastmerlin wrote:
Thu Sep 20, 2018 9:40 am
What is described here is the difference between an implicit (solve it all with a big equation system) and an explicit (small local updates) solution of the system. Implicit sounds good, because you get the whole solution at once, and its globally correct - but i believe its not the right decision here.

First: Implicit it superior for steady state solution. Thats why all those who propose it like to pretend that factorio pipes are mostly steady state. I do not believe that.
Second: The big drawback of explicit is the small timestep size. This does not really matter here, because you need to do small timesteps anyway.
As already estimated: By using any implicit algorithm, equation systems of more than 10000 unknowns can easily arise. This does not sound a lot, but if you try so solve it every step, it really hurts.

Finally: Whatever system gets chosen, one of my main concerns is again: Better opportunity for modding improved pipes. Several have mentioned Bobs/Angels and how the fluid system gets a nightmare there. This is mainly due to the fact, that none of the dozens of new pipes introduced there is really good. Given the fact that bob is an excellend modder I conclude that there are just no good parameters available for tuning right now. Please have a look at this.
+1

algogenetienne
Burner Inserter
Burner Inserter
Posts: 6
Joined: Tue Sep 18, 2018 5:41 pm

Re: Mathematical Optimization for a fluid system

Post by algogenetienne » Thu Sep 20, 2018 12:00 pm

mrvn wrote:
Thu Sep 20, 2018 8:59 am

While this sounds simple I think it is completely impractical computation wise. First the matrix A will often be huge. A simple oil refinery easily has 100 nodes in the graph. For a nuclear power plant I wouldn't be surprised to see 1000-100000 nodes. So doing even one newton iteration on this will be costly.

Next none of the sources or drains are constant. They produce or consume a set volume in a single tick and then pause. So there never is balance point to reach. Every tick needs to evaluate everything again and again. On top of that you have pumps that drain everything available on one side and output it on the other. Worse with circuit controls. Turning off a pump basically cuts an edge in the graph.

Trying to find an optimal flow across a pipe network is a pipe dream. It changes too much to make sense.
Yes, I forgot that Newton's method requires to invert the hessian, so it would grow more than quadratically with the number of edges.
But a gradient descent should work quite well too, and its complexity would be linear with the number of edges, which is similar to the current system.
Now, the number of needed iterations for convergence might be a problem, but since we start our descent at the solution of the previous instant, it should converge rapidly if the demands haven't changed to much.
In fact, only doing 10 gradient descent iterations each tic would give some sort of time continuity, but the stability and consistency (not sure it translates well) of such a simulation would have to be investigated

Pumps wouldn't be that hard : it is a constraint input flow = output flow, and we can put a constraint flow = 0 too.

But it would surely be complicated to add this to the current pipe circuit. There are big chunks moving around in empty pipes and being gulped instantly by plants, it is not how actual pipes work.
I believe that if there was a simple modelization of a tank (pressure = f(volume)), we could make a very realistic pipe network by providing each plant and pump with its personnal tank. If pressure is too low, the tank of a plant does not get filled and the plant does not work, so you have to put pumps like in real life.
Last edited by algogenetienne on Thu Sep 20, 2018 12:27 pm, edited 6 times in total.

meganothing
Fast Inserter
Fast Inserter
Posts: 126
Joined: Thu Sep 15, 2016 3:04 pm

Re: Mathematical Optimization for a fluid system

Post by meganothing » Thu Sep 20, 2018 12:02 pm

astroshak wrote:
Thu Sep 20, 2018 2:23 am
meganothing wrote:
Thu Sep 20, 2018 12:17 am
But fluid input > output should ideally not be enough to ensure all outputs are filled. And as bad as the current system is, it does that right at least.
I disagree. I think there is a condition that, if met, ensures that the outputs do not get all that they can :

Output demand is greater than pipe flowrate.
I don't get what you are driving at. The OP I was answering to made a general statement about ALL models and your assertion that outputs don't get all they can if output demand is greater than pipe flowrate makes no difference at all aka never happens if pipe flowrate in a model is infinite.

And many models proposed do not restrict flowrate in any way.

Note I was answering to two different people on two different subjects, maybe I should have split the post into two.

algogenetienne
Burner Inserter
Burner Inserter
Posts: 6
Joined: Tue Sep 18, 2018 5:41 pm

Re: Mathematical Optimization for a fluid system

Post by algogenetienne » Thu Sep 20, 2018 1:12 pm

So I have run little test using scilab code I have.
I have a pipe network of 22 edges and 16 nodes and I want to find the optimal flow from scratch.
I consider that I have converged when my gradient is smaller than 0.01 (no need to be excessively precise)
I run on one thread for some reason, my scilab looks poorly optimized

With a gradient descent, it takes 0.09 second to find the optimal flow with 1600 iterations
With a Polak-Ribière nonlinear conjugate gradient method, it took 0.03 second with 190 iterations

Both methods complexity grow almost linearly O( n ln(n) ) with the number of edges, so I expect that it will take about 30 seconds to find the perfect flow in a 1000 node power plant with a poorly optimized scilab. But that is used to find the optimal flow from scratch, if you have the optimal flow from last iteration, it should go faster.
The most elegant would be to define a set of equation such that it converge to the optimal flow after a transitory state in such a way that the approximation obtained after a 10 descent iteration corresponds to the transitory state.

If reworking the pipe network is going to take a whole month, I believe this is worth investigating for a few days
Last edited by algogenetienne on Thu Sep 20, 2018 1:54 pm, edited 2 times in total.

Matthias_Wlkp
Long Handed Inserter
Long Handed Inserter
Posts: 96
Joined: Mon Oct 10, 2016 11:28 pm

Re: Mathematical Optimization for a fluid system

Post by Matthias_Wlkp » Thu Sep 20, 2018 1:49 pm

meganothing wrote:
Thu Sep 20, 2018 12:17 am
But fluid input > output should ideally not be enough to ensure all outputs are filled. And as bad as the current system is, it does that right at least.
This is not the point.

You are right - putting more in than you need is not enough to ensure satisfaction at the output.

My point is - fixing that is very simple (add more pipes), so every time you will end up with pipes 100% full and all outputs satisfied.

I don't see why do we need realistic (and possibly buggy) fluid handling just to be occasionally prompted to add more pipes.

Avezo
Filter Inserter
Filter Inserter
Posts: 365
Joined: Fri Apr 01, 2016 3:53 pm

Re: Friday Facts #260 - New fluid system

Post by Avezo » Thu Sep 20, 2018 4:03 pm

Charidan wrote:
Fri Sep 14, 2018 6:19 pm
Turning pipes into segments is basically zero cost with positive gain. You technically need to spend some time calculating the segments, but you only do that when placing or removing pipes, so during the update tick there is no logic cost at all; you just iterate over the already existing segments the same way you would iterate over the set of all pipes in the old system. It might not do much for nuclear power, but it at least helps for refining a little and has great return on transit pipes.
Those short pipe segments are not the main point, the problem is that juntions become more UPS demanding under new system. It's not zero-cost.

Optimized builds (including oil fields) already work very close to having single straight pipe segments as in suggested model thanks to underground pipes, so new system might make it work worse, due to UPS strain from junctions that would add up.

As I understand FFF, it all comes down to what model Dominik uses to compare new fluid system to old.
If it have vastly more pipe segments than junctions - New one would be an improvement, UPS saved on pipes would overweight strain from junctions.
If it have vastly more junction segments than pipes - New one would be a downgrade, UPS saved on pipes would be overweighted by strain from junctions.

Given the examples he used as an illustration, I'm afraid he assumed there is vastly more pipes in average build than junctions, whereas from my game experience it's the opposite, thus I dropped few screenshots as an example.
Image

pleegwat
Fast Inserter
Fast Inserter
Posts: 107
Joined: Fri May 19, 2017 7:31 pm

Re: Mathematical Optimization for a fluid system

Post by pleegwat » Thu Sep 20, 2018 5:08 pm

mrvn wrote:
Thu Sep 20, 2018 8:59 am
Next none of the sources or drains are constant. They produce or consume a set volume in a single tick and then pause. So there never is balance point to reach.
I'm not sure that assumption is necessarily valid. Assembler progress each tick is already dependent on the amount of power satisfaction they get; fluid input could probably be adapted to do the same. I don't know if that'd be worth it for realism's sake, but I do think it'd be worth it if it helps fluid system performance.

I do think interdependencies like that should have a tick delay if at all possible to decouple the various aspects of the simulation.

Post Reply

Return to “News”