Struktur data untuk interpolasi dan threading?

20

Saya telah berurusan dengan beberapa masalah jittering frame-rate dengan permainan saya belakangan ini, dan tampaknya solusi terbaik adalah yang disarankan oleh Glenn Fiedler (Gaffer di Game) dalam klasik Fix Your Timestep! artikel.

Sekarang - Saya sudah menggunakan langkah waktu yang tetap untuk pembaruan saya. Masalahnya adalah bahwa saya tidak melakukan interpolasi yang disarankan untuk rendering. Hasilnya adalah bahwa saya mendapatkan bingkai yang dilipatgandakan atau dilewati jika tingkat render saya tidak cocok dengan tingkat pembaruan saya. Ini bisa terlihat secara visual.

Jadi saya ingin menambahkan interpolasi ke permainan saya - dan saya tertarik untuk mengetahui bagaimana orang lain menyusun data dan kode mereka untuk mendukung ini.

Jelas saya akan perlu menyimpan (di mana? / Bagaimana?) Dua salinan informasi kondisi permainan yang relevan dengan penyaji saya, sehingga dapat diinterpolasi di antara mereka.

Selain itu - ini sepertinya tempat yang bagus untuk menambahkan threading. Saya membayangkan bahwa utas pembaruan dapat berfungsi pada salinan ketiga dari kondisi permainan, meninggalkan dua salinan lainnya sebagai hanya-baca untuk utas render. (Apakah ini ide yang bagus?)

Tampaknya memiliki dua atau tiga versi dari kondisi permainan dapat memperkenalkan kinerja dan - yang jauh lebih penting - masalah keandalan dan produktivitas pengembang, dibandingkan dengan hanya memiliki satu versi. Jadi saya sangat tertarik pada metode untuk mengurangi masalah-masalah itu.

Dari catatan khusus, saya pikir, adalah masalah bagaimana menangani menambah dan menghapus objek dari kondisi permainan.

Akhirnya, tampaknya beberapa keadaan tidak diperlukan secara langsung untuk render, atau akan terlalu sulit untuk melacak versi yang berbeda (misalnya: mesin fisika pihak ketiga yang menyimpan satu keadaan) - jadi saya tertarik untuk mengetahui caranya orang-orang telah menangani data semacam itu dalam sistem seperti itu.

Andrew Russell
sumber

Jawaban:

4

Jangan mencoba mereplikasi seluruh kondisi permainan. Menggabungkannya akan menjadi mimpi buruk. Cukup isolasi bagian-bagian yang variabel dan diperlukan dengan rendering (mari kita sebut ini "Status Visual").

Untuk setiap kelas objek, buat kelas yang menyertainya yang akan dapat menampung objek Status Visual. Objek ini akan diproduksi oleh simulasi, dan dikonsumsi oleh rendering. Interpolasi akan dengan mudah menghubungkannya. Jika keadaan tidak berubah dan diteruskan oleh nilai, Anda tidak akan mengalami masalah threading.

Render biasanya tidak perlu tahu apa-apa tentang hubungan logis antara objek, oleh karena itu struktur yang digunakan untuk rendering akan menjadi vektor biasa, atau paling banyak pohon sederhana.

Contoh

Desain tradisional

class Actor
{
  Matrix4x3 position;
  float fuel;
  float armor;
  float stamina;
  float age;

  void Simulate(float deltaT)
  {
    age += deltaT;
    armor -= HitByAWeapon();
  }
}

Menggunakan kondisi Visual

class IVisualState
{
  public:
  virtual void Interpolate(const IVisualState &newVS, float f) {}
};
class Actor
{
  struct VisualState: public IVisualState
  {
    Matrix4x3 position;
    float fuel;
    float armor;
    float stamina;
    float age;

    virtual auto_ptr<IVisualState> Interpolate(const IVisualState &newVS, float f)
    {
      const VisualState &newState = static_cast<const VisualState &>(newVS);
      IVisualState *ret = new VisualState;
      ret->age = lerp(this->age,newState.age);
      // ... interpolate other properties as well, using any suitable interpolation method
      // liner, spline, slerp, whatever works best for the given property
      return ret;
    };
  };

