How does the conveyor belt lane internal work?

[static sparrow]

There is something I always wondered about:
How Factorio dealt with merging single conveyor belt blocks with others to a lane? I know there was a FFF about it, but it explained only the rough logic instead of showing some clear code. Since I guess they use its own engine, they used some refined version of ECS. So I guess every belt object have its unique component, but what about lanes?

Factorio internal conveyor belt lane work

How does the conveyor belt lane internal work?

[sinful otter]

Did you read https://www.factorio.com/blog/post/fff-364 ?

no one here can give you actual code, as that is all closed source

[static sparrow]

Yeah I did but I hoped some "basic" code examples. Because honestly I have no clue how to code this for my own game, but I had already this logical idea.

[sinful otter]

https://www.factorio.com/blog/post/fff-176 has some more details on actual implementation

[static sparrow]

I refined it even more for my own game, still I have no clue how to add a "lane component" to multiple belts

Oh yeah I read that also

This is inefficient, I overworked that part.

The main question for me is just: how to add and handle a single lane component for multiple conveyor belt blocks?

@sinful otter do you know which of the devs made that part? Maybe I could try to ask in pm about a rough idea how to handle it.

[sinful otter]

Harkonnen, judging from the FFF and team description on the website, but they're not with Wube anymore. Boskid seems to have last done work on them with the multithreading.

[static sparrow]

Aww damn ... thank you

[white leaf]

I am an expert, give me questions and i maybe will respond tomorrow

[static sparrow]

Oh thank you very much

Well I have an ECS similar engine, just with some additions like archetypes how works like a single component for multiple entities. The issue is just, I do now know how to handle lanes. My game can construct a new object with new components and link it to an existing archetype, however it can yet not handle something special like lanes.

I know it must check somehow if multiple conveyor belts are in a lane. The check itself is not that hard for the first time. It adds the belt and check if there is another belt in front, left, right, behind and such ... Here it would be also interesting to know how Factorio adds different object types into the world map (what check are done and such).

The issue is just, how to merge this all into a single lane and keep it flexible (when something at begin, end or in the middle is deleted for example).

The second issue is, how to update them well, you can not update them randomly, you must update them in the right sequence, else it seems like a belt is falsely occupied.

[exotic stratus]

no idea how it actually works in Factorio - but here's my bet anyway:

