Let me clarify the belt algorithm I posted earlier. Since no one commented I may have failed to explain it clearly.
We would like to retain the ability to quickly check a specific region of a belt segment for items. If we can store the position of an item, we can apply a binary search on the item buffer for those positions.
The items on a belt can be separated into two ranges: the freely moving items (range0), and the blocked items at the end of the belt, which move slower or not at all (range1). When freely moving items collide with the blocked items, they migrate from range0 to range1.
Keeping track of these ranges is easy. We let an index into the item buffer point to the last item in range0. When items collide into range1, this index is decremented to reflect the change.
For the purpose of storing item positions, note that the positions of items in either range, relative
to each other, never change. Or put differently: when the absolute positions change, they all change by exactly the same amount. Therefore, for each item we can split the absolute position into a constant
and a variable
. Each range has its own shift
, but the shift
is shared between all items in the range.
Item absolute positions can be converted to relative and visa versa using:
Code: Select all
item[i].xRel = xAbs - belt.shift0;
xAbs = item[i].xRel + belt.shift0;
item[i].xRel = xAbs - belt.shift1;
xAbs = item[i].xRel + belt.shift1;
When an item migrates from range0 to range1, its xRel
is recalculated using
Code: Select all
item[i].xRel = item[i].xRel + belt.shift0 - belt.shift1;
Every tick belt.shift0
is incremented, while belt.shift1
is only incremented when an item can leave the belt.
cannot be incremented, we need to check for item collision. The collision check is cheap, but can be further optimized by caching the gap size between range0 and range1 into a belt.gap
variable. Only when this reaches 0 migration needs to be performed. Migration is also cheap. The index to the last item in range0 is decreased, and item[migrating].xRel
is adjusted by (belt.shift0 - belt.shift1)
When the belt needs to be checked for items on position xAbs
, range0 can be binary searched for a value xRel
equal to (xAbs - belt.shift0)
and range1 can be binary searched for a value xRel
equal to (xAbs - belt.shift1)
. This is the advantage over storing distances between items. Two binary searches can be used to find an item instead of having to iterate and sum distances. This should allow for much larger belt segments.
Also the code should be easier to read, understand, maintain and reason about.
But I suppose I might be overlooking something, otherwise the Factorio devs would probably have taken this approach. If anyone can tell me what I'm missing I would be grateful.