Bagaimana Dwarf Fortress melacak begitu banyak entitas tanpa kehilangan kinerja?

Di Dwarf Fortress, Anda dapat memiliki ratusan Dwarf, hewan, goblin, dll dalam game pada satu waktu, masing-masing dengan AI kompleks dan rutinitas pathfinding sendiri. Pertanyaan saya adalah bagaimana ini tidak menghasilkan penurunan yang nyata? Apakah setiap Dwarf berjalan di utasnya sendiri?

Sistem apa pun yang memiliki utas untuk setiap karakter yang begitu banyak akan kehabisan sumber daya dengan sangat cepat. Utas mungkin memberi Anda akses ke inti prosesor tambahan tetapi mereka tidak membuat sesuatu yang secara intrinsik lebih efisien, dan mereka datang dengan overhead.

Jawaban sederhananya adalah menjadi efisien dalam memproses setiap entitas dalam game.

• Jangan memproses setiap entitas setiap frame.
• Pisahkan pemrosesan menjadi hal-hal yang perlu sering dilakukan dan hal-hal yang tidak perlu sering dilakukan.
• Sebarkan algoritma yang sudah berjalan lama di beberapa bingkai sehingga tidak memblokir pemrosesan di sistem lain.
• Pastikan algoritma dan struktur data yang efisien digunakan.
• Tembolok hasil perhitungan mahal jika kemungkinan akan digunakan lagi.

Dwarf Fortress bukanlah open source, dan walaupun ada banyak dugaan dan rekayasa balik yang dapat menjelaskan bagaimana semua itu bekerja, saya akan lebih fokus pada beberapa teknik dasar untuk mengoptimalkan roguelike 3D (bukan grafik 3D, dunia 3D). Tipe yang sama.

Seperti halnya dengan semua video game ada banyak asap dan cermin yang menciptakan ilusi kompleksitas dari aturan dan sistem sederhana. Ini berkisar dari menggunakan angka acak sederhana untuk gerakan tanpa tujuan sepanjang jalan untuk memanggang mesh tingkat tinggi node untuk merintis jalan.

Gerakan

Berbicara tentang merintis jalan, ini seringkali bisa menjadi masalah yang sangat sulit untuk dipecahkan untuk ruang besar seperti peta DF dapat (sebanyak 768x768x64 IIRC) namun masalahnya dapat disederhanakan dan dipercepat dengan cara-cara ini:

• Jaringan simpul pra-panggang: Ketika peta dibuat, dunia dapat dipecah menjadi potongan-potongan, dan setiap potongan dapat memiliki pintu keluar dan pintu masuk yang dipetakan. Ketika chunk diperbarui, seperti ketika dinding dibangun, hanya jaringan chunk yang perlu diperbarui.
• Penjelajahan Bertahap: Menjalankan lintasan di seluruh peta, sel untuk sel, akan membutuhkan banyak waktu, alih-alih Anda akan menemukan lintasan di jaringan chunk yang lebih besar, yang memetakan semua koneksi antar chunk, dan kemudian hanya menjalankan lintasan intra-chunk ketika bergerak dari chunk ke chunk. Ini melakukan 2 hal untuk Anda. Ini mempercepat pathfinding dengan memecahnya menjadi banyak potongan-potongan kecil, dan juga memungkinkan unit untuk mengubah arah bagian jalan di sepanjang jalan ketika sepotong pembaruan. Akan kembali jalur di jaringan besar jika ada node yang perlu lintas pembaruan.
• Kemudi acak: Saat tidak bergerak ke tujuan, unit hanya perlu berjalan tanpa tujuan. Banyak roguelikes hanya memindahkan unit dalam arah acak, yang terasa tidak wajar. Berbagai teknik kemudi dapat digunakan, yang sederhana lebih disukai untuk bergerak dalam garis lurus dan memiliki lebih sedikit kesempatan untuk bergerak ke arah yang memancar ke belakang, yang hanya memiliki peluang sekitar 1%. Jadi unit kadang-kadang akan berbalik arah sepenuhnya, tetapi jarang.

Saya tidak akan membahas dasar-dasar pencarian jalan. Kebanyakan roguelikes menggunakan A *, tetapi ada metode lain untuk menguliti kucing. Mmmm Kulit kucing ..

Tugas Pribadi

Salah satu hal utama yang membuat unit DF muncul dan terasa hidup adalah daftar sasaran pribadi mereka. Sebenarnya banyak game roguelike memiliki ini pada tingkat dasar. Pada dasarnya setiap unit memiliki daftar keinginan (dan untuk dorf Anda, tugas yang mungkin mereka ambil yang Anda minta untuk diselesaikan) dan mereka akan memilih dari mereka berdasarkan kepribadian mereka (statistik).

Beberapa tugas memiliki persyaratan. Membuat rok kulit mengharuskan dorf berada di toko ini yang memiliki barang-barang X. Jadi semuanya diperiksa dan ditambahkan sebagai tugas dalam daftar mereka. Sederhana seperti itu.

