Cara meningkatkan kinerja untuk fungsi-fungsi mahal di pembangun kota 2d

9

Saya sudah mencari jawaban tetapi saya tidak dapat menemukan pendekatan terbaik untuk menangani fungsi / perhitungan yang mahal.

Dalam permainan saya saat ini (bangunan kota berbasis ubin 2d) pengguna dapat menempatkan bangunan, membangun jalan, dll. Semua bangunan membutuhkan koneksi ke persimpangan yang harus ditempatkan pengguna di perbatasan peta. Jika bangunan tidak terhubung ke persimpangan ini, tanda "Tidak terhubung ke jalan" akan muncul di atas bangunan yang terkena dampak (jika tidak harus dihapus). Sebagian besar bangunan memiliki radius dan mungkin terkait satu sama lain juga (misalnya pemadam kebakaran dapat membantu semua rumah dalam radius 30 ubin). Itulah yang saya juga perlu perbarui / periksa ketika koneksi jalan berubah.

Kemarin saya mengalami masalah kinerja yang besar. Mari kita lihat skenario berikut ini: Seorang pengguna tentu saja dapat juga menghapus bangunan dan jalan. Jadi, jika seorang pengguna sekarang memutuskan koneksi setelah persimpangan saya perlu memperbarui banyak bangunan pada saat yang sama . Saya pikir salah satu saran pertama adalah untuk menghindari loop bersarang (yang jelas merupakan alasan besar dalam skenario ini) tetapi saya harus memeriksa ...

  1. jika bangunan masih terhubung ke persimpangan jika genteng jalan telah dihapus (saya melakukan itu hanya untuk bangunan yang terkena dampak oleh jalan itu). (Mungkin masalah yang lebih kecil dalam skenario ini)
  2. daftar ubin radius dan dapatkan bangunan dalam radius (loop bersarang - masalah besar!) .

    // Go through all buildings affected by erasing this road tile.
    foreach(var affectedBuilding in affectedBuildings) {
        // Get buildings within radius.
        foreach(var radiusTile in affectedBuilding.RadiusTiles) {
            // Get all buildings on Map within this radius (which is technially another foreach).
            var buildingsInRadius = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);  
    
            // Do stuff.
        }
    }

Ini semua memecah FPS saya dari 60 hingga hampir 10 selama satu detik.

Saya juga bisa melakukannya. Gagasan saya adalah:

  • Tidak menggunakan utas utama (fungsi Perbarui) untuk yang satu ini tetapi utas lainnya. Saya mungkin mengalami masalah penguncian ketika saya mulai menggunakan multithreading.
  • Menggunakan antrian untuk menangani banyak perhitungan (apa yang akan menjadi pendekatan terbaik dalam kasus ini?)
  • Simpan lebih banyak informasi di objek saya (bangunan) untuk menghindari lebih banyak perhitungan (misalnya bangunan dalam radius).

Dengan menggunakan pendekatan terakhir saya bisa menghapus satu sarang dalam bentuk foreach ini sebagai gantinya:

// Go through all buildings affected by erasing this road tile.
foreach(var affectedBuilding in affectedBuildings) {
    // Go through buildings within radius.
    foreach(var buildingInRadius in affectedBuilding.BuildingsInRadius) {
        // Do stuff.
    }
}

Tapi saya tidak tahu apakah ini cukup. Gim seperti Kota Skylines harus menangani jauh lebih banyak bangunan jika pemain memiliki peta besar. Bagaimana mereka menangani hal-hal itu ?! Mungkin ada antrian pembaruan karena tidak semua bangunan melakukan pembaruan pada saat yang sama.

Saya menantikan ide dan komentar Anda!

Terima kasih banyak!

