Rustenstein 3D: Pemrograman game seperti tahun 1992

Rustenstein 3D: Pemrograman game seperti tahun 1992 Ditulis oleh Facundo Olano, 02 Februari 2022

Dua kali setahun, NextRoll merayakan Hack Week, di mana karyawan bekerja selama seminggu di sebuah proyek dari pilihan mereka. Ini adalah kesempatan bagus untuk bereksperimen, mempelajari teknologi baru, dan bekerja sama dengan orang-orang dari seluruh perusahaan. Anda dapat mempelajari semua tentang Hack Week di sini.

Seiring NextRoll semakin mengadopsi bahasa pemrograman Rust, biasanya para insinyur menggunakan Hack Week sebagai kesempatan untuk mendapatkan pengalaman dengannya. Pilihan populer lainnya adalah mengerjakan video game dan, seperti yang mungkin sudah Anda duga, kami sering melihatnya digabungkan dalam proyek video game Rust. Tahun lalu, sekelompok dari kami bekerja untuk memperluas permainan rpg-cli saya. Namun kali ini, kami ingin meningkatkannya dengan proyek yang akan menggunakan beberapa kekuatan Rust: pemrograman tingkat rendah, komputasi yang intens, dan interoperabilitas data C. Jadi kami memutuskan untuk mem-port game klasik Wolfenstein 3D ke Rust.

id Software terkenal karena mendorong amplop pemrograman game PC: pertama dengan mengimplementasikan scroller samping seperti NES pada perangkat keras yang tidak disiapkan untuk itu, kemudian secara praktis menciptakan dan mendominasi 3D genre first-person shooter, kemudian membuat jaringan dan multipemain internet menjadi kenyataan. Sepanjang jalan, mereka juga mempopulerkan metode distribusi shareware, mendorong modding komunitas dan open source semua judul hit mereka. Masters of Doom oleh David Kushner menceritakan kisahnya; Buku hitam Game Engine Fabien Sanglard menjelaskan detail teknis.

Mungkin kurang terkenal daripada penerusnya Doom and Quake, Wolfenstein 3D adalah tonggak besar dalam evolusi id Software dan game PC pada umumnya. Selain itu, karena teknologinya lebih primitif, kode sumbernya lebih mudah didekati untuk dipelajari dan diimplementasikan. Gim ini tidak memiliki mesin 3D nyata melainkan mensimulasikan dunia 3D dari peta 2D menggunakan teknik yang disebut Ray Casting. Semua gambar dilakukan dengan langsung meletakkan piksel di layar.

Beberapa tahun yang lalu, setelah membaca buku hitam Wolfenstein, saya menghabiskan beberapa waktu untuk mencoba mem-port-nya ke Python, berdasarkan port modern lainnya, wolf4sdl. Saya mencoba untuk tetap sedekat mungkin dengan sumber aslinya, yang terbukti sangat sulit, jadi saya akhirnya membatalkan proyek tersebut. Baru-baru ini, Mario Rugiero, yang juga membaca buku tersebut, mengusulkan port Rust sebagai proyek untuk Hack Week ini. Beberapa orang melompat masuk, begitu pula saya; meskipun, berdasarkan pengalaman saya sebelumnya, perusahaan masih tampak menakutkan: beberapa dari kami baru mengenal Rust, beberapa belum pernah bermain Wolf, beberapa belum membaca bukunya, dan tidak ada yang pernah menerapkan ray casting sebelumnya. Kami memulai tanpa banyak harapan untuk menunjukkan sesuatu pada akhir minggu, tetapi kami melihat peluang belajar yang sangat besar, jadi kami terjun langsung.

Kami secara kasar mengidentifikasi beberapa komponen permainan yang dapat ditangani secara terpisah, jadi setiap anggota memilih satu dan mulai bekerja di atasnya:

dekompresi file grafik dan parsing

file peta dekompresi, parsing dan interpretasi

Manipulasi grafis SDL dan rendering tekstur

ray casting

loop permainan dan manajemen input