  auto_ptr<VisualState> state_;

  void Simulate(float deltaT)
  {
    state_->age += deltaT;
    state_->armor -= HitByAWeapon();
  }
}
Suma
sumber
1
Contoh Anda akan lebih mudah dibaca jika Anda tidak menggunakan "baru" (kata yang disimpan dalam C ++) sebagai nama parameter.
Steve S
3

Solusi saya jauh lebih elegan / rumit daripada kebanyakan. Saya menggunakan Box2D sebagai mesin fisika saya sehingga menyimpan lebih dari satu salinan dari status sistem tidak dapat dikelola (mengkloning sistem fisika kemudian mencoba untuk menjaga mereka tetap sinkron, mungkin ada cara yang lebih baik tetapi saya tidak bisa datang dengan satu).

Alih-alih, saya terus menghitung jumlah generasi fisika . Setiap pembaruan menambah generasi fisika, ketika sistem fisika memperbarui dua kali lipat, generasi menghasilkan pembaruan ganda juga.

Sistem rendering melacak generasi yang diberikan terakhir dan delta sejak generasi itu. Ketika merender objek yang ingin diinterpolasi posisi mereka dapat menggunakan nilai-nilai ini bersama dengan posisi dan kecepatan mereka untuk menebak di mana objek harus dirender.

Saya tidak membahas apa yang harus dilakukan jika mesin fisika terlalu cepat. Saya hampir berpendapat bahwa Anda seharusnya tidak melakukan interpolasi untuk gerakan cepat. Jika Anda melakukan keduanya, Anda harus berhati-hati agar sprite tidak melompat-lompat dengan menebak terlalu lambat kemudian menebak terlalu cepat.

Ketika saya menulis hal-hal interpolasi saya menjalankan grafik pada 60Hz dan fisika pada 30Hz. Ternyata Box2D jauh lebih stabil ketika dijalankan pada 120Hz. Karena ini kode interpolasi saya menjadi sangat sedikit digunakan. Dengan menggandakan target, framerate fisika pada pembaruan rata-rata dua kali per frame. Dengan jitter yang bisa 1 atau 3 kali juga, tetapi hampir tidak pernah 0 atau 4+. Tingkat fisika yang lebih tinggi agak memperbaiki masalah interpolasi dengan sendirinya. Saat menjalankan fisika dan framerate pada 60Hz Anda mungkin mendapatkan 0-2 pembaruan per frame. Perbedaan visual antara 0 dan 2 sangat besar dibandingkan dengan 1 dan 3.

deft_code
sumber
3
Saya telah menemukan ini juga. Lingkaran fisika 120Hz dengan pembaruan bingkai hampir 60Hz membuat interpolasi hampir tidak bernilai. Sayangnya ini hanya berfungsi untuk set game yang mampu menghasilkan loop fisika 120Hz.
Saya baru saja mencoba beralih ke loop pembaruan 120Hz. Ini tampaknya memiliki manfaat ganda untuk membuat fisika saya lebih stabil dan membuat game saya terlihat mulus dengan frame rate yang tidak cukup-60Hz. Kelemahannya adalah ia menghancurkan semua fisika permainan yang telah saya atur dengan saksama - jadi ini jelas merupakan opsi yang harus dipilih sejak awal dalam suatu proyek.
Andrew Russell
Juga: Saya sebenarnya tidak mengerti penjelasan Anda tentang sistem interpolasi Anda. Kedengarannya seperti ekstrapolasi, sebenarnya?
Andrew Russell
Panggilan yang bagus. Saya sebenarnya menggambarkan sistem ekstrapolasi. Mengingat posisi, kecepatan, dan berapa lama sejak pembaruan fisika terakhir, saya memperkirakan di mana objek akan berada jika mesin fisika tidak berhenti.
deft_code
2

Saya telah mendengar pendekatan ini untuk timesteps yang disarankan cukup sering, tetapi dalam 10 tahun dalam permainan, saya tidak pernah bekerja pada proyek dunia nyata yang mengandalkan stempel waktu dan interpolasi yang tetap.

