Adaptive Tile Refresh milik Commander Keen

 (fabiensanglard.net)
2 poin oleh GN⁺ 2023-07-29 | 1 komentar | Bagikan ke WhatsApp
  • Adaptive Tile Refresh (ATR) adalah teknik scrolling yang dipakai Commander Keen 1~3 untuk menghindari refresh layar penuh EGA yang lambat, dengan menggambar ulang hanya tile yang berubah alih-alih seluruh layar
  • Mode EGA Dh menyimpan layar 320x200 16 warna dengan membaginya ke dalam 4 plane (C0~C3), dan jika seluruh layar 32KiB ditulis setiap frame melalui bus ISA, hasilnya hanya sekitar 5fps sehingga sulit mencapai refresh 60Hz
  • ATR menangani pergeseran vertikal dan horizontal di dalam layar virtual menggunakan register CRTC_START, OFFSET, dan PEL, lalu saat menyentuh tepi melakukan jolt untuk mengembalikan acuan layar dan menimpa hanya tile yang diperlukan ke VRAM
  • Biaya jolt ditentukan oleh jumlah tile yang harus digambar ulang; pada contoh Commander Keen 1, dari 250 tile hanya 40 tile yang berubah sehingga hanya 16% dari seluruh layar yang digambar ulang, dan desain map dengan banyak tile berulang sangat menentukan performa
  • Commander Keen 4~6 beralih dari ATR ke metode yang memanfaatkan wraparound aperture VRAM 64KiB untuk terus melakukan panning sambil menggambar hanya strip tepi yang baru terlihat, tetapi pada sebagian kartu Super VGA muncul masalah kompatibilitas karena bisa masuk ke memori yang belum diinisialisasi

Batas bandwidth yang dihadapi di EGA

  • Commander Keen berjalan paling baik di PC dengan EGA (Enhanced Graphic Adapter), dan pemrograman grafis dilakukan melalui register konfigurasi serta jendela memori 64KiB yang dipetakan ke VRAM
  • EGA menyimpan data internal dalam 4 plane C0, C1, C2, C3
    • C0 menyimpan bit paling rendah (LSB) dari setiap nilai piksel 4-bit
    • C3 menyimpan bit paling tinggi (MSB)
    • Setiap plane terdiri dari 200 baris, masing-masing 40 byte per baris
  • Struktur 4 bank ini dirancang untuk menyediakan bandwidth yang cukup agar bisa mengikuti layar CRT, dan CRTC membaca 4 byte secara paralel
  • Mode EGA Dh yang dipakai Commander Keen menyediakan resolusi 320x200 dan 16 warna
    • Tidak memakai pendekatan seperti mode 10h yang menyusun ulang tinta dari 64 nilai warna
    • Di mode Dh, warna palet tetap bisa diubah dalam 16 warna dasar, dan ini dipakai untuk efek fade in/out sederhana di Commander Keen

Adaptive Tile Refresh menghindari redraw layar penuh

  • Bottleneck utama yang diselesaikan ATR adalah bandwidth
  • Menulis nilai 4-bit untuk layar 320x200 piksel, sekitar 32KiB, di setiap frame adalah beban yang terlalu besar bagi bus ISA
  • Loop sederhana yang memperbarui seluruh layar setiap kali hanya bertahan di kisaran 5 frame per detik
  • EGA juga punya cara untuk menulis ke 4 bank sekaligus, tetapi meski berguna untuk menghapus layar atau mereplikasi kolom seperti di Wolfenstein 3D, itu tidak cocok untuk masalah scrolling di Commander Keen