Karena sebagian besar waktu unit akan dalam perjalanan, pemeriksaan untuk apa unit lakukan bisa sangat cepat, hanya beberapa unit akan membuat pilihan pada saat tertentu, dan secara keseluruhan tidak ada perlambatan bahkan untuk ratusan atau ribuan unit. Dan ingat, di DF segala sesuatu dari lebah ke troglodytes ke pohon adalah satuan.

Dalam melakukan beberapa penelitian tambahan, jelas bahwa, meriah, DF melakukan pekerjaan buruk pathfinding secara umum. Itu tidak memecah peta menjadi potongan-potongan, itu memecah peta menjadi segmen atau area yang terhubung, (yang lebih baik daripada tidak ada yang pasti) sehingga penilaian saya di atas bahkan lebih sedikit contoh tentang cara kerja DF daripada yang saya pikirkan. :) Yang tidak mengatakan bahwa DF adalah sesuatu yang kurang dari luar biasa untuk sejuta alasan lainnya.

Ini menunjukkan bahwa yang penting dalam permainan adalah permainan. Bukan grafis, pemrograman tidak bagus, penulisan tidak hebat, musik tidak hebat, bahkan antarmuka; tidak ada yang bahkan 1% sama pentingnya dengan gim itu sendiri.

Dari halaman ini :

Yah [pathfinding] terlihat luar biasa dari akhir saya, karena ada banyak karakter yang melakukannya sekaligus.

TA: Para kurcaci kebanyakan bergerak dengan A *, dengan heuristik jarak jauh biasa. Bagian yang sulit adalah bahwa ia tidak dapat benar-benar memanggil A * jika mereka tidak tahu mereka bisa sampai di sana terlebih dahulu, atau itu akan berakhir membanjiri peta dan membunuh prosesor.

Saya tidak tahu apakah ini benar-benar cara dia mencegah "membanjiri peta" , tetapi cara biasa untuk melakukan ini dalam permainan menggunakan perubahan ke A * disebut Hierarchical Path-Finding A * , atau HPA *. Idenya adalah untuk memecah grid menjadi potongan yang lebih sedikit tetapi lebih besar, kemudian gunakan A * untuk menemukan jalur terbaik dari setiap potongan ke potongan tetangganya. Anda dapat menggunakan ini untuk membuat grafik yang jauh lebih kecil untuk menjalankan A * untuk setiap unit.

Anda juga dapat mengelompokkan potongan-potongan itu menjadi potongan yang lebih besar, yang merupakan asal dari "hierarkis".

Algoritma ini hanya menemukan jalur yang hampir optimal, tetapi untuk game seperti Dwarf-Fortress yang biasanya ok. Masih dijamin untuk menemukan jalan jika ada; dan ketika tidak ada jalan, itu hanya akan mengisi grafik yang lebih kecil, menghemat banyak waktu.

Ada juga abstraksi HPA * yang berhubungan dengan unit yang dapat melintasi beberapa medan tetapi tidak pada yang lain (seperti tebing, yang dapat dilintasi unit udara tetapi unit darat tidak bisa) . Ini disebut HAA * , dan ada artikel yang sangat mudah dimengerti menjelaskannya di sini .

Anda dapat membaca lebih lanjut tentang berbagai algoritma pencarian jalan di sini .

Jika ada, itu sebaliknya - semuanya berjalan pada satu utas dan sekarang mencapai titik di mana itu menjadi faktor pemblokiran (terakhir kali saya memeriksa!)

Alasannya cepat adalah karena tidak ada grafik yang bagus. Ini menipu, tetapi hal utama yang memperlambat barang adalah menggambar sesuatu (pikirkan dua pertiga bingkai dalam judul AAA). Karena benteng kerdil itu cukup mendasar, ia mencurahkan sisa waktu itu untuk melakukan hal-hal menarik.

Saya tidak tahu bagaimana DF dikodekan tetapi jumlah AI tidak benar-benar membuat saya terkesan karena apa yang orang awasi adalah AI tidak perlu presisi . Sangat layak untuk melakukan banyak hal hanya setiap beberapa detik. Ini juga layak untuk menggunakan perhitungan yang tidak tepat. Ketidaksempurnaan menghemat banyak kinerja . Anda dapat menjalankan pengambilan keputusan rutin 100 unit setiap 100 ms, atau Anda dapat menjalankannya selama 1000 unit setiap detik, ini akan membutuhkan jumlah waktu CPU yang sama tetapi juga ... Anda memiliki 10 kali unit.

Berikut adalah contoh sederhana bagaimana seseorang dapat menangani banyak unit:

int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

AI akan menjadi semakin tidak responsif semakin banyak, tetapi pemain mungkin hanya akan memperhatikannya dalam kasus-kasus ekstrim.