Yheeky
sumber
2
Menggunakan profiler akan membantu mengidentifikasi bit kode mana yang memiliki masalah. Bisa jadi cara Anda menemukan bangunan yang terkena dampak, atau mungkin // melakukan hal-hal. Sebagai catatan permainan besar seperti City Skylines mengatasi masalah ini dengan menggunakan struktur data spasial seperti quad-tree, sehingga semua pertanyaan spasial jauh lebih cepat daripada melalui array dengan for loop. Misalnya, dalam kasus Anda, Anda bisa memiliki grafik ketergantungan semua bangunan dan dengan mengikuti grafik itu bisa langsung tahu apa yang memengaruhi apa yang tanpa iterasi.
Exaila
Terima kasih atas informasi terperinci. Saya suka ide dependensi! Saya akan melihat yang itu!
Yheeky
Nasihat Anda luar biasa! Saya hanya menggunakan VS profiler yang menunjukkan kepada saya, bahwa saya memiliki fungsi pathfinding untuk setiap bangunan yang terpengaruh untuk memeriksa apakah koneksi persimpangan masih valid. Tentu saja itu mahal sekali! Hanya sekitar 5 FPS tetapi lebih baik daripada tidak sama sekali. Saya akan menyingkirkan itu dan menugaskan bangunan ke ubin jalan jadi saya tidak perlu melakukan pemeriksaan pathfinding ini berulang kali. Terima kasih banyak! Tidak, saya hanya perlu memperbaiki bangunan dalam masalah radius yang lebih besar.
Yheeky
Saya senang Anda menemukan manfaatnya: D
Exaila

Jawaban:

3

Caching cakupan gedung

Gagasan untuk men-caching informasi bangunan mana yang berada dalam jangkauan bangunan efektor (yang dapat Anda cache dari efektor atau yang terpengaruh) jelas merupakan ide yang bagus. Bangunan (biasanya) tidak bergerak, jadi ada sedikit alasan untuk mengulang perhitungan mahal ini. "Apa yang mempengaruhi bangunan ini" dan "apa yang mempengaruhi bangunan ini" adalah sesuatu yang hanya perlu Anda periksa ketika sebuah bangunan dibuat atau dihapus.

Ini adalah pertukaran klasik siklus CPU untuk memori.

Menangani informasi cakupan berdasarkan wilayah

Jika ternyata Anda menggunakan terlalu banyak memori untuk melacak informasi ini, lihat apakah Anda dapat menangani informasi tersebut berdasarkan wilayah peta. Bagilah peta Anda menjadi wilayah kuadrat darin *nubin. Jika suatu daerah sepenuhnya ditutupi oleh pemadam kebakaran, semua bangunan di wilayah itu juga tercakup. Jadi, Anda hanya perlu menyimpan informasi cakupan berdasarkan wilayah, bukan oleh bangunan individu. Jika suatu wilayah hanya tercakup sebagian, Anda perlu kembali menangani koneksi dengan membangun di wilayah itu. Jadi fungsi pembaruan untuk bangunan Anda pertama kali akan memeriksa, "Apakah wilayah tempat gedung ini dilindungi oleh pemadam kebakaran?" dan jika tidak "Apakah bangunan ini secara individual dilindungi oleh pemadam kebakaran?". Ini juga mempercepat pembaruan, karena ketika pemadam kebakaran dihilangkan, Anda tidak perlu lagi memperbarui status cakupan 2000 bangunan, Anda hanya perlu memperbarui 100 bangunan dan 25 wilayah.

Pembaruan tertunda

Pengoptimalan lain yang dapat Anda lakukan adalah tidak memperbarui semuanya dengan segera dan tidak memperbarui semuanya secara bersamaan.

Apakah bangunan masih terhubung ke jaringan jalan atau tidak, Anda tidak perlu memeriksa setiap frame (Ngomong-ngomong, Anda mungkin juga menemukan beberapa cara untuk mengoptimalkan ini secara khusus dengan melihat sedikit ke dalam teori grafik). Akan sangat memadai jika bangunan hanya memeriksa secara berkala setiap beberapa detik setelah bangunan dibangun (DAN jika ada perubahan pada jaringan jalan). Hal yang sama berlaku untuk efek rentang bangunan. Sangat dapat diterima jika sebuah bangunan hanya memeriksa setiap beberapa ratus frame, "Apakah setidaknya salah satu dari departemen pemadam kebakaran yang mempengaruhi saya masih aktif?"