Tampaknya umumnya lebih banyak upaya daripada sistem timestep variabel (dengan asumsi rentang framerate yang masuk akal, dalam kisaran 25Hz-100Hz).

Saya memang mencoba pendekatan interpolasi + timestep tetap sekali untuk prototipe yang sangat kecil - tidak ada threading, tetapi pembaruan logika timestep tetap, dan rendering secepat mungkin ketika tidak memperbarui itu. Pendekatan saya di sana adalah memiliki beberapa kelas seperti CInterpolatedVector dan CInterpolatedMatrix - yang menyimpan nilai sebelumnya / saat ini, dan memiliki accessor yang digunakan dari kode render, untuk mengambil nilai untuk waktu render saat ini (yang akan selalu antara sebelumnya dan waktu saat ini)

Setiap objek gim akan, pada akhir pembaruannya, mengatur keadaan saat ini ke satu set vektor / matriks yang saling terkait ini. Hal semacam ini dapat diperluas untuk mendukung threading, Anda memerlukan setidaknya 3 set nilai - yang sedang diperbarui, dan setidaknya 2 nilai sebelumnya untuk menginterpolasi antara ...

Perhatikan bahwa beberapa nilai tidak dapat diinterpolasi secara sepele (mis. 'Frame animasi sprite', 'special effect active'). Anda mungkin dapat melewati interpolasi sepenuhnya, atau dapat menyebabkan masalah, tergantung pada kebutuhan gim Anda.

IMHO, yang terbaik adalah dengan hanya pergi variabel timestep - kecuali jika Anda membuat RTS, atau permainan lain di mana Anda memiliki sejumlah besar objek, dan harus menyimpan 2 simulasi independen dalam sinkronisasi untuk permainan jaringan (hanya mengirim pesanan / perintah melalui jaringan, daripada posisi objek). Dalam situasi itu, fixed-timestep adalah satu-satunya pilihan.

bluescrn
sumber
1
Tampaknya setidaknya Quake 3 menggunakan pendekatan ini, dengan "centang" default menjadi 20 fps (50 ms).
Suma
Menarik. Saya kira itu memang memiliki keuntungan untuk permainan PC multipemain yang sangat kompetitif, untuk memastikan bahwa PC yang lebih cepat / framerat yang lebih tinggi tidak mendapatkan terlalu banyak keuntungan (kontrol yang lebih responsif, atau perbedaan kecil tapi dapat dieksploitasi dalam perilaku fisika / tabrakan) ?
bluescrn
1
Sudahkah Anda dalam 10 tahun tidak berlari ke game mana pun yang menjalankan fisika tidak berhadapan dengan simulasi dan penyaji? Karena saat Anda melakukan itu, Anda harus melakukan interpolasi atau menerima jerkiness yang dirasakan dalam animasi Anda.
Kaj
2

Jelas saya akan perlu menyimpan (di mana? / Bagaimana?) Dua salinan informasi kondisi permainan yang relevan dengan penyaji saya, sehingga dapat diinterpolasi di antara mereka.

Ya, untungnya kuncinya di sini adalah "relevan dengan penyaji saya". Ini mungkin tidak lebih dari menambahkan posisi lama dan cap waktu untuk itu ke dalam campuran. Diberikan 2 posisi, Anda dapat melakukan interpolasi ke posisi di antara mereka, dan jika Anda memiliki sistem animasi 3D, Anda biasanya dapat hanya meminta pose pada titik waktu yang tepat.

Ini benar-benar sangat sederhana - bayangkan penyaji Anda harus dapat merender objek game Anda. Dulu ia menanyakan objeknya seperti apa, tapi sekarang harus bertanya seperti apa itu pada waktu tertentu. Anda hanya perlu menyimpan informasi apa pun yang diperlukan untuk menjawab pertanyaan itu.

Selain itu - ini sepertinya tempat yang bagus untuk menambahkan threading. Saya membayangkan bahwa utas pembaruan dapat berfungsi pada salinan ketiga dari kondisi permainan, meninggalkan dua salinan lainnya sebagai hanya-baca untuk utas render. (Apakah ini ide yang bagus?)