1. all belts in one system connect into a graph, where node is any intersection between belts
2. graph nodes has queues to store amount of items moved on them, one record per one belt section, each X ticks you need to move front value to next nodes (if there's space, otherwise compacting queue is necessary), and receive new value from previous nodes
3. each belt sector have records on which graph it is part of, which node is a "parent node", and his number on the queue
4. if belts require drawing on screen - they receive information from graph, then from node, then from queue
5. if any change to system is made - assigned for changed belts graph need to be rebuild

really interested, how far I'm off with this

[static sparrow]

Well thats nice from you but this doesn't answer deep coding related questions xD
It sounds very easy but you have to be aware of a lot, like splitting up and merging belts (and so segments)

[exotic stratus]

splitting should work like this (in system above):

1. convert system to graph - picture 1 to picture 2, where circles is nodes of the graph
   basic algorithm idea is: starting left to right: if you encounter regular belt - extend length of the segment on parent node, if you encounter splitting/merging - create node. any cycle prevention algorithm will be necessary for regular cycles - and for situation like that, when you might want to go backwards on second belt to see where it's connected

not sure if it's detailed enough, but - here it is)

on updating it - entire graph update each tick should do

[white leaf]

Ok i am now on my PC so i can type walls of text more comfortably

Transport lines structure as it is in factorio when knowing all the details is a really simple structure

First lets just define a TransportLine: it is an abstract holder of items at various positions. It knows what is the speed of that line (so during update it knows by how much items should be shifted forward) and it knows its own total length. Single TransportLine may hold multiple items and for every item there is a position stored for that item on that line

TransportLine is just an abstraction of a straight line segment with points on it that are moving one way, and it is heavily optimized for the most basic operations like moving items forward: items do not store their absolute position on a line because that would require iterating entire line when all items are to be shifted by the same amount: for that a line keeps distance to first item measuring from the front of the line (where items go off the line), distance to last item (so it is easy to see if more items can be inserted from the back) and every item that is not last knows a distance to the previous item

For simplification lets assume a transport lines are entirely within a single entity (obviously not true in factorio but that is good for explanation to avoid unnecesary details right now)

transport belt connectables (class of entities that can connect with other belts) may have multiple lines on them, this is just a matter of having more of them held in an entity state. Amount of transport lines is observable from outside (in Lua you can see this by checking https://lua-api.factorio.com/1.1.101/classes/LuaEntity.html#get_max_transport_line_index) and it is possible to obtain every transport line of that entity independently by the index

for example a TransportBelt has always 2 lines: a left one (with index of 1) and right one (with index of 2)

TransportBelt creates 2 transport lines for its own purposes, sets their speed based on the prototype, sets their lengths based on the belt shape and that is most of the important stuff happening with transport belts for the current stage of explanation

Main glue that makes transport lines interesting is set of 2 functions: one is transport line position function, which is a function specific to given entity at given position, given direction and given shape: it takes (TransportLineIndex, TransportLinePosition) and converts it into MapPosition

this is basically how items on transport lines know where to draw on the screen and this is how inserters know where the items are so they can start chasing them. This is also used when a character goes into vacuum mode (holding "F" to pickup items around): it searches for entities around and if they are belts, character iterates over all lines, for each line goes through each item and if an item position is within character's vacuum range the item is taken from the line and into character's inventory

second function is the opposite, its an item insertion specification function: given a MapPosition, it provides (TransportLineIndex, TransportLinePosition) where the item should be inserted when it is dropped at that entity on provided map position

that way inserter dropping items on a belt knows on which lane it should insert an item and at what position along that lane, same as mining drills and player dropping items on belt

for the interactions, every transport line during entity setup is connected to other transport lines. Transport line knows what transport line it feeds into (when item moves from the front of the line, it is inserted into that line), it knows which line it is fed from directly (so if the items were moved it knows which line should be activated so the items start moving recursively) and it knows which lines are feeding it from the sides (so if there is a gap between items on a line, it can also activate those side interactions so they can try to fill the gaps on a line).

Transport line group is just set of multiple transport lines that have connection in any way between them: if one line feeds directly another transport line, they are both part of the same group. In that sense it is a graph: transport lines are vertices and points of contact represent edges)

transport lines connecting to other lines in factorio is a relatively complex piece of logic that consists of 3 stages: first is neighbour discovery, where a transport belt connectables searches for neighbours at its north/east/south/west and remembers them. By having those neighbours found it removes need from repetitive entity searches later. Second stage is update shape: given all the neighbours a shape is selected (this is only used for transport belts, at this stage when transport belt sees it has a left neighbour (if belt goes east, neighbour on the north is its left neighbour) pointing into us and there are no right and back neighbours pointing us, belt decides to select a left turning shape which affects selection of the item position function, item insert specification function and affects exact lengths of left and right lines). After shape is set, there is third stage where a lines are connected. Here a belt that has outgoing lanes goes to its neighbour at the drop position and says "this is my left and my right output lane, please connect them to yourself" and the other belt connectable sets connections: either its a direct connection (for example when east belt goes onto another east belt), its a side connection (for example south belt drops onto east belt that is straight because of other neighbours) or the target may decide to not connect given line (for example underground belt when side loaded only connects one lane that goes into the hat opening from the side, the other line is not connected)

transport lines that span multiple entities is an optimization that tries to keep amount of transport lines that need to update as few as possible because if moving entire line content is just O(1), having less amount of lines to update is better

here there is a small amount of indirection: there exists a "transport line connector": its just a pointer to a transport line but it also contains a range of positions of that line that belong to this particular entity

so if you have 3 belts of the same speed, at the beginning each of them will contain a pair of 1 tile long transport lines, but later a manager may see that this structure is not optimal, will allocate one line that has length of 3 and will replace those lines in the transport belt connectables: first belt will be told "use this line, your range starts at 2 and ends at 3", second belt will be told "use this line, your range starts at 1 and ends at 2" and last will be told "use this line, your range starts at 0 and ends at 1"

there is also opposite mapping: transport line knows all entities it goes through, so if an item of that long line is to be drawn, it is possible to obtain specific entity that owns this specific section of transport line so a correct item position function can be obtained and from this a correct map position of an item can be obtained and rendered

Simple, isn't it?

[exotic stratus]

I'm off, but not insanely off

[toxic slate]

Thank you for this interesting Factorio Saturday Fact.
Had a rough idea about transport lines before, this is obviously more in-depth. and ofc simple :)

[static sparrow]

And how is this dealt? Those are 2 segments (green and red arrows) but how does green pass something into the red segment? How is the blue arrow processed?

Also thank you very much. The first part was honestly that what I already guessed but the second part was very usefully.

[white leaf]

This is simple, green line is connected as side loading onto red line (when connecting to belt with red line that belt decided it has straight shape so when it was asked to connect lines from the top belt they are registered as side loading)

As for the update, when green line updates it knows it is side loading and it knows at what position it is side loading. That side line just tries to insert item into red line and if that fails the item stays at the front of green line

[static sparrow]

but I noticed that sometimes side loads block the main load under special conditions

[white leaf]

Red line knows all side interactions so if there are gaps it can activate side lines so they start updating

