8 ms·

B-trees in Factorio

330 points by hellorashid 3y ago

ivanjermakov 3y ago
I thought author will implement it with Factorio's circuitry..
pram 3y ago
You could do this all with splitters, don’t need the boxes and filter inserters. Nice explanation!
- deathanatos 3y ago
  How? They're not just trying to split an output into multiple lanes. The boxes represent the item stored in that "node" of the B-Tree (laid out here in 2D). I haven't had time to watch the video, but the prose & screenshots indicates there is associated logic on the inserters to maintain the "sorted" nature of the tree, by sending stuff down the appropriate path to child nodes. Given the OP's choice of values for keys … you could use splitters to do the splitting, but IIRC splitters only accept a single filter, and so you'd need many of them at each junction (as many as items at that junction). Filter-serters permit several filters, which is a bit nicer here. (You can see that in first screenshot.) (Unless you just forgo the entire B-Tree design and just n-splitters to sort into n boxes … but that's boring and I think isn't what the OP is going for.)
  - dragontamer 3y ago
    The fastest "filter inserter" in modern Factorio meta is the splitter, which operates at full speed of the belt. There's almost no reason to use inserters for belt-to-belt transfers for modern meta, aside from a few speed-running stats where you use red-inserters while skipping logistics2 or something. But if you're trying to sort items on a belt by placing them onto another belt, the answer is a splitter. Item A splits off to another belt, while all other items loop back.
    - __rito__ 3y ago
      Filter inserters are what came to mind when I saw the title.
    - htgb 3y ago
      > Item A splits off to another belt, while all other items loop back. This doesn't address the parent comment's concern: > IIRC splitters only accept a single filter, and so you'd need many of them at each junction I haven't played Factorio in years, but IIRC the splitter maintains state (direction for next item) per item type, so I guess it can be set up to filter as many types as you like? I remember you had to prime it for the desired item type, but I forgot the specifics of how it does the rest of the filtering "logic".
      - dragontamer 3y ago
        > I haven't played Factorio in years Oh geez, your comment reminds me of like 8 years ago. You've really been out of the loop haven't ya? Yeah, what you say used to be true, but that's not what I'm talking about. All splitters today can split items off. You can just click on a modern splitter and say "Left side Iron ore", and all iron-ore leaves the left side of the splitter, and all other items go out the right side. This operates at full speed, no glitches. > so I guess it can be set up to filter as many types as you like? So use a splitter per item, and then merge the belts back together later. If you have 5 items to sort, create 5 filters, and then run the belts to route them where those 5 items need to go. For "Meta" builds, the key requirement isn't size. Its throughput. When you have 5 filters inserters, you barely will have ~10 items/second throughput (and that will glitch out depending on how successful your inserters are at picking up items, corners can pose issues for example) When you have 5 filter-splitters (on 5 different items), you easily prove that every decision point operates at the full 15/30/45 items/second (yellow/red/blue belts respectively).
        BlueTemplar 3y ago
        Who said anything about throughput ? Splitters can still only filter out a single item type, so if your goal is to do comparisons using a single entity (for clarity reasons for instance), they won't cut it. ---- Also, Factorio speedrunning has no metagame, since it's not a PvP game (well, aside from the less played PvP mode) : speedrunners don't have to adapt to changes in tactics of other speedrunners, they only have to learn new tricks that other speedrunners might discover, which is part of discovering the game itself.
  - deleted 3y ago
    [deleted]
- cheschire 3y ago
  They are assigning multiple items to each inserter. Splitter filters only filter one thing to one side, and everything else to the other side. That's not what is happening in this example though, where several things are going one way, and several things are going the other way.
- hellorashid 3y ago
  thanks! but yea as some people mentioned, i need to sort/filter multiple items, (ie the first node needs wood,coal,stone to go left and the metals to go right), and the splitters can only filter 1 item.
  - all2 3y ago
    You'd have to chain splitters. It would be ugly, but it would work.