rendering dunia Dalam kasus di mana output dari satu komponen diperlukan sebagai input untuk komponen berikutnya, kami menggunakan data pra-parsing atau hard-coded, yang diekstraksi dari referensi implementasi wolf4py dan wolf4sdl: dekompresi biner aset, hardcoded peta dan dinding, dll. Ini memungkinkan kami untuk membuat kemajuan secara paralel. Aktiva

Tugas pertama porting game adalah membaca datanya. Wolfenstein dikirimkan dengan satu set file untuk aset yang berbeda: grafik (gambar, tekstur dan sprite), audio (musik dan efek suara) dan peta. Salah satu komplikasinya adalah setiap versi gim memiliki berkas yang sedikit berbeda, dengan offset yang berbeda dan, dalam beberapa kasus, menggunakan metode kompresi yang berbeda. Untuk Rustenstein, kami menggunakan file .WL1 dari versi shareware, yang kami sertakan dalam repositori.

Setiap file menggunakan kombinasi yang berbeda dari beberapa algoritma dekompresi, yang semuanya harus kami port ke Rust:

• kompresi Huffman tradisional
• kompresi RLEW, algoritme pengkodean run-length yang bekerja pada tingkat kata

kompresi "Carmack", yang merupakan varian John Carmack metode LZ (Lempel-Ziv). Menurut Buku Hitam, tanpa banyak akses ke literatur, Carmack akan "menciptakan" sebuah algoritma untuk kemudian mengetahui bahwa orang lain telah melakukannya sebelumnya.

Mesin Serigala asli memiliki komponen Pengelola Memori untuk menangani alokasi dan pemadatan memori (bukan C malloc) serta Pengelola Halaman untuk memindahkan aset dari disk ke RAM. Kedua komponen tersebut tidak diperlukan dalam perangkat keras modern karena kami dapat dengan aman berasumsi bahwa kami dapat memasukkan semua aset ke dalam memori, jadi kami tidak memasukkannya ke dalam port kami.

Kode penguraian dan dekompresi dapat ditemukan di sini untuk peta, dan di sini untuk aset lainnya.

Daftar Isi

Toggle

Peta

Peta Wolfenstein 3D didefinisikan sebagai petak petak 64x64. Setiap peta memiliki dua lapisan ubin: satu untuk dinding dan pintu, dan satu lagi untuk menempatkan pemain, musuh, dan item bonus. Nilai ubin yang berbeda menentukan tekstur apa yang akan ditampilkan di dinding, kunci apa yang diperlukan untuk pintu, ke arah mana pemain menghadap, dll. Semua dinding memiliki ketinggian yang sama dan karena direpresentasikan sebagai balok di kisi ubin, semua persimpangan berbentuk persegi panjang ; sementara ini membatasi desain level, ini secara dramatis menyederhanakan algoritme ray casting untuk menggambar dunia 3D.

Di bawah ini adalah peta pertama dari episode pertama, seperti yang terlihat di editor peta Wolfenstein:

Dan peta yang sama dengan ASCII, seperti yang dicetak oleh kode debug kami:

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWW wwwwww WWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWW wwwwww WWWWWWWW WW WWWWWWWWWWWWWWWWWWWWWWWWWWWW | | Wwwwwwwwwwwwwwwww wwwwww wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwal | Wwwwwwwwww WWWWWWWWWWWWWWWWWWWWWWWWWWWW wwwwww W wwwwwwwwww WWWWWWWWWWWWWWWWWWWWWWWWWWWW wwwwww WWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW W WW WWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW W WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW W Wwwww WWWWWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWWWWWWW WW-wwwwww WWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW W Wwwww WWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW W WWWWWWWWWWWWWWWWWWWWWWWWWWWWW-WWWWWWWWWWWWWWWWWWWWWWWWWWWWW W WW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW | | WW WW WWWWWWWWWWWW WW WW W WW WWWWWWWWWWWW wwww wwww WW W WW WWWWWWWWWWWW Wwwww Wwwww WW W WW WWWWWWWWWWWWWWWWW wwwwwwwwww Wwwww WW W wwwwww-WWWWWWWWWWWWWWWWWWWWWWW-WWWWWWWWWWWW Wwwwwww WW wwww W Wwwww WWWWWWWWWWWWWWWWWWWWW wwwwwwwwwww WWWWWWWWWWWWWWW W Wwwww WWWWWWWWWWWWWWWWWWWWW wwwwwwwwwww WWWWWWWWWWWWWWW WWW WWWWWWWWWWWWWWWWWWWWW wwwwwwwwwww WWWWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWW wwwwwwwwwww WWW WWW WWWWW WWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW akan semakin dekat WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW W W Wwwwwww WWWWWWWWWWWWWWWWWWWWWWWWWWWW WW wwwwwwwwww WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWW WW wwwwwwwwwwwwww-WWWWWWWWWWWWWWWWWWWWWWWWWWWWW wwwwwwwwww WWW Wwwwwwwww WW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWW wwwwwwwwwww | | WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWW WWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWW WWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW P | | WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Gambar piksel

