B-tree di Factorio

Mempelajari B-tree

• Binary Search Tree (BST): setiap node memiliki kunci; node di kiri memiliki nilai kunci yang lebih rendah, dan node di kanan memiliki nilai kunci yang lebih tinggi.

• BST hanya berfungsi ketika kunci dapat diurutkan, dan jika nilai hanya ditambahkan ke satu sisi, keseimbangannya rusak sehingga efisiensinya menurun.

• BST yang tidak seimbang dapat diperbaiki melalui pivoting, tetapi tidak cocok untuk penyimpanan berbasis disk (karena perlu sering diseimbangkan ulang, dan node yang berdekatan bisa tersimpan di halaman yang berbeda).

• B-tree: terdiri dari node dengan lebih banyak kunci dan pointer dibanding pohon biner.

• Setiap node memiliki beberapa kunci, dan berdasarkan setiap kunci memiliki beberapa pointer (misalnya, node dengan kunci 17 dan 24 memiliki pointer ke node dengan kunci lebih kecil dari 17, node dengan kunci di antara 17 dan 24, dan node dengan kunci lebih besar dari 24).

Implementasi B-tree di Factorio

• Implementasi binary search tree sederhana di Factorio (game pembangunan pabrik): setiap node terdiri dari peti kayu (kunci) dan dua jalur (pointer).
• Karena tidak ada cara untuk membandingkan nilai material, urutan arbitrer diberikan dan dibandingkan menggunakan lengan filter.
• Implementasi B-tree lebih kompleks: setiap node memiliki tiga kunci dan empat pointer ke node anak.
• B-tree dapat menyimpan lebih banyak informasi, dan alih-alih menyortir item secara manual, pohonnya dibiarkan kosong sampai ditemukan cara representasi yang lebih baik nanti.

Opini GN⁺

• Hal terpenting dari tulisan ini adalah memahami konsep B-tree dan pendekatan kreatif untuk mengimplementasikannya di dalam game Factorio.
• Yang menarik bagi pembaca adalah bahwa ini memberi kesempatan untuk memahami struktur data ilmu komputer yang kompleks secara visual dan intuitif melalui game.
• Pendekatan seperti ini membuat pembelajaran lebih menyenangkan dan menarik, serta menawarkan cara baru untuk mengeksplorasi konsep dasar rekayasa perangkat lunak melalui media nontradisional seperti game.

[GN⁺]

Komentar Hacker News

• Desain game Factorio tidak sepenuhnya mencerminkan teori ilmu komputer, dan berfokus pada menikmati permainan daripada permainan yang dioptimalkan secara teoretis.
• Di Factorio, pohon biner self-balancing (pohon 2-3, pohon merah-hitam, pohon B) tidak dapat direkonstruksi, sehingga fitur terpentingnya, yaitu penyeimbangan mandiri, hilang.
• Dari sudut pandang optimisasi, inserter di Factorio lebih lambat daripada belt; empat inserter hanya dapat menangani 12 item per detik per belt, sedangkan blue belt dapat menangani 45 item per detik, jadi penggunaan splitter direkomendasikan untuk desain optimal yang hanya mengandalkan belt.
• Penggabungan ilmu komputer dan splitter mencakup konsep jaringan Benes (jaringan yang hanya terdiri dari crossbar 2-input 2-output), dan untuk desain pabrik yang efisien, hal ini perlu dipelajari.
• Desain mixed belt penting di Factorio, dan membaca buku tentang struktur internal database bisa membantu.
• Pohon pencarian biner (BST) tidak cocok untuk penyimpanan berbasis disk, dan pencarian node pohon B lebih cepat daripada traversal pointer pohon biner. Kompleksitas implementasinya memang meningkat, tetapi kecuali Anda memakai bahasa C, jarang ada kebutuhan untuk mengimplementasikan map berbasis pohon sendiri.
• Ditunjukkan bahwa ketiadaan huruf kapital dapat mengganggu keterbacaan tulisan.
• Konten terkait Factorio yang dibagikan memicu keinginan untuk kembali menghabiskan ratusan jam di game itu.
• Semua pekerjaan dapat dilakukan hanya dengan splitter, dan peti serta filter inserter tidak diperlukan.
• Disebutkan bahwa semula dikira ini akan diimplementasikan menggunakan circuit di Factorio, tetapi ternyata tidak.