dragontamer 3y ago
An inefficient design, but computer-science theory in Factorio means playing suboptimally necessarily. (Factorio wasn't designed to show off B-Trees, all the tools were designed to ya know... play Factorio) ------------ So I have to comments. #1 is about the Comp-Sci side, and #2 is about the optimization side. #3 combines both together for what I'd like to talk about. 1. Self-balancing trees (2-3 trees, Red-black Trees, and B-Trees) are about the self-balancing part. Not just the construction of a singular tree. You cannot recongfigure trees to rebuild themselves in Factorio, so the biggest feature is missing already. 2. From an optimization perspective: inserters are slower than belts. Even 4 inserters per belt only allows like 12-items per second, and blue-belts can push 45 items-per-second. You want to use splitters (which operate at full speed: 45 items per second) for the best belt-only design. (Bots obviously sort items fastest, but I am presuming this is some kind of belt-only challenge build). 3. The intersection of splitters + computer science is therefore: the Splitter (Factorio) and Benes Networks (creation of networks built off of only a 2-input to 2-output crossbar). If you really want to have a crazy good factory design, start studying this stuff: https://en.wikipedia.org/wiki/Clos_network https://en.wikipedia.org/wiki/Clos_network (A Benes network is simply a Clos network of size 2-input and 2-outputs. Clos networks are of any size: like 5-to-7 and other such odd numbers) -------- In Factorio, the meta you want to be searching for is "mixed belt" design, it seems.
- AaronM 3y ago
  Per the cheat sheet, 1.625 stack inserters can half fill a blue belt at their stack bonus of 7
  - Dylan16807 3y ago
    That's pulling out of a chest, where they can pick up the entire stack in a single tick. Pulling off a belt will be a notable slowdown, and picking items off of a wildly mixed belt will be a huge slowdown.
- hellorashid 3y ago
  thanks for the notes! def want to see if I can implement self-balancing next - was thinking the bots would come in handy here? not sure if its possible to have them dynamically build blueprints
eatonphil 3y ago
Awesome to see this. > i've been reading Database Internals with a book club, and this week was chapter 2, about B-Trees. For the crowd: signups are closed. But if you want: grab a copy of Database Internals and follow along "read-only" with the schedule and notes here: https://eatonphil.com/2023-database-internals.html https://eatonphil.com/2023-database-internals.html.
skitter 3y ago
> BSTs however are not good for disk based storage. The listed reasons also apply to in-memory storage – searching a btree node is faster than doing the equivalent amount of pointer traversals for a binary tree. Of course this comes at the cost of increased implementation complexity, but unless you're using C, you're probably not implementing your own tree-based map. You can then use different variants such as packing more entries into interior nodes by only storing values in the leafs (assuming you're making a map and not just a set, that is). If you then link neighboring nodes, you basically have a skip list.
- eatonphil 3y ago
  For further reading on this, see for example: [0] https://abseil.io/blog/20190812-btree https://abseil.io/blog/20190812-btree [1] https://opensource.googleblog.com/2013/01/c-containers-that-save-memory-and-time.html https://opensource.googleblog.com/2013/01/c-containers-that-...
jon-wood 3y ago
Why did someone have to go and post Factorio content here? Now I’ve got the urge to sink another hundred hours or so into it when there are already way too many good games to play this year.
- Cpoll 3y ago
  A big rebalance + Space Age expansion is slated for late next year, so you may wish to wait for that.
jakey_bakey 3y ago
This is really cool, but one budding writer to another; it's very distracting that capital letters aren't used at the start of sentences.
charlieyu1 3y ago
How good is Factorio? Everyone says many good things about it, but I’m worried if the game would be too repetitive, and the theme of building factories sounds a bit dull
- JWLong 3y ago
  The people I know that have played it, have all dumped 1,000+ hours into it.
- merdaverse 3y ago
  I was very skeptic before I tried it, I had the same concerns as you. And before I realized, I had dumped 100+ hours into it.
kunalgupta 3y ago
lol nice

B-trees in Factorio

330 points by hellorashid 3y ago

ivanjermakov 3y ago

I thought author will implement it with Factorio's circuitry..

pram 3y ago

You could do this all with splitters, don’t need the boxes and filter inserters. Nice explanation!

deathanatos 3y ago
How? They're not just trying to split an output into multiple lanes. The boxes represent the item stored in that "node" of the B-Tree (laid out here in 2D). I haven't had time to watch the video, but the prose & screenshots indicates there is associated logic on the inserters to maintain the "sorted" nature of the tree, by sending stuff down the appropriate path to child nodes. Given the OP's choice of values for keys … you could use splitters to do the splitting, but IIRC splitters only accept a single filter, and so you'd need many of them at each junction (as many as items at that junction). Filter-serters permit several filters, which is a bit nicer here. (You can see that in first screenshot.) (Unless you just forgo the entire B-Tree design and just n-splitters to sort into n boxes … but that's boring and I think isn't what the OP is going for.)
- dragontamer 3y ago
  The fastest "filter inserter" in modern Factorio meta is the splitter, which operates at full speed of the belt. There's almost no reason to use inserters for belt-to-belt transfers for modern meta, aside from a few speed-running stats where you use red-inserters while skipping logistics2 or something. But if you're trying to sort items on a belt by placing them onto another belt, the answer is a splitter. Item A splits off to another belt, while all other items loop back.
  - __rito__ 3y ago
    Filter inserters are what came to mind when I saw the title.
  - htgb 3y ago
    > Item A splits off to another belt, while all other items loop back. This doesn't address the parent comment's concern: > IIRC splitters only accept a single filter, and so you'd need many of them at each junction I haven't played Factorio in years, but IIRC the splitter maintains state (direction for next item) per item type, so I guess it can be set up to filter as many types as you like? I remember you had to prime it for the desired item type, but I forgot the specifics of how it does the rest of the filtering "logic".
    - dragontamer 3y ago
      > I haven't played Factorio in years Oh geez, your comment reminds me of like 8 years ago. You've really been out of the loop haven't ya? Yeah, what you say used to be true, but that's not what I'm talking about. All splitters today can split items off. You can just click on a modern splitter and say "Left side Iron ore", and all iron-ore leaves the left side of the splitter, and all other items go out the right side. This operates at full speed, no glitches. > so I guess it can be set up to filter as many types as you like? So use a splitter per item, and then merge the belts back together later. If you have 5 items to sort, create 5 filters, and then run the belts to route them where those 5 items need to go. For "Meta" builds, the key requirement isn't size. Its throughput. When you have 5 filters inserters, you barely will have ~10 items/second throughput (and that will glitch out depending on how successful your inserters are at picking up items, corners can pose issues for example) When you have 5 filter-splitters (on 5 different items), you easily prove that every decision point operates at the full 15/30/45 items/second (yellow/red/blue belts respectively).
      - BlueTemplar 3y ago
        Who said anything about throughput ? Splitters can still only filter out a single item type, so if your goal is to do comparisons using a single entity (for clarity reasons for instance), they won't cut it. ---- Also, Factorio speedrunning has no metagame, since it's not a PvP game (well, aside from the less played PvP mode) : speedrunners don't have to adapt to changes in tactics of other speedrunners, they only have to learn new tricks that other speedrunners might discover, which is part of discovering the game itself.
- deleted 3y ago
  [deleted]
cheschire 3y ago
They are assigning multiple items to each inserter. Splitter filters only filter one thing to one side, and everything else to the other side. That's not what is happening in this example though, where several things are going one way, and several things are going the other way.
hellorashid 3y ago
thanks! but yea as some people mentioned, i need to sort/filter multiple items, (ie the first node needs wood,coal,stone to go left and the metals to go right), and the splitters can only filter 1 item.
- all2 3y ago
  You'd have to chain splitters. It would be ugly, but it would work.

dragontamer 3y ago

An inefficient design, but computer-science theory in Factorio means playing suboptimally necessarily. (Factorio wasn't designed to show off B-Trees, all the tools were designed to ya know... play Factorio) ------------ So I have to comments. #1 is about the Comp-Sci side, and #2 is about the optimization side. #3 combines both together for what I'd like to talk about. 1. Self-balancing trees (2-3 trees, Red-black Trees, and B-Trees) are about the self-balancing part. Not just the construction of a singular tree. You cannot recongfigure trees to rebuild themselves in Factorio, so the biggest feature is missing already. 2. From an optimization perspective: inserters are slower than belts. Even 4 inserters per belt only allows like 12-items per second, and blue-belts can push 45 items-per-second. You want to use splitters (which operate at full speed: 45 items per second) for the best belt-only design. (Bots obviously sort items fastest, but I am presuming this is some kind of belt-only challenge build). 3. The intersection of splitters + computer science is therefore: the Splitter (Factorio) and Benes Networks (creation of networks built off of only a 2-input to 2-output crossbar). If you really want to have a crazy good factory design, start studying this stuff: https://en.wikipedia.org/wiki/Clos_network https://en.wikipedia.org/wiki/Clos_network (A Benes network is simply a Clos network of size 2-input and 2-outputs. Clos networks are of any size: like 5-to-7 and other such odd numbers) -------- In Factorio, the meta you want to be searching for is "mixed belt" design, it seems.

AaronM 3y ago
Per the cheat sheet, 1.625 stack inserters can half fill a blue belt at their stack bonus of 7
- Dylan16807 3y ago
  That's pulling out of a chest, where they can pick up the entire stack in a single tick. Pulling off a belt will be a notable slowdown, and picking items off of a wildly mixed belt will be a huge slowdown.
hellorashid 3y ago
thanks for the notes! def want to see if I can implement self-balancing next - was thinking the bots would come in handy here? not sure if its possible to have them dynamically build blueprints

eatonphil 3y ago

Awesome to see this. > i've been reading Database Internals with a book club, and this week was chapter 2, about B-Trees. For the crowd: signups are closed. But if you want: grab a copy of Database Internals and follow along "read-only" with the schedule and notes here: https://eatonphil.com/2023-database-internals.html https://eatonphil.com/2023-database-internals.html.

skitter 3y ago

> BSTs however are not good for disk based storage. The listed reasons also apply to in-memory storage – searching a btree node is faster than doing the equivalent amount of pointer traversals for a binary tree. Of course this comes at the cost of increased implementation complexity, but unless you're using C, you're probably not implementing your own tree-based map. You can then use different variants such as packing more entries into interior nodes by only storing values in the leafs (assuming you're making a map and not just a set, that is). If you then link neighboring nodes, you basically have a skip list.

eatonphil 3y ago
For further reading on this, see for example: [0] https://abseil.io/blog/20190812-btree https://abseil.io/blog/20190812-btree [1] https://opensource.googleblog.com/2013/01/c-containers-that-save-memory-and-time.html https://opensource.googleblog.com/2013/01/c-containers-that-...

jon-wood 3y ago

Why did someone have to go and post Factorio content here? Now I’ve got the urge to sink another hundred hours or so into it when there are already way too many good games to play this year.

Cpoll 3y ago
A big rebalance + Space Age expansion is slated for late next year, so you may wish to wait for that.

jakey_bakey 3y ago

This is really cool, but one budding writer to another; it's very distracting that capital letters aren't used at the start of sentences.

charlieyu1 3y ago

How good is Factorio? Everyone says many good things about it, but I’m worried if the game would be too repetitive, and the theme of building factories sounds a bit dull

JWLong 3y ago
The people I know that have played it, have all dumped 1,000+ hours into it.
merdaverse 3y ago
I was very skeptic before I tried it, I had the same concerns as you. And before I realized, I had dumped 100+ hours into it.

kunalgupta 3y ago

lol nice