[HN Gopher] B-trees in Factorio
___________________________________________________________________
B-trees in Factorio
Author : hellorashid
Score : 319 points
Date : 2023-11-15 17:25 UTC (2 days 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.
| dragontamer wrote:
| There's no "metagame" in Factorio because its not a PvP
| game.
|
| The "metagame" in Magic the Gathering or Starcraft
| revolves around the game before the game is played. For
| example, if I see that my opponent in Starcraft is a
| Terrain player (and I'm a Zerg player), I can study their
| games and see that they prefer to open 8-rax 3 marines
| very early harassments.
|
| I then decide to practice 9-pool / 6-ling and make sure
| I'm good at that before the game even starts, so that I'm
| well practiced against what they like to do. That's the
| "metagame", decisions you make before the game even
| starts.
|
| Or in MTG, its knowing how good Rakdos decks are (or
| whatever is popular today) and finding counter-cards. You
| play the game before you even start the game, because you
| have to prepare your deck.
|
| --------------
|
| So there's no real "metagame" in Factorio. There is a
| "meta" however. (IE: what most players tend to do).
| leetbulb wrote:
| The game being PvP is not relevant. PvP games have a
| goal, beat the other player(s) or team(s). Factorio has a
| goal, launch as many rockets as you can. Not to mention,
| within the community or your own imagination there are an
| infinite amount of niche game styles encompassing goals
| of their own. For example: speed runs, smallest
| footprint, highest efficiency, most advanced automation,
| most chaotic pipes, CPU design, actual PvP mode (yes it
| does have PvP, but in the spirit of my argument I'll
| ignore this)...the list goes on and on, and permutations
| of all of the above.
|
| Regardless of the goal you choose, you're competing,
| expanding knowledge, and defining standards with yourself
| and/or the community in some way, be it by playing co-op
| mode or sharing your results / optimizations /
| innovations on forums. Similar to PvP games, reaching
| that goal requires extremely nuanced strategic planning
| and making tactical decisions, even before starting the
| game, drawing from personal and/or community experience,
| understanding and adapting to game patches that may
| affect strategies, etc.
|
| Regarding "meta" vs "metagame," I still assert the former
| is simply shorthand for the latter.
| Qwertious wrote:
| I'm gonna disagree with you - accepting your definitions,
| Factorio has both a meta _and_ a metagame. Because _co-
| op_ can have a metagame, except instead of needing to
| know what your opponent will do in order to best hinder
| them, you need to know what your _friend_ will do in
| order to best _help_ them.
|
| Point in case: try joining a deathworld server (with
| experienced players), and then spamming burner miners.
| Once you're immediately kicked, please ponder your
| statement that "there's no real 'metagame'".
| BlueTemplar wrote:
| That's still game, not metagame : burner miners are bad
| because polluting, that's just game knowledge, you would
| have trouble if you tried to do that yourself in your own
| Death World game.
|
| But great point, co-op might require modifying your
| tactics to better work with teammates - in case of
| Factorio I know that you have to be WAY more careful to
| not make spaghetti in MP, which might also depend on the
| familiarity between the players - so I would say that you
| can potentially have a metagame as soon as you have MP,
| even without PvP.
|
| But now that I think of it, you can potentially have a
| metagame even when playing against AI. It's just that it
| needs to be advanced enough to be able to play
| rock/paper/scissors and remember previous games against
| you. AFAIK these games exist, but because it's much less
| effort and better reward to support basic AI + MP, they
| tend to be vanishingly rare, especially for more complex
| games.
| 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.
| itishappy wrote:
| https://mods.factorio.com/mod/recursive-blueprints
| hellorashid wrote:
| omg tysm!!
| 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
| willis936 wrote:
| I remember this guy on Comedy Central growing up. I never
| knew he died in 2005. Sucks.
| h2odragon wrote:
| I missed his entire career. head down working no time for
| TV, people said "you should check this guy out" and a few
| years later he wasnt there no more.
| 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
| munchbunny wrote:
| Factorio's "circuits" mechanic could implement neural
| networks pretty directly since the components can do 32-bit
| logic and arithmetic (integer only). It'd be pretty
| straightforward to implement a multi-layered neural network
| with a ReLU activation function.
| araes wrote:
| Agree. Just based on the previous comments, it sounded like
| the goals was a "belt only" type of design. Figured there
| might be interesting functionality with variable belt
| object density arriving at a location being a determinant.
| jon_richards wrote:
| > In Factorio, the meta you want to be searching for is "mixed
| belt" design, it seems.
|
| A more specific case is the "sushi belt" where one belt
| balances multiple ingredients while looping around on itself.
|
| Sometimes they just accept new items in a fixed ratio,
| sometimes they can actually rebalance if disturbed. This is my
| favorite https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
|
| While that one uses the in-game circuitry logic, the Factorio
| forum has a "circuit-free" section
| https://forums.factorio.com/viewforum.php?f=202
|
| And my favorite fun fact: The "fish" object in Factorio is a
| useless joke item, but because it isn't used by anything, it's
| sometimes used as a null value, a flag for when a belt has
| completed a full loop, or a debugging tool.
| https://forums.factorio.com/viewtopic.php?p=544302#p544302
| rollcat wrote:
| If you'd like to see sushi belts pushed to absurd levels,
| check out DoshDoshington:
|
| https://www.youtube.com/watch?v=6bRi1ykIeHg
| demondemidi wrote:
| "but somehow I feel that's really far away ... its been two
| hours and we're just getting furnaces up"
|
| ...
|
| "yeah ... its'a 30 lane wide sushi bus ... that's almost
| 900 underground belts in one blueprint..."
|
| LOL! That guy's delivery is hilarious. And his patience is
| astonishing.
| hackcasual wrote:
| He's completed both Space Exploration and Seablock, both
| of which are 300+ hour runs. Kind of shocking really how
| much time you can spend on Factorio overhauls
| ketzo wrote:
| Oh man, I just watched this whole video and I am in awe of
| this guy.
| Baeocystin wrote:
| You should check out his Circuit Abominations Factorio
| video. It's amazing.
|
| https://www.youtube.com/watch?v=etxV4pqVRm8
| wolletd wrote:
| Also DocJade: https://www.youtube.com/watch?v=6Kvi4JPUsak
| boredtofears wrote:
| This is awesome thanks for sharing. I'm about 20 hours into
| my first free play run through and just got to end game
| science and have been progressively trying different belt
| patterns. The early half of my base looks completely
| different than my later half.
| Qwertious wrote:
| >And my favorite fun fact: The "fish" object in Factorio is a
| useless joke item, but because it isn't used by anything,
| it's sometimes used as a null value, a flag for when a belt
| has completed a full loop, or a debugging tool.
| https://forums.factorio.com/viewtopic.php?p=544302#p544302
|
| 1. Fish is a crafting item for spidertron, it's not
| completely useless. 2. In multiplayer, the standard null-
| value item is the deconstruction planner (which is a big red
| square). I guess some people might use fish, but I've never
| seen it. It helps that deconstruction planners are free,
| nowadays, if you click the red button at the bottom-screen
| UI. 3. Fish is _incredibly_ useful for fighting in early-game
| - if a nest won 't stop bugging you, just go to the nearest
| pond, grab a few dozen fish, and you're basically invincible
| for a few minutes as long as you spam fish whenever you reach
| low health. Make sure to bring extra pistol ammo though,
| otherwise killing the nests will take _ages_ (you can melee
| them to death but it deals even less damage than pistols).
| dragontamer wrote:
| Shotgun is usually my first move out.
|
| Shotgun means you can kill nests very quickly. It's
| terrible at killing biters though, but machine gun kills
| early biters while shotguns clear nests.
| jon_richards wrote:
| Ah. I was playing before the 1.0.0 spidertron and the
| 0.15.0 patch where fish healing apparently got 20x as
| effective!
| cedws wrote:
| I've been dreaming of coming up a kind of 'ultimate' design by
| generating an expandable factory blueprint based on a set of
| guaranteed resource inputs, ensuring 100% utilisation of every
| machine and making output (rockets) at a predictable rate. Such
| a design would be complicated by speed/productivity upgrades
| that you get as you progress.
| hospitalJail wrote:
| This is why I don't play factorio. That brainpower can be used
| towards humanity and you get sick social media likes when you
| show off your results.
|
| Video games that ask me to provide brainpower in return for
| numbers on a screen are bottom of my list. I want to learn
| something new.
|
| Sure there might be puzzle aspects, and yes we decide that it
| is fun... but can't you also decide your studies are fun too?
| 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-...
| ivanjermakov wrote:
| I thought author will implement it with Factorio's circuitry..
| jon-wood wrote:
| 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 wrote:
| A big rebalance + Space Age expansion is slated for late next
| year, so you may wish to wait for that.
| jakey_bakey wrote:
| 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 wrote:
| 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 wrote:
| The people I know that have played it, have all dumped 1,000+
| hours into it.
| merdaverse wrote:
| 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.
___________________________________________________________________
(page generated 2023-11-17 23:02 UTC)