algogenetienne wrote: ↑
Wed Sep 19, 2018 7:39 pm
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.