Untuk aset grafis, mendekompresi dan memuat data ke memori hanyalah setengah dari cerita. Potongan biner yang membuat setiap grafik (gambar, sprite, atau tekstur) diatur secara eksplisit untuk rendering cepat pada tampilan VGA yang awalnya dirancang untuk game tersebut. Ini berarti bahwa grafik diputar untuk digambar dalam kolom, dan kolom itu sendiri tampak disisipkan dalam file karena VGA memungkinkan penulisan paralel ke empat bank memori video yang berbeda.

Setiap byte dalam potongan biner grafis adalah indeks ke 256 palet warna yang digunakan di Wolfenstein 3D. Implementasi wolf4sdl referensi akan menulis potongan-potongan itu ke permukaan SDL, yang pada gilirannya akan diterjemahkan ke warna RGB sebelum disalin ke layar, seperti yang dijelaskan dalam posting blog ini. Karena binding Rust untuk SDL menggunakan set abstraksi yang berbeda (dan, khususnya, mereka tidak mengekspos fungsi SDL_ConvertPixels), kami memilih untuk mengonversi dari indeks palet ke warna RGB dengan cepat, menulis langsung ke tekstur RGB yang kemudian akan disalin ke kanvas yang dapat dirender. Ini berarti bahwa rutinitas rendering perlu disesuaikan untuk menulis merah, hijau dan biru b ytes untuk membentuk setiap piksel, bukan byte indeks palet tunggal.

fn put_pixel(penyangga: &mut , melempar : gunakan , x : u32 , y : u32 , warna : ( u8 , u8 , u8)) { membiarkan (R, G, B) = warna; membiarkan offset =

y

sebagai gunakan * melempar + x sebagai gunakan * 3; penyangga[offset] = R; penyangga[offset + 1] = G; penyangga[offset + 2] = B; }

Dua rutinitas rendering grafis yang kami terapkan langsung di-porting dari implementasi wolf4py, yang pada giliran porting hampir baris demi baris dari garpu referensi wolf4sdl. Pegangan rutin pertama menampilkan gambar penuh langsung ke layar. Ini digunakan untuk layar judul serta bilah status pemain di bagian bawah tampilan dalam game:

Rutin kedua, yang jauh lebih kompleks, bertugas menggambar sprite dan saat ini digunakan untuk menampilkan pemain senjata. Fungsi serupa tetapi bahkan lebih rumit dibiarkan porting: yang menggambar gambar berskala seperti tekstur dinding dan sprite musuh.

Sebuah sprite tak terduga muncul alih-alih senjata selama pengembangan.

Akan diharapkan untuk meningkatkan implementasi ini sehingga sebagian besar pemrosesan dilakukan sekali sebagai bagian dari langkah pemuatan aset, dan bongkahan biner disimpan dalam memori, siap untuk ditulis ke layar.

The kode terkait dapat ditemukan di sini.

Pengecoran Sinar

