Misalnya, permainan Anda memiliki 100 musuh (di tim yang berbeda) berlarian dan AI mereka ingin memeriksa entitas terdekat untuk melihat mana yang harus diserang. Apa cara cepat untuk mengatur entitas tersebut sehingga setiap musuh tidak harus menghitung jarak antara dirinya dan semua entitas lainnya?
Singkatnya, apa cara cepat bagi entitas AI untuk menjawab pertanyaan "Siapa yang dekat dengan saya?"
3d
ai
entity-system
data-structure
khayman218
sumber
sumber
Jawaban:
Anda menginginkan indeks spasial seperti quadtree (2D) atau octree (3D).
sumber
Solusi paling sederhana adalah kisi . Letakkan kisi 2D di atas level Anda. Setiap sel dalam kisi menyimpan koleksi entitas yang saat ini menempatinya. Saat entitas bergerak, keluarkan mereka dari sel yang mereka tinggalkan dan tambahkan ke yang mereka masukkan.
Anda kemudian dapat menemukan entitas terdekat hanya dengan memeriksa sel-sel terdekat. Quadtree memoles ini dengan membagi kisi-kisi secara rekursif, tetapi kadang-kadang yang datar memadai, terutama jika ukuran level Anda tetap dan relatif kecil.
sumber