pengantar
The Algoritma Boids adalah demonstrasi yang relatif sederhana dari perilaku muncul dalam kelompok. Ia memiliki tiga aturan utama, seperti yang dijelaskan oleh penciptanya, Craig Reynolds:
Model berkelompok dasar terdiri dari tiga perilaku kemudi sederhana yang menggambarkan bagaimana seorang individu dapat melakukan manuver berdasarkan posisi dan kecepatan teman-teman sekawanan terdekatnya:
- Pemisahan : mengarahkan untuk menghindari berkerumunnya kawanan domba setempat.
- Alignment : mengarahkan ke arah rata-rata teman kawanan lokal.
- Kohesi : mengarahkan untuk bergerak menuju posisi rata-rata teman sekawanan lokal.
Setiap boid memiliki akses langsung ke deskripsi geometris seluruh adegan, tetapi berbondong-bondong mengharuskan hanya bereaksi terhadap teman flock dalam lingkungan kecil tertentu di sekitarnya. Lingkungan dicirikan oleh jarak (diukur dari pusat boid) dan sudut , diukur dari arah terbang boid. Teman kawanan di luar lingkungan lokal ini diabaikan. Lingkungan tersebut dapat dianggap sebagai model persepsi terbatas (seperti oleh ikan di air keruh) tetapi mungkin lebih tepat untuk menganggapnya sebagai mendefinisikan wilayah di mana teman sekawanan domba mempengaruhi kemudi pengendara.
Saya tidak sempurna saat menjelaskan sesuatu, jadi saya sangat merekomendasikan untuk memeriksa sumbernya . Dia juga memiliki beberapa gambar super informatif di situsnya.
Tantangan
Mengingat jumlah boids (entitas yang disimulasikan) dan jumlah frame, output animasi dari simulasi.
- Boids harus dirender sebagai lingkaran merah, dengan garis di dalam lingkaran menunjukkan headingnya, yang merupakan arah boid menunjuk:
- Sudut setiap boid (seperti yang dijelaskan oleh Reynolds) harus 300 derajat penuh. (bukan 360)
- Judul awal dan posisi setiap boid harus acak secara acak (tetapi diunggulkan, sehingga outputnya masih ditentukan), serta posisinya.
- Jika radius boid adalah 1, maka radius lingkungan harus 3.
- Jumlah boid akan berkisar antara 2-20.
- Jumlah bingkai akan berkisar 1-5000
- Animasi harus dimainkan dengan minimum 10 milidetik per bingkai dan maksimum 1 detik kali jumlah boid. (2 boids = 2 detik per frame max, 3 boids = 3 detik per frame max, dan sebagainya)
- Animasi output harus minimal 5 boid-radius dengan 5 boid-jari-jari, kali setengah jumlah boid. Jadi, ukuran minimum untuk 2 boid adalah 10 boid-radius dengan 10 boid-radius, minimum untuk 3 boid adalah 15 boid-radius dengan 15 boid-radius, dan lain-lain.
- Jari-jari setiap boid harus minimal 5 piksel dan maksimal 50 piksel.
- Kecepatan setiap boid perlu dibatasi sehingga tidak bergerak lebih dari 1/5 dari jari-jarinya dalam satu frame.
- Output perlu ditentukan, sehingga input yang sama akan menghasilkan output yang sama jika dijalankan beberapa kali.
- Jika boid mencapai perbatasan, itu harus membungkus kembali ke sisi lain. Demikian juga, lingkungan di sekitar setiap boid juga harus membungkus perbatasan.
Aturan untuk algoritme
Dalam hal ini, setiap boid memiliki sektor di sekitarnya yang mencakup 300 derajat, berpusat pada heading boid. Setiap boids lain di "lingkungan" ini dianggap "tetangga", atau (untuk menggunakan istilah Reynolds) "teman sekawanan".
Setiap boid harus menyesuaikan headingnya untuk menghindari tabrakan dan menjaga jarak nyaman satu radius boid dengan tetangganya. (Ini adalah aspek "Pemisahan" dari algoritma. Yang satu jari-jari dapat dilewati, tetapi harus seperti karet gelang, terpasang kembali ke tempatnya.)
Setiap boid juga harus menyesuaikan headingnya agar lebih dekat dengan heading rata-rata boid lain di lingkungannya, selama itu tidak mengganggu aturan pertama. (Ini adalah aspek "Alignment" dari algoritma)
Setiap boid harus berbelok ke posisi rata-rata teman kawanannya, selama ini tidak menyebabkan tabrakan atau secara signifikan mengganggu aturan kedua.
Dalam makalahnya tentang subjek , ia menjelaskan ini sebagai berikut:
Untuk membuat kawanan yang disimulasikan, kita mulai dengan model boid yang mendukung penerbangan geometris. Kami menambahkan perilaku yang sesuai dengan kekuatan lawan dari penghindaran tabrakan dan keinginan untuk bergabung dengan kawanan. Dinyatakan secara singkat sebagai aturan, dan dalam urutan menurun diutamakan, perilaku yang mengarah ke simulasi berkelompok adalah:
- Penghindaran Tabrakan: hindari tabrakan dengan teman sekawanan terdekat
- Pencocokan Kecepatan: upaya untuk mencocokkan kecepatan dengan teman kawanan terdekat
- Flock Centering: berusaha untuk tetap dekat dengan teman flock terdekat
Deskripsi gerakan yang lebih terperinci:
- Implementasi standar dari Algoritma Boids biasanya melakukan perhitungan untuk setiap aturan, dan menggabungkannya bersama.
- Untuk aturan pertama, boid menelusuri daftar boid tetangga dalam lingkungannya, dan jika jarak antara dirinya dan tetangga kurang dari nilai tertentu, vektor yang mendorong boid menjauh dari tetangga diterapkan ke heading boid.
- Untuk aturan kedua, boid menghitung rata-rata heading tetangganya, dan menambahkan sebagian kecil (kita akan menggunakan 1/10 dalam tantangan ini) dari perbedaan antara heading saat ini dan rata-rata heading ke heading saat ini.
- Untuk aturan ketiga dan terakhir, boid rata-rata posisi tetangganya, menghitung vektor yang menunjuk ke lokasi ini. Vektor ini dikalikan dengan angka yang bahkan lebih kecil dari yang digunakan untuk aturan 2 (untuk tantangan ini, 1/50 akan digunakan) dan diterapkan ke pos.
- Boid kemudian dipindahkan ke arah posnya
Berikut ini adalah implementasi pseudocode yang bermanfaat dari Algoritma Boids.
Contoh Input dan Output
Memasukkan:Keluaran:5, 190 (5 boids, 190 frame)
Kriteria menang
Ini adalah kode-golf , jadi solusi terkecil dalam byte menang.
sumber
Jawaban:
Memproses 3.3.6 (Jawa) ,
932931940928957917904 byte-1 byte dari Jonathan Frech
+11 byte untuk lebih cocok dengan spec
-2 byte dari Kevin Cruijssen
-12 byte untuk mengubah args ke t ()
+29 byte karena saya melakukan ghosting yang salah, lihat versi komentar di bawah
-40 byte untuk menggunakan untuk loop alih-alih panggilan terpisah untuk setiap hantu
-13 byte untuk menggunakan frameRate default, 30
Yah, ini awal, bagi seseorang yang tidak menggunakan Java-golf. :)
Saya tidak tahu cara yang masuk akal untuk melakukan input dalam Pemrosesan, jadi dua variabel pertama adalah input (dan saya tidak menghitung nilainya (5 byte) terhadap jumlah byte). Jika ini masalah, saya bisa mencoba hal lain.
Saya juga tidak tahu cara yang baik untuk memungkinkan mencobanya secara online (proyek Processing.js tidak dapat menangani gaya kode ini) tanpa hosting sendiri; dan itu adalah sesuatu yang tidak ingin saya coba. Beri tahu saya jika ada hal pintar yang bisa saya lakukan.
Kode yang diformat, dengan komentar
Output sampel
n = 15, bingkai = 400:
Atau, animasi yang sama, tetapi menunjukkan lingkungan masing-masing boid.
sumber
2*PI
tidak menjadiTAU
untuk menyimpan byte?,i,
untuk,i=0,
dan kemudian menghapus bagiani=0
dalam for-loop. (-1 byte);frameCount%f==0
keframeCount%f<1
(1 byte);&&
untuk&
di final jika2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6
(-1 byte). Sekali lagi, tidak yakin apakah ini mungkin, tetapi karena Pemrosesan tampaknya cukup mirip dengan Java, saya pikir begitu. Anda juga dapat mencoba membuat gif dengan screentogif.com .JavaScript (ES6) + HTML5, 1200 byte
Inilah solusi saya saat ini menggunakan Canvas API. The
eval()
mengembalikan fungsi kari yang input pertama adalahBoid
populasi, dan kedua adalah jumlah frame animasi. Anda dapat menggunakanInfinity
untuk animasi berkelanjutan.Ini
eval(...)
adalah 1187 byte dan<canvas id=c>
13 byte, menghasilkan total 1200. CSS tidak perlu, tetapi untuk kenyamanan, ini memungkinkan Anda untuk melihat tepi kanvas.Edit
Seperti yang diminta, cuplikan lain dengan input untuk populasi Boid:
sumber
t.a+v+l/10+f/50
, jika Anda mengubahnya ket.a+v/3+l/10+f/50
, itu menghasilkan perilaku yang agak lebih menarik, tetapi program saat ini lebih kecil dan masih spek.