[HN Gopher] B-trees in Factorio
___________________________________________________________________
B-trees in Factorio
Author : hellorashid
Score : 157 points
Date : 2023-11-15 17:25 UTC (5 hours ago)
(HTM) web link (razberry.substack.com)
(TXT) w3m dump (razberry.substack.com)
| pram wrote:
| You could do this all with splitters, don't need the boxes and
| filter inserters. Nice explanation!
| deathanatos wrote:
| 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 wrote:
| 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__ wrote:
| Filter inserters are what came to mind when I saw the
| title.
| htgb wrote:
| > 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 wrote:
| > 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 wrote:
| 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.
| dragontamer wrote:
| Meta doesn't mean metagame.
|
| "The Meta" is how most other people play. The "standard"
| set of designs that experienced players have all
| discovered (and rediscovered) as you play the game. Ya
| know, 3-wire assembly machines feed into 2-green circuits
| kinda things.
|
| There's patterns of play between players. We all got our
| own style, but some designs are universally deployed
| across all experienced players, because those designs are
| just so good.
| leetbulb wrote:
| You've just described what "metagame" is; "meta" means
| metagame.
| Dylan16807 wrote:
| It's more complicated when you have many types of item
| and not many of each item, because a filter inserter can
| do five types and a splitter can do one.
|
| And if you add some wires, you can have each inserter
| automatically grab whatever is directly in front of it
| that isn't on a blacklist. At that point a max-throughput
| build with inserters is a big but roughly fixed size,
| while a build for splitters is proportional to the number
| of items.
| cheschire wrote:
| 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 wrote:
| 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 wrote:
| You'd have to chain splitters. It would be ugly, but it would
| work.
| dragontamer wrote:
| 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 (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 wrote:
| Per the cheat sheet, 1.625 stack inserters can half fill a blue
| belt at their stack bonus of 7
| Dylan16807 wrote:
| 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 wrote:
| 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
| dragontamer wrote:
| The main issue with bots is that they "cheat" what you're
| trying to do and just instantly solve the problem.
|
| You can click on your logistic auto-fetch feature and just
| have robots search all the boxes for the items you want, and
| they'll automatically refill your inventory to 300-belts.
|
| And then when you build a belt somewhere, you can either
| choose from your inventory, or shift-click and/or blueprint
| build to have robots search for those items in your entire
| logistic network and they just fly out, find the item, come
| back, and place it for you. Just in like 2 or 3 clicks (or
| less).
|
| So for a lot of these challenges and demonstrations, Factorio
| players aim for "belts only" or other such constraints, to
| try and force ourselves into design constraints. Belts-only
| also uses zero-power (bots need power to function, and its
| rather substantial in practice). So there's power-benefits to
| going belt-only.
|
| -----------------------
|
| So what is your goal here? If its to build a tree in
| Factorio, I think we can say you succeeded.
|
| But its not the optimal play or the "meta" factory design,
| lol. But I recognize that's not quite what you were going
| for. (Ex: the meta would be to just use bots in a bot-
| factory. Or keep items sorted in a belt factory, no reason to
| mix belts)
|
| I think pushing players to think deeply about the "meta",
| including the deep thoughts upon how CLOS Networks apply to
| high-quality Belts/and/splitter designs, is very rewarding.
| Its not about trees though.
|
| -----------
|
| Mixed-belts are fun though. And I think I spent many good
| hours and weeks thinking about them back in my Factorio days.
| Lots of interesting problems to solve, but I think my problem
| was that these solutions weren't meta, nor did they
| demonstrate any beautiful mathematical concept.
|
| Benes Networks / CLOS networks applied to belts however, were
| a perfect match. The best builds were those that matched the
| deep mathematical/comp. sci foundation of Benes Networks. So
| it was the "more fun" part of Factorio to me. Not only was I
| learning some deep Comp. Sci topic, but when I improved my
| designs based on CLOS Networks, they instantly led to
| improved belt-balance and throughput in my factory designs.
| daedrdev wrote:
| And a good reason to be pick about bots is in the endgame
| the limit is ones hardware, and bots are really
| computationally demanding compared to other transportation
| poink wrote:
| > not sure if its possible to have them dynamically build
| blueprints
|
| Not in the base game, but there's a mod for it. Nilaus
| recently did a short series of videos on YouTube where he
| used it to make an auto-expanding factory, so you should be
| able to find the mod name there if you want to mess with it.
| mathgradthrow wrote:
| if you treat splitters as moving the computation backward on
| the belt, I'm pretty sure they're universal, so the
| intersection of splitters and computer science is computer
| science
| DonHopkins wrote:
| Is there a Factorio extension like "Scriptorio" that lets you
| put JSON on conveyor belts? With JavaScript or Lua function
| factories.
|
| Then you could pass the b-trees themselves around with conveyor
| belts and inserters, as well as the objects to insert and
| search.
|
| And write a recursive search function with a loop of conveyor
| belts running through factories, that just loops the tree
| around peeling off a level at a time until it hits the leaf,
| breaking the loop and outputting the result.
|
| It's an interesting execution model, not standard JavaScript,
| more data flow. Should you allow "quantum tunneling" and
| "action at a distance" by allowing multiple references to the
| same underlying JSON objects from different conveyor belts /
| inserters / factories? That could be useful, but Factorio
| itself traditionally treats each physical item having a unique
| identity, so maybe it would be more "realistic" not to support
| multiple references. Or you can only make multiple references
| once you research "Quantum Tunneling JSON" technology, with the
| "JSON Reference Entangler Factory"!
| h2odragon wrote:
| Factorio is _extremely mod friendly_
|
| If it doesn't exist you can probably wedge it in fairly
| easily.
|
| I suggest that it would be worth your time to give it a poke
| just to see what a thoroughly excellent example of software
| engineering they've made there.
| DonHopkins wrote:
| Oh I know, but normal Factorio is Programmer Crack, and
| going meta like that would be like Scarfacing Programmer
| Fentanyl for me!
|
| First I'd use it to implement an email reader, and then ...
| more Factorio mods!
|
| Then Terraform integration.
|
| https://en.wikipedia.org/wiki/Jamie_Zawinski#Zawinski's_Law
| h2odragon wrote:
| steam tells me my play time is 2,779.2 hr
|
| i got bored / sane after the first 10k SPM base,
| ~1,200hr. then i got into making "me" mods.
| DonHopkins wrote:
| I'm at 6,251.5 but I leave it running all night long.
|
| I used to play Factorio.
|
| I still do, but I used to, too.
|
| https://www.youtube.com/watch?v=VqHA5CIL0fg
| all2 wrote:
| Would you accidentally a scheme? Would you could you in a
| train? Would you could you with a plane?
|
| If you go that route, let me know when your emacs
| implementation is complete. I'll replace my OS with
| Factorio.
| araes wrote:
| Superficially examining the Clos Network article, if Factorio
| is amenable to creating such networks, then it seems like it
| would be possible to create some of the simpler neural network
| designs, such as shown here: [1] Maybe having something like a
| weighting of the resource density arriving at a certain
| location to change the output? From the mechanics I can see
| here [2] it looks like Mergers / Un-Mergers and three belt
| speeds could probably do density weighted decision making.
|
| [1] https://www.asimovinstitute.org/wp-
| content/uploads/2019/04/N...
|
| [2] https://wiki.factorio.com/Belt_transport_system#Splitters
| eatonphil wrote:
| 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.
| skitter wrote:
| > 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 wrote:
| For further reading on this, see for example:
|
| [0] https://abseil.io/blog/20190812-btree
|
| [1] https://opensource.googleblog.com/2013/01/c-containers-
| that-...
___________________________________________________________________
(page generated 2023-11-15 23:00 UTC)