nyatalily (Natalie)#FactoryGame
Ok. So. Conveyors hard. Well. Performant conveyors hard.
---
There's the relative distance approach. Items track the distance to the next item on thr belt. This means you only need to update the distance of the first item on the belt, and the other items are updated as they're effectively relative to it. To my knowledge, this is the approach factorio uses (these days,).
Pro: Cheap to update, cheap to change belt length, arbitrary belt length
Cons: Viewing, inserting items or extracting items requires iteration of items from the head to the relevant distance along the belt.
Con mitigations: Caching (last time we were waiting for item #18 and it was 5 units away, don't check until we think it should have arrived or an item is inserted between 17 & 18 or of 18 is removed before it gets to us ie.)
Con mitigation con: ow. no thanks. exploiting temporal coherence is an exercise left to the reader.
---
Then there's the timestamp approach. It's an evolution of the relative distance approach. Instead of tracking relative distance, you mark the timestamp it would reach the end of the belt at, if unobstructed. To resolve the position of an item you pick the higher value of: a) the time between it's end time and the current time, and b) the # item in the queue it is. B ensures items don't overlap, and instead accumulate at the head of the belt.
Pro: Less iteration required, belts have 0 update cost
Con: Factorio maps have already run long enough that 32bit timestamps aren't enough, lengthening/shortening belts from the head is expensive, arbitrary belt length
Con minimisation: when the 32 bit timestamp is hit pause the game and adjust timestamps to exist closer to zero, when lengthening or shortening belts track the "time offset" (apply to all belt timestamps when save/load or offset limit hit)
Con minimisation con: gross, but the second one is probably fine
---
The approach I came up with is what I call the occupany map approach. We represent each belt as a 32/64 bit interger. We do some shifting magic involving
Pros: updates are cheap (like 4x 1 clock cost instructions), memory footprint amortizes well (64bit/63 items*, ~1 bit per item vs 32bits/item), position of items is explict and absolute.
Cons: belt lengths are limited, machines without the BMI1 instruction set will have less terse asm
Con mitigation: we'll get into this with my next post because this is what I've been scraping my face against
* 31/63 items is due to needing to reserve the top bit to cause 1s to shift in naturally, instead of requiring a branch
- posted by Natalie
Ok. So. Conveyors hard. Well. Performant conveyors hard.
---
There's the relative distance approach. Items track the distance to the next item on thr belt. This means you only need to update the distance of the first item on the belt, and the other items are updated as they're effectively relative to it. To my knowledge, this is the approach factorio uses (these days,).
Pro: Cheap to update, cheap to change belt length, arbitrary belt length
Cons: Viewing, inserting items or extracting items requires iteration of items from the head to the relevant distance along the belt.
Con mitigations: Caching (last time we were waiting for item #18 and it was 5 units away, don't check until we think it should have arrived or an item is inserted between 17 & 18 or of 18 is removed before it gets to us ie.)
Con mitigation con: ow. no thanks. exploiting temporal coherence is an exercise left to the reader.
---
Then there's the timestamp approach. It's an evolution of the relative distance approach. Instead of tracking relative distance, you mark the timestamp it would reach the end of the belt at, if unobstructed. To resolve the position of an item you pick the higher value of: a) the time between it's end time and the current time, and b) the # item in the queue it is. B ensures items don't overlap, and instead accumulate at the head of the belt.
Pro: Less iteration required, belts have 0 update cost
Con: Factorio maps have already run long enough that 32bit timestamps aren't enough, lengthening/shortening belts from the head is expensive, arbitrary belt length
Con minimisation: when the 32 bit timestamp is hit pause the game and adjust timestamps to exist closer to zero, when lengthening or shortening belts track the "time offset" (apply to all belt timestamps when save/load or offset limit hit)
Con minimisation con: gross, but the second one is probably fine
---
The approach I came up with is what I call the occupany map approach. We represent each belt as a 32/64 bit interger. We do some shifting magic involving
blsr, which causes the bits to shift right but to never shift 0s out, causing them to accumulate. 0s represent items on the belt and their position, and the number of 0 bits before an item determines its index in an array.Pros: updates are cheap (like 4x 1 clock cost instructions), memory footprint amortizes well (64bit/63 items*, ~1 bit per item vs 32bits/item), position of items is explict and absolute.
Cons: belt lengths are limited, machines without the BMI1 instruction set will have less terse asm
Con mitigation: we'll get into this with my next post because this is what I've been scraping my face against
* 31/63 items is due to needing to reserve the top bit to cause 1s to shift in naturally, instead of requiring a branch
- posted by Natalie
/~gfaster 
