B-trees in Factorio
razberry.substack.com
razberry.substack.com
------------
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.
Pulling off a belt will be a notable slowdown, and picking items off of a wildly mixed belt will be a huge slowdown.
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.
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.
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"!
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.
First I'd use it to implement an email reader, and then ... more Factorio mods!
Then Terraform integration.
i got bored / sane after the first 10k SPM base, ~1,200hr. then i got into making "me" mods.
I used to play Factorio.
I still do, but I used to, too.
If you go that route, let me know when your emacs implementation is complete. I'll replace my OS with Factorio.
[1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
[2] https://wiki.factorio.com/Belt_transport_system#Splitters
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
...
"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.
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).
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.
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?
> 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.
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.
[0] https://abseil.io/blog/20190812-btree
[1] https://opensource.googleblog.com/2013/01/c-containers-that-...
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.)
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.
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".
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).
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.
"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.
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).
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.
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'".
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.
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.
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.