Otomat seluler adalah sistem yang terdiri dari sel dengan nilai numerik dalam kisi, serta aturan yang menentukan perilaku sel-sel ini. Berulang kali menerapkan aturan untuk setiap sel grid secara paralel dengan visualisasi grid, kita sering bisa mendapatkan efek dari organisme yang berkembang tertentu dengan perilaku yang kompleks dan rumit, bahkan jika aturannya relatif sederhana.
Automata seluler memiliki berbagai bentuk, tipe, dan dimensi. Mungkin otomat seluler paling terkenal adalah Conway's Game of Life (GOL). Ini terdiri dari grid dua dimensi di mana setiap sel berisi nilai biner (hidup atau mati). Aturan yang menyertainya, berdasarkan keadaan sel tetangga, menentukan apakah sel itu harus mati atau hidup. Aturan mengatakan bahwa sel hidup mati kesepian jika ada kurang dari 2 sel hidup di sekitarnya. Jika lebih dari tiga sel tetangga hidup, dia mati karena kelebihan populasi. Dengan kata lain, sel "bertahan" jika ada tepat 2 atau 3 sel tetangga di sekitarnya. Agar sel
mati dapat hidup, ia harus memiliki 3 sel tetangga yang hidup, jika tidak sel itu tetap mati. Contoh mesin GoL yang berulang melalui beberapa negara ditunjukkan di bawah ini.
Versi lain yang terkenal dari otomat seluler adalah satu dimensi; itu disebut Elementary Cellular Automaton (ECA). Inilah yang kami laksanakan dalam posting ini.
Setiap keadaan otomat ini disimpan sebagai array satu dimensi dari nilai Boolean, dan sementara dua dimensi diperlukan untuk memvisualisasikan keadaan GOL, satu otomat nilai cukup untuk otomat ini. Berkat ini, kita dapat menggunakan dua dimensi (bukan animasi) untuk memvisualisasikan seluruh sejarah keadaan otomat ini. Seperti dalam kasus GOL, keadaan sel dalam mesin ini adalah 0 atau 1, tetapi tidak seperti sel GOL, yang diperbarui tergantung pada 8 tetangganya, sel ECA diperbarui berdasarkan keadaan tetangga kiri, tetangga kanan, dan itu sendiri!
Contoh aturan ditunjukkan di bawah ini: tiga sel teratas adalah input dari aturan, dan yang bawah adalah output, di mana hitam adalah 1 dan putih adalah 0. Juga, kita bisa melihat pola yang dihasilkan oleh masing-masing, ketika keadaan awal semua 0 kecuali 1 di sel tengah.
Anda mungkin bertanya-tanya: mengapa aturan yang disajikan di atas ditunjukkan oleh angka? Karena setiap angka dalam rentang dari 0 hingga 255 secara langsung sesuai dengan aturan ECA, dan oleh karena itu angka-angka ini digunakan sebagai nama-nama aturan. Korespondensi ini ditunjukkan di bawah ini:
Dari angka ke aturanSetiap angka dalam kisaran dari 0 hingga 255 dapat direpresentasikan dalam bentuk biner hanya dengan 8 digit (panah pertama di atas). Selain itu, kami dapat memberikan masing-masing angka ini indeks berdasarkan lokasinya (panah kedua). Secara alami, indeks ini berada dalam kisaran 0 hingga 7, yaitu mereka dapat direpresentasikan dalam bentuk biner hanya dengan menggunakan 3 digit (panah ketiga). Menafsirkan 3 digit ini sebagai input, dan digit yang sesuai dari angka asli sebagai output, kita mendapatkan fungsi ternary yang kita butuhkan (panah keempat).
Generasi pemerintahan
Mari kita terapkan interpretasi di atas sebagai fungsi
get_rule yang menerima angka dari 0 hingga 255 sebagai input dan mengembalikan aturan ECA yang sesuai dengan angka itu.
Kita perlu membuat sesuatu seperti ini:
const rule30 = get_rule(30); const output110 = rule30(1, 1, 0);
Dalam contoh di atas, mulai
rule30(1,1,0) menggabungkan ketiga nilai biner menjadi satu angka (110 = 6) dan akan mengembalikan sedikit pada posisi itu (6) dalam representasi biner 30. Angka 30 dalam representasi biner adalah 00011110, oleh karena itu, fungsi akan mengembalikan 0 (kami menghitung di kanan dan mulai menghitung dari 0).
Mengetahui bahwa tiga variabel input biner akan digabungkan menjadi satu angka, mari kita mulai dengan mengimplementasikan fungsi
combine .
const combine = (b1, b2, b3) => (b1 << 2) + (b2 << 1) + (b3 << 0);
Setelah menggeser argumen ke posisi yang sesuai, lalu menjumlahkan tiga angka yang digeser, kita mendapatkan kombinasi yang diinginkan.
Bagian penting kedua dari fungsi
get_rule adalah menentukan nilai bit pada posisi tertentu dalam sebuah angka. Oleh karena itu, mari kita membuat fungsi
get_bit(num, pos) , yang dapat mengembalikan nilai bit pada posisi posisi tertentu pada angka tertentu. Misalnya, angka 141 dalam bentuk biner adalah 10001101, jadi
get_bit(2, 141) harus mengembalikan
1 , dan
get_bit(5, 141) harus mengembalikan
0 .
Fungsi
get_bit(num,pos) dapat diimplementasikan dengan terlebih dahulu melakukan sedikit pergeseran angka dengan
pos ke kanan, dan kemudian melakukan operasi bitwise "AND" dengan angka 1.
const get_bit = (num, pos) => (num >> pos) & 1;
Sekarang kita hanya perlu menggabungkan dua fungsi ini:
const get_rule = num => (b1, b2, b3) => get_bit(num, combine(b1, b2, b3));
Hebat! Jadi, kami memiliki fungsi yang untuk setiap angka dalam interval kami memberi kami aturan ECA unik yang dengannya kami dapat melakukan apa saja. Langkah selanjutnya adalah membuat mereka di browser.
Visualisasi Aturan
Untuk merender automata di browser, kita akan menggunakan elemen
canvas .
canvas dapat dibuat dan ditambahkan ke badan html sebagai berikut:
window.onload = function() { const canvas = document.createElement('canvas'); canvas.width = 800; canvas.height = 800; document.body.appendChild(canvas); };
Untuk dapat berinteraksi dengan
canvas , kita perlu
konteks . Konteks memungkinkan kita untuk menggambar bentuk dan garis, mewarnai objek, dan biasanya menavigasi
canvas . Ini diberikan kepada kami melalui metode
getContext dari
canvas kami.
const context = canvas.getContext('2d');
Parameter
'2d' mengacu pada jenis konteks yang akan kita gunakan dalam contoh ini.
Selanjutnya, kita akan membuat fungsi yang memiliki konteks, aturan ECA, serta beberapa informasi tentang skala dan jumlah sel, menggambar aturan di atas
canvas . Idenya adalah untuk menghasilkan dan menggambar garis grid demi baris; Bagian utama dari kode terlihat seperti ini:
function draw_rule(ctx, rule, scale, width, height) { let row = initial_row(width); for (let i = 0; i < height; i++) { draw_row(ctx, row, scale); row = next_row(row, rule); } }
Kita mulai dengan beberapa jenis set sel awal, yang merupakan baris saat ini. Baris ini, seperti pada contoh di atas, biasanya berisi semua nol, dengan pengecualian satu unit di sel tengah, tetapi juga bisa berisi baris acak sepenuhnya dari 1 dan 0. Kami menggambar baris sel ini, kemudian menggunakan aturan untuk menghitung baris berikutnya dari nilai berdasarkan garis saat ini. Kemudian kita cukup mengulang gambar dan menghitung langkah-langkah baru sampai kita menemukan bahwa kisi cukup tinggi.
Untuk cuplikan kode di atas, kita perlu mengimplementasikan tiga fungsi:
draw_row ,
draw_row dan
next_row .
initial_row adalah fungsi sederhana. Ini menciptakan array nol dan mengubah elemen di tengah array satu per satu.
function initial_row(length) { const initial_row = Array(length).fill(0); initial_row[Math.floor(length / 2)] = 1; return initial_row; }
Karena kita sudah memiliki fungsi aturan, fungsi
next_row dapat terdiri dari satu baris. Nilai setiap sel dalam baris baru adalah hasil dari penerapan aturan dengan nilai sel terdekat, dan baris lama digunakan sebagai input.
const next_row = (row, rule) => row.map((_, i) => rule(row[i - 1], row[i], row[i + 1]));
Apakah Anda memperhatikan bahwa kami curang pada baris ini? Setiap sel di baris baru membutuhkan input dari tiga sel lain, tetapi dua sel di tepi baris hanya menerima data dari dua sel. Sebagai contoh,
next_row[0] mencoba untuk mendapatkan nilai
next_row[0] dari
row[-1] . Ini masih berfungsi, karena ketika mencoba mengakses nilai dengan indeks yang tidak ada dalam array, javascript mengembalikan
undefined , dan kebetulan
(undefined >> [ ]) (dari fungsi
combine ) selalu mengembalikan 0. Ini berarti bahwa dalam kenyataannya kami memproses setiap nilai di luar array sebagai 0.
Saya tahu ini jelek, tapi segera kami akan membuat sesuatu yang indah di layar, sehingga kami bisa dimaafkan.
Berikutnya adalah fungsi
draw_row ; dialah yang melakukan rendering!
function draw_row(ctx, row, scale) { ctx.save(); row.forEach(cell => { ctx.fillStyle = cell === 1 ? '#000' : '#fff'; ctx.fillRect(0, 0, scale, scale); ctx.translate(scale, 0); }); ctx.restore(); ctx.translate(0, scale); }
Di sinilah kita sangat bergantung pada objek konteks, menggunakan setidaknya 5 metode berbeda dari itu. Berikut adalah daftar singkat dan cara menggunakannya.
fillStyle menunjukkan bagaimana kita ingin mengisi bentuk. Ini bisa berupa warna, misalnya, "#f55" , serta gradien atau pola. Kami menggunakan metode ini untuk memisahkan sel 0 dari sel 1 secara visual.fillRect(x, y, w, h) menggambar persegi panjang dari titik (x, y) dengan lebar w dan tinggi h, diisi sesuai dengan fillStyle . Persegi panjang kami adalah kotak sederhana, tetapi Anda mungkin terkejut bahwa titik awal dari semuanya adalah asal. Itu terjadi karena kami menggunakan metode ini dalam kombinasi dengan translate .translate(x, y) memungkinkan Anda untuk memindahkan seluruh sistem koordinat. Posisi disimpan, sehingga metode ini merupakan alternatif yang sangat baik untuk melacak berbagai posisi elemen. Misalnya, alih-alih menghitung posisi setiap sel kisi individu, kita bisa menggambar sel, bergerak ke kanan, menggambar sel baru, dan seterusnya.save() dan restore() digunakan bersamaan dengan translate dan metode konversi koordinat lainnya. Kami menggunakannya untuk menyimpan sistem koordinat saat ini pada titik tertentu, sehingga nanti kami dapat kembali ke sana (menggunakan pemulihan ). Dalam hal ini, kami menyimpan sistem koordinat sebelum merender baris dan memindahkannya ke kanan. Kemudian, ketika kami selesai menggambar garis dan pergi ke kanan, koordinat dikembalikan dan kami kembali ke keadaan semula. Lalu kami bergerak turun untuk bersiap-siap untuk menggambar garis berikutnya.
Sekarang kita memiliki semua bagian yang diperlukan untuk fungsi
draw_rule . Kami menggunakan fungsi ini di
window.onload setelah menyiapkan
canvas . Kami juga akan menentukan parameter yang kami butuhkan.
window.onload = function() { const width = 1000;
Kami mengekstraksi dimensi
canvas sebagai variabel terpisah bersama dengan jumlah sel secara horizontal. Kemudian kita menghitung
cell_scale dan 'cells_down' sehingga kisi-kisi mengisi seluruh
canvas , sementara sel tetap persegi. Berkat ini, kita dapat dengan mudah mengubah "resolusi" dari grid, yang tersisa di dalam
canvas .
Itu saja! Contoh kode lengkap ada di
github dan
codepen :
Pindah
Berkat sistem ini, kami akan dapat memeriksa satu demi satu semua 256 aturan, baik secara iteratif, mengubah kode, atau memilih nomor aturan secara acak pada setiap pemuatan halaman. Bagaimanapun, sangat menarik untuk mempelajari semua hasil yang tidak terduga ini di lingkungan kita yang terkendali.
Anda juga dapat membuat keadaan awal sel-sel automaton secara acak alih-alih “nol nol dan satu unit” statis. Jadi kami mendapatkan hasil yang lebih tidak terduga. Versi fungsi
initial_row ini dapat ditulis seperti ini:
function random_initial_row(width) { return Array.from(Array(width), _ => Math.floor(Math.random() * 2)); }
Di bawah ini Anda melihat seberapa besar perubahan jalur output ini berdampak besar pada output.
String Sumber AcakDan ini hanyalah satu aspek yang bisa Anda ubah! Mengapa membatasi diri hanya dengan dua syarat? (Transisi dari 2 ke 3 negara meningkatkan jumlah aturan dari 256 ke 7 625 597 484 987!) Mengapa dibatasi pada kotak? Kenapa hanya 2 dimensi? Mengapa hanya satu aturan dalam satu waktu?
Contoh visualisasi berdasarkan ECA ditunjukkan di bawah, tetapi dengan fungsi
draw_rule alternatif yang
draw_rule garis tidak dengan kotak, tetapi dengan pola isometrik, dan kemudian mengisi area yang ditentukan oleh garis-garis ini dengan warna. Anda bahkan tidak perlu menampilkan garis pemisah dan hanya menampilkan warna.
Jika Anda melangkah lebih jauh, maka Anda dapat menambahkan simetri, baik aksial (baris tengah) dan cermin (baris bawah).
Jika visualisasi ini tampak menarik bagi Anda, tetapi pelajari
kotak pasir interaktif ini , atau bahkan lebih baik, mulailah dengan kode yang kami buat dan cobalah untuk membuat automata seluler Anda sendiri!
Semoga beruntung