Itu hanya terdengar seperti resep untuk menambah rasa sakit pada titik ini. Saya belum memikirkan keseluruhan implikasinya tetapi saya kira Anda mungkin mendapatkan sedikit throughput tambahan dengan biaya latensi yang lebih tinggi. Oh, dan Anda mungkin mendapat manfaat dari bisa menggunakan inti lain, tapi saya tidak tahu.

Kylotan
sumber
1

Catatan Saya tidak benar-benar melihat ke dalam interpolasi sehingga jawaban ini tidak mengatasinya; Saya hanya khawatir memiliki satu salinan dari status permainan untuk utas render, dan satu lagi untuk utas pembaruan. Jadi saya tidak bisa mengomentari masalah interpolasi, meskipun Anda bisa memodifikasi solusi berikut untuk interpolasi.

Saya telah bertanya-tanya tentang ini karena saya telah merancang dan memikirkan mesin multithreaded. Jadi saya mengajukan pertanyaan tentang Stack Overflow, tentang bagaimana menerapkan semacam pola desain "penjurnalan" atau "transaksi" . Saya mendapat beberapa tanggapan yang baik, dan jawaban yang diterima benar-benar membuat saya berpikir.

Sangat sulit untuk membuat objek abadi, karena semua anak-anaknya juga harus abadi, dan Anda harus benar-benar berhati-hati bahwa semuanya benar-benar abadi. Tetapi jika Anda memang berhati-hati, Anda bisa membuat superclass GameStateyang berisi semua data (dan subdata dan sebagainya) di game Anda; bagian "Model" dari gaya organisasi Model-View-Controller.

Kemudian, seperti yang dikatakan Jeffrey , instance dari objek GameState Anda cepat, hemat memori, dan aman. Kelemahan besar adalah bahwa untuk mengubah apa pun tentang model, Anda perlu membuat ulang model, jadi Anda harus benar-benar berhati-hati bahwa kode Anda tidak berubah menjadi kekacauan besar. Menyetel variabel dalam objek GameState ke nilai baru lebih banyak terlibat dari sekadar var = val;, dalam hal baris kode.

Saya sangat tertarik dengan itu. Anda tidak perlu menyalin seluruh struktur data Anda setiap frame; Anda cukup menyalin pointer ke struktur yang tidak bisa diubah. Itu dengan sendirinya sangat mengesankan, tidakkah Anda setuju?

Ricket
sumber
Ini memang struktur yang menarik. Namun saya tidak yakin itu akan bekerja dengan baik untuk permainan - karena kasus umumnya adalah pohon benda yang cukup datar yang masing-masing berubah tepat sekali per frame. Juga karena alokasi memori dinamis adalah hal yang tidak boleh.
Andrew Russell
Alokasi dinamis dalam kasus seperti ini sangat mudah dilakukan secara efisien. Anda dapat menggunakan buffer bundar, tumbuh dari satu sisi, relase dari yang kedua.
Suma
... itu bukan alokasi dinamis, hanya penggunaan dinamis memori yang sudah dialokasikan;)
Kaj
1

Saya mulai dengan memiliki tiga salinan status permainan dari setiap node dalam grafik adegan saya. Satu sedang ditulis oleh utas grafik adegan, satu sedang dibaca oleh renderer, dan yang ketiga tersedia untuk membaca / menulis segera setelah salah satu dari mereka perlu bertukar. Ini bekerja dengan baik, tetapi terlalu rumit.

Saya kemudian menyadari bahwa saya hanya perlu menjaga tiga keadaan dari apa yang akan diberikan. Utas pembaruan saya sekarang mengisi satu dari tiga buffer "RenderCommands" yang jauh lebih kecil, dan Renderer membaca dari buffer terbaru yang saat ini sedang tidak ditulis, yang mencegah utas agar tidak pernah menunggu satu sama lain.

Dalam pengaturan saya, setiap RenderCommand memiliki geometri / bahan 3d, matriks transformasi, dan daftar lampu yang mempengaruhinya (masih melakukan render maju).

Thread render saya tidak lagi harus melakukan perhitungan jarak culling atau cahaya, dan ini mempercepat banyak hal pada adegan besar.

Dwayne
sumber