Jadi, Anda dapat memiliki loop-pembaruan Anda hanya melakukan perhitungan mahal ini untuk beberapa ratus bangunan sekaligus untuk setiap pembaruan. Anda mungkin ingin memberikan preferensi ke bangunan yang saat ini ada di layar, sehingga para pemain mendapatkan umpan balik langsung atas tindakan mereka.

Mengenai Multithreading

Pembangun kota cenderung berada di sisi yang lebih mahal secara komputasi, terutama jika Anda ingin membiarkan pemain membangun sangat besar dan jika Anda ingin memiliki kompleksitas simulasi yang tinggi. Jadi dalam jangka panjang mungkin tidak salah untuk berpikir tentang perhitungan apa dalam game Anda yang dapat ditangani secara tidak sinkron.

Philipp
sumber
Ini menjelaskan mengapa SimCity pada SNES membutuhkan waktu untuk daya untuk terhubung kembali, saya kira itu terjadi dengan efek luas lainnya juga.
lozzajp
Terima kasih atas komentar Anda yang bermanfaat! Saya juga berpikir bahwa menyimpan lebih banyak informasi dalam memori dapat mempercepat permainan saya. Saya juga menyukai gagasan untuk membagi TileMap menjadi beberapa daerah tetapi saya tidak tahu apakah pendekatan ini cukup baik untuk menghilangkan masalah awal saya yang sudah lama tertunda. Saya punya pertanyaan tentang pembaruan yang tertunda. Mari kita asumsikan saya memiliki fungsi yang membuat FPS saya turun dari 60 menjadi 45. Apa pendekatan terbaik untuk membagi perhitungan untuk menangani jumlah sempurna yang bisa ditangani CPU?
Yheeky
@Yheeky Tidak ada solusi yang berlaku secara universal untuk ini, karena sangat tergantung situasi perhitungan mana yang dapat Anda tunda, yang Anda tidak bisa dan apa yang merupakan unit perhitungan yang masuk akal.
Philipp
Cara saya mencoba menunda kalkulasi ini adalah membuat antrian dengan item yang memiliki bendera "Sedang Diperbarui". Hanya item ini yang disetel ke true. Ketika perhitungan telah selesai, item telah dihapus dari daftar dan item berikutnya ditangani. Ini seharusnya berhasil, bukan? Tetapi metode apa yang bisa digunakan jika Anda tahu bahwa satu perhitungan itu sendiri akan menurunkan FPS Anda?
Yheeky
1
@Yekek Seperti yang saya katakan, tidak ada solusi yang berlaku secara universal. Apa yang biasanya saya coba (dalam urutan itu): 1. Lihat apakah Anda dapat mengoptimalkan perhitungan itu dengan menggunakan algoritma dan / atau struktur data yang lebih tepat. 2. Lihat apakah Anda dapat membaginya menjadi sub-tugas yang dapat Anda tunda satu per satu. 3. Lihat apakah Anda dapat melakukannya dalam ancaman terpisah. 4. Singkirkan mekanik permainan yang membutuhkan perhitungan itu dan lihat apakah Anda dapat menggantinya dengan sesuatu yang kurang mahal secara komputasi.
Philipp
3

1. Pekerjaan duplikat .

Anda affectedBuildingsmungkin saling berdekatan, sehingga jari-jari yang berbeda akan tumpang tindih. Tandai bangunan yang perlu diperbarui, lalu perbarui.

var toBeUpdated = new HashSet<Tiles>();
foreach(var affectedBuilding in affectedBuildings) {
    foreach(var radiusTile in affectedBuilding.RadiusTiles) {
         toBeUpdated.Add(radiusTile);

}
foreach (var tile in toBeUpdated)
{
    var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);
    // Do stuff.
}

2. Struktur Data yang Tidak Cocok.

var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);

harus jelas

var buildingsInRadius = tile.Buildings;

dimana Bangunan adalah IEnumerable dengan waktu iterasi konstan (misalnya a List<Building>)

Peter
sumber
Poin bagus! Saya kira saya mencoba menggunakan Distinct () pada yang menggunakan MoreLINQ tapi saya setuju bahwa ini mungkin lebih cepat daripada memeriksa duplikat.
Yheeky