Bagaimana Dwarf Fortress melacak begitu banyak entitas tanpa kehilangan kinerja?

79

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?

RSH1
sumber
6
Pertanyaan menarik. Meskipun saya tidak suka cara ini diungkapkan, karena itu hanya akan menjadi spekulasi untuk menjawab pertanyaan ini sebagai kata. Bagaimanapun, Anda mungkin telah melihat artikel ini berbicara dengan Tarn Adams. Di mana mereka secara singkat membahas penemuan jalur.
MichaelHouse
25
Ini benar-benar menghasilkan perlambatan nyata setelah Anda memiliki topologi terowongan yang kompleks dan 100+ kurcaci.
Russell Borogove
3
Ya, DF dalam pengalaman saya sangat lambat dalam skenario yang Anda gambarkan.
argentage
4
Hancurkan tangga utama dan perhatikan tetesan framerate Anda seperti batu untuk sesaat sementara setiap kurcaci tiba-tiba mem-repath pada waktu yang bersamaan.
Mooing Duck
2
Saya akan berpadu dan setuju bahwa DF bukan contoh terbaik; sebenarnya DF terkenal menderita masalah kinerja.
Robert S.

Jawaban:

110

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.
Kylotan
sumber
2
Beri +1 untuk ini, karena benar-benar menjelaskan apa yang terjadi, alih-alih membahas tentang gambar seperti saya. :)
Matt Kemp
4
Agar adil, saya memberi Anda +1 juga karena saya lupa tentang aspek itu, dan itu sangat benar - keluarkan gfx dari persamaan dan itu seperti membuat komputer 2x atau 3x lebih cepat secara instan.
Kylotan
Saya pernah mendengar bahwa DF sekarang multithreaded, tetapi setidaknya sampai saat ini, semuanya dilakukan dalam satu utas. (Mungkin masih, tidak yakin)
Mooing Duck
@ MoooDuck Masih tidak.
Tharwen
63

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.

DampeS8N
sumber
1
1024X1024X32? Vertikal adalah 128 atau 256 saya percaya. Jauh lebih besar dari 32.
Lawton
@Lawton Saya percaya saya salah tentang ukuran maks, tetapi tingginya tidak salah. Saya memperbaikinya. Saya memuat permainan dan memulai saya hanya sekitar 45 level. Lebih mungkin 'disimulasikan' tetapi saya tidak memiliki akses ke mereka untuk menggali atau membangun.
DampeS8N
@ DampeS8N Saya baru saja memuat peta menengah yang tidak dimodifikasi dan dapat melihat dari +16 hingga -156, sekitar 180 level. 40 peta level adalah pengecualian, bukan aturan. Bahkan jika Anda hanya dapat menggali 40 dari mereka karena terhalang oleh akifer atau lava, itu tidak relevan, karena area di bawahnya masih dipenuhi dengan kesenangan yang disimulasikan.
Lawton
@Lawton, peta saya hanya memungkinkan saya untuk melewati 45 level. Mereka benar-benar variabel tetapi saya tidak dapat dengan mudah menemukan angka pada berapa banyak setiap peta dapat diakses. Ini juga tergantung pada versi gim yang kita gunakan. Pada akhirnya itu tidak terlalu penting untuk jawaban saya.
DampeS8N
Itu adalah pos lama tetapi kedalaman di benteng katai tergantung pada lapisan sedimen. Seperti kerak bumi yang lebih tebal di beberapa tempat. DF tidak sepenuhnya benar secara geologis tetapi mereka mempelajarinya seperti pro: D.
Madmenyo
50

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.

Pathfinding hirarkis

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 .

BlueRaja - Danny Pflughoeft
sumber
3
Saya menemukan video ini dari pengembang RimWorld sangat mencerahkan. Ini adalah game yang mirip, sementara hanya dalam 2D. Dia menjelaskan dasar-dasar di balik pencarian jalan dan manfaat memisahkan peta menjadi daerah. youtube.com/watch?v=RMBQn_sg7DA
Sire
18

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.

Matt Kemp
sumber
8
Satu titik data yang mendukung ini adalah penulisan ulang OpenGL dari waktu yang lalu yang saya ingat membawa peningkatan frame rate yang besar. Jadi, bahkan melakukan grafik sprite sederhana yang dilakukan DF secara efisien berdampak.
milimoose
3
+1 Strip graphics = sejumlah besar waktu luang untuk komputasi gameplay
Laurent Couvidou
2
Perlu dicatat bahwa grafis DF hampir sama mendesaknya dengan game 2D indie modern mana pun. Ada banyak tekstur, meskipun kecil dan sederhana, dan dapat tersebar di monitor HD real-estate penuh. Tidak ada efek partikel mencolok atau apa pun yang Anda miliki, tetapi karya "cat semua piksel ini" masih ada dan karena jumlah panggilan undian yang diperlukan untuk ukuran ubin kecil sebenarnya merupakan tantangan yang cukup besar untuk membuat performan.
DampeS8N
Ini mungkin terlihat seperti jawaban konyol pada awalnya, tetapi ini benar, bayangkan apa yang dapat dilakukan dengan daya GPU 4-12gb gram dan 4-12tflops jika Anda tidak perlu menggambar primitif kompleks, membuka bungkusan, tekstur, mengubah vektor 3d menjadi array 2d piksel, bayangan, dll
Felype
10

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.

API-Beast
sumber
Ada banyak yang bisa dikatakan untuk melangkah melalui tumpukan tugas yang tidak tepat tingkat-bingkai. Game AAA sering secara eksplisit memberi waktu pada setiap departemen dalam persentase frame sehingga satu departemen tidak bisa menginjak-injak departemen lain. Jika metode untuk menggerakkan goyangan pohon berdasarkan kecepatan dan arah angin lambat, lebih sedikit pohon yang akan diproses daripada menghabiskan anggaran tim lain.
DampeS8N