Scrolling mulus dengan register

  • ATR mula-mula membuat layar virtual yang lebih besar dari layar tampilan di dalam VRAM, lalu menggerakkan area tampilan dengan mengubah nilai CRTC_START yang menentukan dari mana CRTC mulai membaca
  • Scrolling vertikal relatif sederhana
    • Dengan menambahkan masing-masing 16 baris di atas dan bawah layar tampilan, setiap plane memakai 40 x 232 = 9,280 byte
    • Saat layar digeser satu baris ke atas, CRTC_START dinaikkan 40 byte
    • Saat layar digeser satu baris ke bawah, CRTC_START diturunkan 40 byte
  • Scrolling horizontal memakai kombinasi register OFFSET dan PEL
    • Jika OFFSET diatur ke 2, padding 16 byte ditambahkan di antara baris sehingga ada ruang 16 piksel di kiri dan kanan layar virtual
    • Jika CRTC_START dinaikkan 1, karena struktur plane layar akan bergerak dalam satuan 8 piksel sehingga terlalu kasar
    • Horizontal Pel Panning, yaitu register PEL, dapat melewati hingga 7 bit setelah CRTC_START, sehingga memungkinkan scrolling horizontal per piksel
  • Pergerakan horizontal nyata dilakukan dengan menyesuaikan CRTC_START memakai hasil pembagian koordinat dengan 8, lalu mengatur PEL dengan sisa koordinat tersebut (% 8)

Jolt dan pembaruan parsial per tile

  • Saat mencapai tepi layar virtual, ATR melakukan jolt untuk memusatkan kembali layar virtual
  • Jika seluruh layar digambar ulang, proses ini memakan sekitar 200ms dan frame rate turun ke 5fps, jadi jolt bekerja dengan menimpa hanya tile yang berubah alih-alih melakukan redraw penuh
  • Level Commander Keen dibuat dari tile 16x16
    • Saat artis menggambar tile, sistem build memberi setiap tile sebuah ID unik
    • Desainer level menyusun map dengan menempatkan ID tile di editor 2D
    • Engine melacak ID tile apa yang ada di layar virtual
  • Pada saat jolt, ID tile dari keadaan layar virtual saat ini dibandingkan dengan keadaan target yang sudah dipusatkan kembali
    • Tile yang sama dilewati
    • Hanya tile yang berbeda yang ditimpa ke VRAM
  • Efisiensi jolt berbanding terbalik dengan jumlah tile yang harus digambar ulang, sehingga desainer game harus menyusun tilemap agar banyak tile berulang
  • Pada contoh Commander Keen 1, ketika bergerak mulus ke kanan lalu layar virtual habis dan terjadi jolt 16 piksel ke kiri, dari 250 tile hanya 40 tile yang berubah
    • Rasio yang digambar ulang hanya 16% dari seluruh layar
  • Di atas latar belakang, ada layer sprite
    • Engine menyimpan daftar koordinat tile kotor yang tertimpa sprite
    • Di setiap frame baru, daftar kotor itu ditelusuri untuk memulihkan tile latar lalu menggambar ulang sprite