Di jantung mesin 3D Wolfenstein adalah algoritma Ray Casting. Rutinitas ini memungkinkan kita untuk memproyeksikan dunia 2D (didefinisikan oleh peta ubin 64×64) ke dalam tampilan 3D, hanya berdasarkan operasi 2D. Algoritma dapat diringkas sebagai berikut:

Pancarkan sinar dari posisi pemain saat ini untuk setiap kolom piksel di lebar layar. Misalnya, resolusi 3D Wolfenstein klasik adalah 320×200, jadi ini berarti memancarkan 320 sinar untuk menggambar bingkai. Perpanjang sinar ke arah yang ditentukan oleh piksel horizontal saat ini, posisi pemain dan bidang pandangnya, hingga menyentuh dinding di peta. Karena dindingnya berbentuk persegi panjang, perhitungan untuk memperpanjang sinar sangat disederhanakan, karena ada jarak yang konstan antara ubin dan ubin berikutnya. Sekali sinar memotong dinding, menghitung jarak dari pemain ke dinding itu, menggunakan trigonometri.

Setel ketinggian dinding, berbanding terbalik dengan jarak yang dihitung. Ini adalah: semakin jauh dinding yang terkena sinar dari pemain, semakin kecil dinding terlihat dari sudut pandang pemain (dan semakin kecil kolomnya n piksel kita perlu menggambar di layar).

Di bawah ini adalah versi JavaScript yang disederhanakan dari algoritme, berdasarkan tutorial ini:

fungsi rayCasting(layar, peta, pemain) { membiarkan presisi = 64; membiarkan incrementAngle = pemain.bidang pandang / layar.lebar; membiarkan Ketinggian dinding = []; membiarkan rayAngle = pemain.sudut - pemain.bidang pandang / 2; untuk(membiarkan rayCount = 0; rayCount  layar.lebar; rayCount++) { // memulai ray di posisi pemain  membiarkan sinar = {  x :  pemain . x , y :  pemain . y }; // sinar bergerak dengan kenaikan konstan  membiarkan rayCos = Matematika.cos(derajatUntukRadian(rayAngle)) /  presisi ; membiarkan raySin = Matematika.dosa(derajatUntukRadian(rayAngle))) / presisi; // memajukan sinar sampai menemukan dinding (ubin bukan nol) membiarkan dinding = 0; ketika(dinding == 0) { sinar.x += rayCos; sinar.y += raySin; dinding = peta[Math.floor(ray.x)][Math.floor(ray.x)]; } // menghitung jarak dari pemain ke dinding yang dipukul  membiarkan jarak = Matematika.sqrt(Matematika.pow(pemain.x - sinar.x, 2) + Matematika.pow(pemain.y - sinar.y, 2))) ;  // menghitung tinggi saat ini x berbanding terbalik dengan jarak  Tinggi Dinding.  dorongan ( Matematika . lantai ( layar . setengah Tinggi  /  jarak ) ); // menambah sudut untuk sinar berikutnya rayAngle += incrementAngle; } kembali Tinggi dinding; } 

Untuk implementasi ray casting yang lebih dekat dengan yang asli Wolfenstein 3D, seri tutorial ini direkomendasikan.

Rutinitas ini jelas merupakan yang paling menantang yang kami tangani selama Hack ini Minggu, tetapi kami membuat beberapa keputusan sejak awal yang cukup mengurangi kerumitan untuk dapat mengirimkan sesuatu tepat waktu. Pertama, kami menggunakan versi paling dasar dari algoritme yang mendukung dinding warna solid, bukan tekstur. Kedua, Josh Burroughs menemukan ray casting secara terpisah, berdasarkan tutorial, alih-alih mencoba membuat port baris demi baris dari implementasi Carmack asli (yang, mengutip Sanglard, adalah “740 baris buatan tangan yang sangat tidak ortodoks dan super kode perakitan yang efisien”) atau rekan wolf4sdl-nya (yaitu C tetapi masih sangat bergantung pada

goto pernyataan dan memiliki banyak efek samping global selain menghitung ketinggian dinding).

Inilah tampilan top-down dari peta Wolf pertama setelah mengintegrasikannya ke dalam rutinitas ray casting:

Implementasi lengkap dapat ditemukan di sini.

Dunia Re nderi ng

Dunia 3D ditampilkan dengan pemisahan pertama layar secara horizontal menjadi dua bagian, mengecat bagian atas dengan warna solid langit-langit dan bagian bawah dengan warna lantai. Setelah itu, kolom piksel perlu digambar dengan ketinggian yang diterima dari algoritma ray casting untuk setiap koordinat horizontal. Saat algoritme masih dalam pengembangan, kami menguji kode rendering dengan dinding hard-code:

Setelah rutinitas ray casting diterapkan dan diberi makan dengan peta Wolfenstein yang sebenarnya, kami mendapatkan array ketinggian dinding untuk setiap kolom piksel di layar, dan kami mulai melihat dunia:

Meskipun kami belum menerapkan rendering tekstur, ada beberapa trik yang meningkatkan tampilan pemandangan: menggunakan warna yang berbeda untuk permukaan horizontal dan vertikal dinding, dan membuat komponen r, g, b dari setiap piksel berbanding terbalik dengan jarak ke pemain (yang kita ketahui dari ketinggian dinding), untuk menghasilkan efek kegelapan:



Kode rendering dunia, kemudian, terlihat seperti ini:

 tekstur   .with_lock(Tidak ada, |penyangga:  &mut  ,  melempar :   gunakan |  {  // menggambar warna lantai dan langit-langit membiarkan lantai = color_map[VGA_FLOOR_COLOR]; membiarkan langit-langit = color_map[x as usize]; membiarkan vm = view_height / 6; untuk x di 0..pix_width { untuk y di 0..pix_height / 2 { membiarkan langit-langit = warna_gelap(langit-langit, vm - y, pix_center); put_pixel(penyangga, melempar, x, y, langit-langit); } untuk y di pix_height / 2..pix_height { membiarkan lantai = warna_gelap(lantai, y - vm, pix_center); put_pixel(penyangga, melempar, x, y, lantai); } } untuk x di 0..pix_width {  // gunakan warna berbeda untuk permukaan dinding horizontal dan vertikal membiarkan mut warna = jika ray_hits [x as usize].horisontal { color_map[155] } kalau tidak { warna_peta
 }; membiarkan saat ini = min(ray_hits[x as usize].tinggi, pix_center); warna = warna_gelap(warna, saat ini, pix_center); untuk y di pix_center - saat ini..pix_center + saat ini { put_pixel(penyangga, melempar, x,  y , warna ); } } }) fn warna_gelap(warna:  (u8,u8,u8), keringanan:  u32, maks:  u32) -> (u8,u8,u8) { membiarkan (R,G, B) = warna; membiarkan  faktor  =  ringan  sebagai f64 /  maks sebagai f64 /  KEGELAPAN; membiarkan rs = (R sebagai  f64     faktor )  sebagai  u8 ;  membiarkan  gs  = ( G  sebagai   f64    faktor )  sebagai  u8 ;  membiarkan bs = (B sebagai f64 *  faktor ) sebagai u8; (rs, gs, bs) } 
 
 

Sehari sebelum demo, kami hanya memiliki potongan permainan: aset pemuatan belum selesai, kami memiliki bug show-stopper dalam penguraian peta dan rendering sprite, dan mesin ray casting bekerja di peta hardcode 2D, terpisah dari proyek lainnya. Dalam beberapa jam terakhir yang menakjubkan, semuanya baru saja beres: bug telah diperbaiki, komponen yang berbeda cocok bersama dan, dengan beberapa peretasan dan banyak kode jelek, kami berhasil mengumpulkan video yang tampak mengesankan, tepat di waktu untuk sesi demo Hack Week. Kami bahkan punya waktu untuk memasukkan animasi wajah karakter di menit-menit terakhir! Seluruh pengalaman itu mengingatkan saya pada cerita-cerita tentang perusahaan video game yang menyusun build satu kali dengan tergesa-gesa, hanya untuk membuat demo E3.