4 ms·

I was wondering, what's the "right" way to run a Factorio-like simulation, algorithmic ally speaking? I.e. You have conveyor belts bringing items to/from produc

• amelius 6y ago
  I suspect the answer can be found in how more general physics engines work. https://en.wikipedia.org/wiki/Physics_engine https://en.wikipedia.org/wiki/Physics_engine
  • tgb 6y ago
    I'm imagining a discrete system here, like a tile-based map. I haven't actually played Factorio, so I'm just assuming that's how it works (seems like it from the link a sibling post gave). As such, I'm not sure physics engine share much in common here.
    • duskwuff 6y ago
      It's not as simple as a tile-based map. Structures are built on a square tile grid, but objects on belts move at a much finer resolution, and have a bunch of specific behaviors (moving in two lanes, being picked up or dropped onto belts by inserters, belts merging into other belts, etc). Older versions of the game actually used an even more flexible physics engine for objects on belt (not restricted to two lanes), but that was deemed unnecessarily complex -- and the current model is much more performant.
• skitter 6y ago
  Not quite what you were asking for, but Factorio updates only segnebts of belts (made of multiple tiles) wuthout touching the items: https://www.factorio.com/blog/post/fff-176 https://www.factorio.com/blog/post/fff-176
• jcranmer 6y ago
  The general way you design simulation is that you have a master list of entities (each inserter, conveyor belt, etc. is a different entity), and each type of entity has its own doTick code that updates each tick. Then the very first optimization you implement is realizing that most entities don't do anything most of the time, so you segregate the list into active and inactive entities and only process active entities each tick.
  • tgb 6y ago
    Right, but what's in the doTick of a conveyor belt cell? Presumably it would look something like: if nextCell.isEmpty(): moveContentsToNextCell() But what happens when you have A connected to B connected to C and A and B have items? It depends upon the execution order of A and B's doTicks(). If A's runs first then B is still full and so A can't advance its contents. If B's runs first, then it passes its contents to C and then can receive from A when A runs. You might put the entities into a graph, order them by their connections and run the doTicks in the right order. But you can't do that if there are loops in the conveyor belts (which Factorio handles, at least). I haven't come up with a trivial modification of this scheme to handle these problems. Do you have to do multiple passes until everything has gotten a chance? Or maybe a priority queue? I'm not sure. And what if the loop is entirely full? It should advance all the contents one square but may instead get jammed.
    • jcranmer 6y ago
      There's often a deterministic order of evaluation, to support multiplayer (you want every client to get the same results in all cases). > And what if the loop is entirely full? It should advance all the contents one square but may instead get jammed. In Factorio, it jams.
      • tgb 6y ago
        But what deterministic order do you use? Any order seems problematic to me, once loops are involved. Certainly if you just pick a naive order like "lowest entity ID runs first", then you end up with a lot of items not moving when they should, since the cell in front of them is still full even though it'll empty later this tick. And what would you do if you want the entirely full loop to not jam? It sounds possible, probably even simple, but I haven't seen how. A solution to this problem is orthogonal to the points you've raised.