Those are update order artifacts, sometimes back line may update first, then front line updates creating a gap and side line updates filling the gap

[static sparrow]

ah

So to summary this, every belt basically stores an id which lane it uses and (probably also an id) the local position in the segment?

And the segments stores which segments it have in front and which side loads it have?

[white leaf]

Line knows what it has in the back, what it has in the front and what it has on the side. Entities have multiple lane connectors which point at transport lines and tell what range of positions belong to that entity

Line front may be a direct connection (when it connects to the back of other line) or be a side connection

[static sparrow]

I see
Honestly I have the feeling it feels more bulky as it should be, but as long as it works.

My first main idea was to use a round array to store the IDs of the items on the belt and then it basically just updates the first iterator position of the array, instead of moving the whole array.
You also have an ID of the next lane (to recursive update them, as you told), but I didn't saw yet a reason to store all the side loads and the back. ... but maybe there is an issue I do not see yet?

But it was honestly really helpfully to know what every entity stores, I feel stupid now because it seemed so simple. xD

[static sparrow]

Also btw about this, why is the segment size limited to only 10 entities? Why not as long as possible and draw then that whats on screen? It would theoretically lower the load a lot more.

But yeah I think an issue about round array in factorio would be that there are 2 lanes (my game just uses one)

[exotic stratus]

hm, why use round array instead of queue?

[static sparrow]

Well in queues every elements are usually skattered in the heap and they are just holded together via pointers. This means the computer have to jump a lot in the ram to call the right elements. This makes queues much more flexible to add or call elements, but horrible to iterate over.
Arrays are always bounded together, so you have every element next to each other, the computer can call every single element super quickly.
And round array, because the size of the array stays constant (except you add or delete an entity) and you can still call every element really quickly. This is incredible fast and data dense.

[exotic stratus]

yeah, my brain skipped the part where you might want to get fast access to random part of the belt - good call

[static sparrow]

Ah now I understand why the size of the segments are limited to 10.
In an array you can call an element basically via the pointer to the first element and then move by X. In queues you have to call every single pointer to get the right element. This needs a lot more time. So the bigger the size, the more the performance drops.

@white leaf thank you very much, I know now how to continue ^^ I stucked there for a long time. xD

[white leaf]

We are using CompactDeque, custom implementation of a deque on top of a vector, its a circular structure which may reallocate if there is not enough free space to insert more

[toxic slate]

@livid ivy can tell you how to force that sideloading bug. or how to prevent it from happening

[static sparrow]

ah okay, this sounds still a bit bulky tbh.

I mean it checks always if the size still fits. I mean okay, maybe more like a point of view. But I would like to avoid it.

[static sparrow]

Mind to tell which library you uses for Factorio? I don't know if thats a secret.

[white leaf]

Lines can span at most over 200 entities but we may split earlier because side interactions are expensive as item positions needs to be computed by accumulating distances between items, so inserters dropping cause line to be split at most 3 tiles away and side loading belts force lines to be split at most 2 tiles away

[static sparrow]

ah

[white leaf]

We have a lot of custom containers implemented in house

[static sparrow]

Ah cool
I'm doing the same, because I know then at least how it works and can fix possible issues (or squeeze a bit more performance out of it)

@white leaf ah one more and last question (before I forget it):

If you add or remove entities, what will happen each to affected lanes? I know you have to split, merge, increase or decrease the size, but how is this handled? I do not think it will check every tick if lanes could be merged.

[white leaf]

Lines unmerging is just a single call, it causes one line to unmerge immediately into 2 lines, either in front or in the back of current entity's connector

When entity is to be removed, it unmerges all lines going through it which exposes connection in front and in the back which then can be simply disconnected to break a connection and release an entity

Line merge and line ummerge operations have to implemented for this to work

Opposite is different, by default entity built will connect lines but merge is not immediate. For this entity requests a manager to look at the lines later and the manager may decide to merge lines or not

[static sparrow]

how does this "request" work? Thats the part where I also stuck

[white leaf]

Its just a record "please take a look at this line after tick X", manager after that tick looks at that line and other lines in front and in the back to decide if merges and unmerges are needed

[static sparrow]

Curiously, how do you leave this message? Do you register this entity in an array somewhere or how?

Ah now I understand why the "last" lane is also important to know.

[white leaf]

This goes too deep into implementation details, i wont describe it

[static sparrow]

Ah okay, I get it. Thank you for all!

[livid ivy]

https://media.discordapp.net/attachments/579345487837003836/1191043610725068962/image.png

Make a transport line break happen right before the sideload and you'll get this issue.

It doesn't always happen, and it generally self corrects after a bit, but that assumes that you have continuous supplies and the downstream output is free flowing. It's very possible to create scenarios where this results in inserters being unable to consistently fill a belt.