Double buffer dan drifting pada trilogi kedua

  • Untuk menghindari artefak visual, seluruh sistem diduplikasi menjadi dua framebuffer
    • Saat CRTC membaca satu buffer, penulisan bisa dilakukan ke lokasi VRAM lain pada buffer kedua
    • Setiap buffer memakai (320 + 32) * (200 + 32) * 4 / 8 = 40,832 byte
    • Total double buffer menjadi 40,832 * 2 = 81,664 byte, melebihi 64KiB pada kartu EGA asli IBM
  • Menurut VileR, hanya papan IBM EGA asli yang dibekali 64KiB, sementara sebagian besar klon EGA yang muncul sekitar 1986~1987 sudah memakai 256K, dan saat Commander Keen dirilis hampir tidak ada kartu EGA dengan kapasitas di bawah 256K
  • Commander Keen 1~3 menampilkan pola berulang yang dibutuhkan ATR dengan cukup jelas di layar, tetapi ciri yang sama tidak terlalu menonjol pada Commander Keen 4~6
  • Trilogi Keen kedua memanfaatkan perilaku wraparound saat CRTC_START mencapai ujung blok 64KiB lalu kembali ke awal blok
    • Layar terus melakukan panning sambil menggambar hanya baris strip tepi yang baru terlihat
    • Karena jolt hilang, kebutuhan untuk membuat bidang berulang dengan warna serupa juga berkurang
  • Pendekatan ini lebih merupakan penyempurnaan untuk menghilangkan jolt daripada penambahan fitur baru
    • Kedua elemen double buffer drift di ruang VRAM dengan kecepatan yang sama sehingga tidak saling bertumpuk
    • Dalam kebanyakan kasus, cara ini bekerja dengan baik
  • Pada sebagian kartu Super VGA, muncul masalah
    • Pada kartu dengan implementasi non-standar dan memori lebih besar, alih-alih wraparound dari akhir ke awal, sistem bisa masuk ke memori nyata yang belum diinisialisasi
    • Daripada menangani tiap kartu non-standar secara terpisah, Carmack memilih solusi yang lebih mudah: saat mencapai ujung layar, ia menerima adanya hitch dan menyalin seluruh layar ke atas
  • Teknik drifting ini mungkin membuat pendekatan menyimpan tile dan sprite di VRAM untuk memanfaatkan salinan cepat VRAM-to-VRAM menjadi tidak memungkinkan, tetapi karena jumlah yang perlu digambar tiap frame sangat sedikit, kemungkinan besar hal itu bukan masalah besar

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-29
Opini Hacker News

  • Kelancaran scrolling di Commander Keen 4~6 tidak tertandingi oleh game lain di PC selama bertahun-tahun, bahkan setelah game-game beralih ke grafis 256 warna
    Berkat kerja teknis luar biasa John Carmack dan seni palet 16 warna Adrian Carmack, id pada dasarnya membuat game platform PC dengan tampilan terbaik selama suatu periode pada 1990-an
    Adrian Carmack bukan kerabat Carmack yang lebih terkenal itu, tetapi menurut saya ia adalah maestro tersembunyi palet 16 warna

    • Rasanya cukup aneh bahwa semua game klasik Commander Keen dikembangkan dan dirilis antara Desember 1990 dan Desember 1991
      Laju peningkatan grafis dan gameplay benar-benar luar biasa
      Perubahan dari game pertama: https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
      Perubahan hingga game terakhir: https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
      Saya memainkannya sendiri saat masih kecil waktu itu, dan sempat lupa bahwa semuanya terjadi secepat itu
    • Untuk game platform PC dengan tampilan terbaik selama suatu periode pada 1990-an, saya akan memilih Prince Of Persia
      Bukan bermaksud meremehkan Commander Keen, tetapi visual dan mekanika game PoP terasa tak tertandingi menurut standar saat itu
      Saat pertama memainkannya sekitar usia 7 tahun, kesannya seperti sihir, dan sampai sekarang masih menjadi game platform favorit saya, jadi memang ada bias
      Tentu saja PoP sama sekali tidak punya scrolling, dan bagian itu adalah ilmu hitamnya Commander Keen
    • Mungkin ini sudut pandang saat melihat ke belakang sekarang, tetapi banyak dari pengembangan inovatif semacam ini tampak cukup sederhana dibandingkan pengembangan masa kini
      “Karena memori lambat, gambar ulang hanya yang berubah” sekarang hampir terasa seperti ide yang sudah jelas
      Meski begitu, optimisasi di episode 4~6 tetap menarik. Menarik juga bahwa di episode 1~3 mereka melakukan seluruh pekerjaan karena asumsi bahwa buffer tidak melakukan wrapping, padahal sebenarnya buffer itu wrapping sehingga pekerjaan tersebut menjadi sia-sia
    • Bagaimana dengan Jazz Jackrabbit? Game itu juga punya scrolling VGA yang benar-benar mulus

  • Saya pernah membuat game berbasis tile dengan DirectX 5 di Windows 98, dan pada awalnya mengimplementasikan cara yang mirip dengan yang dijelaskan di tulisan ini
    Situasinya sedikit lebih sederhana karena layar tidak melakukan scrolling, tetapi banyak tile bisa saja perlu digambar ulang
    Pada akhirnya saya membuang semua kode itu, karena saat memprofil biaya menggambar seluruh layar pada kartu RIVA TnT, waktunya terlalu kecil bahkan untuk diukur
    Saya bersyukur melewatkan era EGA dalam pengembangan PC. Kalau berada di masa itu, rasanya saya tidak akan pernah menyelesaikan apa pun

    • Saya justru menyukai pemrograman tingkat rendah seperti itu
      Mengoptimalkan dengan bit shift alih-alih perkalian, menulis kode inti dalam assembly, lalu seiring prosesor berkembang menulis 16 bit atau 32 bit sekaligus
      Karena sumber daya yang saya punya sedikit, saya terus belajar dari buku perpustakaan daerah dan floppy disk berisi file txt
      Saya terlalu muda dan kurang pengalaman sehingga tidak pernah menyelesaikan apa pun, tetapi saya berhasil membuat scrolling vertikal yang mulus, scrolling horizontal hampir berjalan, dan juga mengimplementasikan double buffering untuk kubus 3D yang berputar. Itu termasuk depth buffering, matematika, sampai menggambar poligon per baris
      Lalu DirectX muncul dan titik kontak dengan mesin menghilang; kubus 3D berputar menjadi terlalu mudah sehingga tidak menyenangkan lagi
    • Bahkan saat itu, jarak antara kartu grafis paling lambat dan paling cepat sudah makin besar
      Bus melebar dari 8 bit menjadi 16/32 bit, kartu grafis mendukung posted writes sehingga CPU tidak perlu terlalu lama menunggu, dan CPU juga makin cepat, sehingga sistem yang cepat bisa menulis layar 640x480x256 dengan lebih dari 300 frame per detik
      Dalam kasus ini, mungkin itu adalah buffer memori sistem yang di-cache dan salinan DMA, atau mungkin blitter yang menangani penggambaran. Namun bahkan pada era Windows 98, di antara kartu 3D kelas bawah ada juga yang akses CPU-nya sangat lambat, hanya sedikit lebih baik daripada kartu bus ISA lama
      Karena resolusi layar menjadi terlalu tinggi, sekarang ada bagian yang agak berbalik lagi. Walaupun bisa menggambar ulang seluruh layar 4K pada 60 frame per detik, sulit menyebutnya efisien
      Game biasanya masih menggambar ulang semuanya, tetapi compositor desktop melakukan cukup banyak optimisasi, misalnya menetapkan layer secara dinamis ke hardware plane untuk mengurangi area yang digambar ulang

  • Saya bekerja di perusahaan game lain pada periode yang sama, dan secara mandiri menemukan teknik scrolling seperti pendekatan kedua itu
    Saya tidak menganggapnya sesuatu yang begitu mencengangkan. Kalau waktu itu sedang memecahkan masalah yang sama, kemungkinan besar orang akan sampai pada kesimpulan serupa
    Saya juga membuat driver audio PWM sendiri untuk memutar sampel suara lewat PC speaker, dan sepertinya semua orang lain juga melakukan hal serupa
    PC tidak mendapat cukup cinta sebelum kami semua pindah ke konsol. Demo seperti 8088 MPH dari Hornet masih membuat saya bersemangat

    • Kalau itu game yang dirilis, bisakah memberi tahu judulnya agar bisa dibandingkan? Saya setuju bahwa solusi serupa mungkin terpikir oleh kebanyakan orang, tetapi saya penasaran apakah hasil saat dimainkan terasa sama
    • Kalau itu tidak sehebat itu, mengapa saat itu begitu banyak game platform scrolling papan atas pun terasa patah-patah?
      Itu memang bukan syarat wajib untuk game yang menyenangkan, tetapi kelancaran yang ditunjukkan Keen, terutama pada hardware kelas rendah seperti di bawah 10MHz, benar-benar membuka mata pada masa itu
    • Reputasi sering kali muncul bukan dari penemuannya sendiri, melainkan dari kemampuan komersialisasi dan pemasaran
      Pasti ada tak terhitung penemuan hebat yang tidak dikenal selama ribuan tahun
      Saya juga “menemukan” sesuatu yang mirip 10 tahun sebelum LinkedIn muncul, tetapi tidak berhasil mengomersialkannya. Menurut saya sebagian besar penemuan tidak pernah dikenal luas
      Karena itu banyak startup dimulai oleh dua orang: satu ahli dan satu pebisnis
      Jadi itu tidak salah. Penemuan ini mungkin saja bukan sesuatu yang istimewa, tetapi menjadi istimewa karena gabungan kebaruan, kegunaan, dan komersialisasi yang berhasil

  • Dalam buku luar biasa Masters of Doom, Keen dijelaskan sebagai game ala Mario, yaitu game side-scrolling
    id menawarkan teknologi ini kepada Nintendo sebagai opsi untuk mem-porting Mario ke PC, tetapi Nintendo menolaknya, dan karena itulah Keen lahir
    Itu adalah lompatan besar bagi game PC, dan membuka era baru game PC
    Namun yang masih belum benar-benar saya pahami adalah, apa yang begitu berbeda antara teknologi NES dan PC sehingga Nintendo bisa menerapkan side-scrolling beberapa tahun lebih awal daripada PC

    • EGA pada dasarnya menyediakan framebuffer besar
      Dalam mode grafis EGA, Anda bisa menggambar apa pun yang diinginkan—garis, lingkaran, piksel individual, dan sebagainya—dan memang dibuat untuk dipakai seperti itu
      Namun scrolling tidak gratis. Memori harus disalin langsung, dan seperti yang ditunjukkan artikel yang ditautkan, jika dipaksakan secara kasar, karena batas bandwidth bus ISA hasilnya hanya sekitar 5 frame per detik
      NES dan konsol game 8/16-bit lainnya tidak dibuat untuk menggambar apa pun secara arbitrer. Mereka dibuat untuk merender tile
      Anda cukup mendefinisikan kisi tile latar belakang dan memberikan offset scroll. Sprite juga bekerja mirip, tetapi bisa bergerak secara independen. Semua ini tersedia “gratis” pada 60 frame per detik
      Kekurangannya adalah tidak mudah merender sesuatu secara arbitrer. Misalnya, untuk mewarnai satu piksel individual di suatu tempat, diperlukan workaround yang cukup parah
      Jadi ini bukan masalah yang “ditemukan” Nintendo lebih dulu daripada IBM; IBM membuat sistem grafis serbaguna yang disesuaikan untuk komputer serbaguna dan grafis statis, serta menyediakan kontrol halus atas setiap piksel. Kalau melihat kartu EGA, itu perangkat yang cukup besar dengan banyak silikon
      Sebaliknya, Nintendo membuat sistem grafis khusus yang jauh lebih sederhana dan disesuaikan untuk menggeser tile
    • Sebenarnya mereka membuat port SMB3 dan menunjukkannya kepada Nintendo
      Ketika Nintendo tidak menerimanya, mereka membuat aset baru yang kemudian menjadi Keen
      Video port-nya ada di sini: https://youtu.be/1YWD6Y9FUuw
    • Saya tidak sepenuhnya yakin, tetapi setahu saya NES memiliki chip grafis khusus untuk manipulasi sprite, sedangkan di PC semua ini harus dilakukan dalam perangkat lunak
    • Metode dalam tulisan itu adalah meniru tile yang dikelola hardware lewat software dengan menggunakan framebuffer piksel independen
      Untuk sisi NES, https://www.nesdev.org/wiki/PPU tampaknya titik awal yang bagus
      Tantangan utamanya bukanlah “menemukan cara melakukan side-scrolling” itu sendiri, melainkan menyesuaikan engine game side-scrolling agar bekerja dengan baik dalam ruang memori dan batasan bandwidth dari sistem yang sama sekali berbeda
    • Sepertinya NES dan GB memang berbasis tile
      Karena game dibuat berbasis sprite dengan layer, cara untuk “mengakselerasi” 2D ini cukup masuk akal

  • Dalam wawancara John Carmack oleh Lex Fridman, mereka membahas semua inovasi utama di setiap game
    Episodenya benar-benar menarik, jadi kalau punya waktu saya sangat merekomendasikannya. Durasinya kira-kira 5 jam

  • Saya masih ingat masa ketika saya percaya tahu hampir semua elemen rahasia di Commander Keen Goodbye Galaxy
    Teman-teman sekolah sering bertanya kepada saya tentang rahasia level yang mereka mainkan di komputer sekolah sepulang sekolah

    • Iri sekali. Di sekolah saya, sejauh orang-orang yang pernah saya ajak bicara, saya adalah satu-satunya geek yang pernah mendengar Commander Keen

  • Begitu melihat fabiensanglard.net, saya langsung memberi rekomendasi

    • Dia benar-benar seperti harta karun. Buku CPS1-nya juga luar biasa
      Kalau ada yang tahu blog game klasik lain yang teknis dan mendalam, saya ingin mereka membagikannya
      https://nicole.express/ dan https://sudden-desu.net/ juga termasuk favorit saya

  • Saya memahami bagaimana scrolling vertikal bekerja jika titik awal framebuffer disesuaikan per scanline, tetapi awalnya tidak jelas bagaimana scrolling horizontal bisa dilakukan tanpa membengkokkan framebuffer secara parah
    Setelah berpikir sedikit lagi, saya menyadari ini mirip menggambar gambar di sisi sebuah silinder. Di mana pun tepi kiri gambar digambar, selalu ada cara untuk memutar silinder lalu mengatur register CRTC_START dan PEL agar seluruh gambar terlihat jelas
    Bagian yang mengatakan bahwa “ketika mencapai tepi layar, sebagai solusi sederhana mereka menerima sedikit tersendat dan menyalin seluruh layar ke atas” juga menarik
    Saya ingat ketika memulai Keen biasanya muncul pesan seperti “VGA compatibility mode enabled”, dan saya selalu penasaran apa maksudnya

  • Commander Keen benar-benar gim kecil yang menggemaskan
    Sepertinya saya harus mencari cara untuk menjalankannya lagi
    Tapi sebaiknya bagaimana menjalankan ini? Setelah jadi “orang dewasa”, saya sudah sekitar 20 tahun tidak memakai Windows; bagaimana cara memainkannya di Debian?

    • Bisa langsung dimainkan: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Saya tidak setuju. Ini adalah gim untuk anak-anak yang, entah karena alasan apa, punya akses ke komputer tetapi tidak punya Nintendo
      Saat itu komputer kira-kira 10 kali lebih mahal daripada konsol, jadi biasanya karena orang dewasa punya pandangan kuat tentang apa yang seharusnya dilakukan anak-anak
      Dibandingkan gim-gim NES dan Genesis, gim ini kurang berjiwa. Dulu saya menyukainya, tetapi ketika baru-baru ini mencobanya lagi di DosBox, saya merasa jelas sekali tidak sebanding
    • DosBox menjalankan gim VGA lama dengan sangat baik, dan berjalan di hampir semua platform, termasuk di dalam browser: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Sepertinya DosBox
    • Commander Keen dan Jill of the Jungle dulu adalah gim yang pertama kali memperkenalkan saya pada PC. Kenangan yang sangat indah

  • Beberapa tahun lalu saya mengimplementasikan metode kedua, tetapi menggambar tepi depan saja pun sangat lambat
    Namun, saya menulisnya dalam C, dan tidak pernah benar-benar mempelajari pemrograman assembly dengan baik
    https://github.com/geon/kate/blob/master/src/platform/dos/eg...