Kultspillet Doom brugte militært udviklet datastruktur til sin banebrydende grafik-engine

Illustration: Steam
Spillet Doom blev udgivet i 1993 og blev hurtigt populært hos forbrugere for sin blodige grafik, men også hos software-entusiaster for sin banebrydende grafik-engine.

Chefprogrammøren for Doom, John Carmack, havde et betydeligt problem:

Han stod med en grov udgave af det, der skulle blive et banebrydende skydespil – men pc'er dengang havde CPU'er, der knap kunne lave et enkelt FLOPS.

Det skriver udvikler og master-studerende i computational analysis Sinclair Target på sin blog Twobitstory, hvor han også beskriver, hvordan John Carmack implementerede helt nye computermodeller i spillets kode for at imødekomme den simple hardware i private hjem anno 1993.

Læs også: Diablo er kommet til din browser

For den begrænsede CPU-kraft betød, at nogle af banerne i skydespillet laggede voldsomt, når de skulle renderes. En sand katastrofe for et spil, der gerne ville være hektisk og actionpacked.

Løsning udviklet af det amerikanske luftvåben

John Carmacks søgen efter en løsning bragte ham tilbage til en model, der blev beskrevet og udviklet af en forskningsenhed i det amerikanske luftvåben (PDF) mere end 20 år tidligere.

Læs også: Steam vil lade alle spil køre på Linux via modificeret Wine-distribution

Med de såkaldte BSP trees, forskerne havde beskrevet, kunne John Carmack og hans team optimere Doom-spillets famøse engine. Og kalde sig de første til at implementere teknologien i et skydespil.

Ros for at tænke akademisk

Sinclair Target roser i sit blogindlæg chefudvikleren for at implementere avancerede datastrukturer, herunder især BSP trees, i Doom i stedet for at ty til de løsninger, man normalt brugte i datidens spilprogrammering.

»Perhaps the accomplishment that we should really celebrate is the Doom game engine as a whole, which is a seriously nifty piece of work. We shouldn’t forget that the visible surface determination problem was just one of many problems that Carmack had to solve to make the Doom engine work,« skriver Sinclair Target og fortsætter:

»That he was able, on top of everything else, to read about and implement a complicated data structure unknown to most programmers speaks volumes about his technical expertise and his drive to perfect his craft.«

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (12)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Jacob Gorm Hansen

Bogen "Computer Graphics" (kendt som Foley & van Dam) som i andenudgaven har vaeret udgivet siden 1990 (foerste udgave siden 1982) omtaler BSP-trees, saa det maa nok siges at have vaeret en "textbook method" som alle der havde taget et bachelor-niveau kursus i computergrafik maatte forventes at kende til i 1993. Men det er naturligvis stadig sejt nok at faa det til at virke og koere med kun en enkelt floating point operation i sekundet...

  • 5
  • 0
Peter Hansen

Bogen "Computer Graphics" (kendt som Foley & van Dam) som i andenudgaven har vaeret udgivet siden 1990 (foerste udgave siden 1982) omtaler BSP-trees, saa det maa nok siges at have vaeret en "textbook method" som alle der havde taget et bachelor-niveau kursus i computergrafik maatte forventes at kende til i 1993. Men det er naturligvis stadig sejt nok at faa det til at virke og koere med kun en enkelt floating point operation i sekundet...


Det du skriver er faktisk ordret hvad der står i blogindlægget:

Carmack consulted a 1991 paper by Chen and Gordon as well as a 1990 textbook called Computer Graphics: Principles and Practice. Though no citation is provided for this claim, it is probably true. The 1991 Chen and Gordon paper outlines a front-to-back rendering approach using BSP trees that is basically the same approach taken by Doom, right down to what I’ve called the “implicit z-buffer” data structure that prevents farther polygons being drawn over nearer polygons. The textbook provides a great overview of BSP trees and some pseudocode both for building a tree and for displaying one. (I’ve been able to skim through the 1990 edition thanks to my wonderful university library.) Computer Graphics: Principles and Practice is a classic text in computer graphics, so Carmack might well have owned it.

Still, Carmack found himself faced with a novel problem—”How can we make a first-person shooter run on a computer with a CPU that can’t even do floating-point operations?”—did his research, and proved that BSP trees are a useful data structure for real-time video games. I still think that is an impressive feat, even if the BSP tree had first been invented a decade prior and was pretty well theorized by the time Carmack read about it.

  • 0
  • 0
Peter Hansen

Det var dælme heller ikke meget så. Meeeen, mon ikke der menes et enkelt Mega FLOPS.

x87 is a floating-point-related subset of the x86 architecture instruction set. It originated as an extension of the 8086 instruction set in the form of optional floating-point coprocessors that worked in tandem with corresponding x86 CPUs. These microchips had names ending in "87". This was also known as the NPX (Numeric Processor eXtension). Like other extensions to the basic instruction set, x87 instructions are not strictly needed to construct working programs, but provide hardware and microcode implementations of common numerical tasks, allowing these tasks to be performed much faster than corresponding machine code routines can. The x87 instruction set includes instructions for basic floating-point operations such as addition, subtraction and comparison, but also for more complex numerical operations, such as the computation of the tangent function and its inverse, for example.

Most x86 processors since the Intel 80486 have had these x87 instructions implemented in the main CPU, but the term is sometimes still used to refer to that part of the instruction set. Before x87 instructions were standard in PCs, compilers or programmers had to use rather slow library calls to perform floating-point operations

https://en.wikipedia.org/wiki/X87#80387

Doom kører ikke imponererende godt på en 386'er jf. denne Youtube-video:

https://www.youtube.com/watch?time_continue=147&v=9_2qGaIOvjs&feature=em...

Så spørgsmålet er, hvor stor Carmarcks præstation egentlig var, når det kommer til stykket.

  • 0
  • 1
Mads Thomsen

Fabien Sanglard har skrevet to ret fantastiske bøger, Game Engine Black Book om hhv. Wolfenstein 3D og DOOM. Jeg mener at han arbejder på en om Quake.

Han skiller både hardwaren fra tidspunktet og koden til DOOM fuldstændigt ad og forklarer hvordan delene hænger sammen. Det er et ret imponerende stykke reverse engineering.

Bogen om DOOM findes som PDF her, og kan bestilles på print:
http://fabiensanglard.net/gebbdoom/

  • 1
  • 0
Lars Hansen

Så spørgsmålet er, hvor stor Carmarcks præstation egentlig var, når det kommer til stykket.

Det kan jeg heller ikke sige, men der var intet andet som Doom da det kom.

Jeg kan huske mine venner der spillede det, havde henholdsvis en 386DX 40MHz, som på din video der, og en anden har haft en 486er vidst nok en DX2 66MHz hvorpå det kørte OK. Jeg mener ham med 386eren satte detail level ned (der var vidst 3 settings man kunne vælge imellem instantly) og gjorde vinduet en tak mindre, så kørte det OK efter tidens standard for hvad der var "flydende" - ham med 486eren tænkte det kørte perfekt. Tidens standard for hvornår noget er flydende, var meget lavere, end hvad vi anvender til at beskrive begrebet idag. Jeg hørte ingen snakke om de 60Hz på monitoren som en begrænsning i noget spil f.eks - i det hele taget blev ting mere gjort op i, om de hakkede eller ej, og ikke så meget frames/s.

Selv var jeg ludfattig og lige ved at være færdig med folkeskolen, hvor jeg fik min anden PC - en Pentium 60Mhz. Den maskine, kunne køre det noget mere glidende end de andre, men vi var ikke bevidste om forskellen imellem en 486er 66MHz og Pentiumen før vi spillede multiplayer over coax i computerklubben. Her havde jeg åbenbart en fordel over de andre, da det viste sig, at jeg blev dårligere når jeg fik en langsommere maskine (vi skiftede rundt). Vi nåede frem til, at selvom det så ud til at køre "flydende" på de andre maskiner, var det bare, mere flydende på min, og det var en fordel for reaktionstiden.

Dengang var jeg lidt med i det første 3D First Person Shooter esport i Danmark, hvor der blev afholdt DM i Doom (det var før der var Quake, så vidt jeg husker). Det var Fona der stod bag, så lidt gik vi op i det, men levetiden i spil var, selv for Doom, kort dengang. Det var elementære ting, som f.eks. om et keyboard virkede med både arrow up og right trykket ned der var afgørende + hurtig nok CPU. Jeg oplevede kun 1 der spillede med mus, og det virkede som en underlig ting at gøre dengang, man kunne jo ikke sigte op og ned da der her var auto aim.

Long story short. Indtil Quake kom, var det Doom og spil baseret på den engine, der satte niveauet som mange andre byggede på Heretic, Duke Nukem, Heretic etc.

På mig, som bruger dengang, virkede det som et kvantespring fra Wolfenstein 3D, som også havde været voldsomt imponerende. Subjektivt ud for det, vil jeg tillade mig, at kalde det en stor præstation - om kode magien i det, også var det, er jeg ikke kompetent til at sige - men ingen andre leverede noget der kunne matche det på det tidspunkt - og der havde spil branchen dog alligevel nogle år på bagen. Så jeg var imponeret :-)

  • 1
  • 0
Baldur Norddahl

Som ung gymnasieelev sad jeg på værelset og kodede en simpel Wolfenstein render engine i maskinkode. Jeg hævder ikke at have opfundet noget, os brødre syntes bare det var sjovt at lave en Wolfenstein editor.

Floating point var alt for langsomt, så vi brugte i stedet fixed point beregninger. Husker ikke helt om det var 16 eller 32 bit. Men principet er at du splitter eksempelvis dit 16 bit register i to dele, en del til fraktion og en den anden til heltal.

I 8086 maskinkode kan du referere til et 16 bit register som AX og også til det samme register som to 8 bit registre kaldet AH og AL. Hvis du skal trace en linje hvor 1 pixel på skærmen svarer til 1,5 pixel fra et bitmap, så kan du indlæse 1 i AH og 128 i AL. Det repræsenterer så værdien 1,5. For hver gang du går en pixel frem lægger du så AX til din counter, der kunne være i CX, men bruger kun CH, altså de øverste 8 bit, til at beregne adressen hvorfra du henter dine pixels.

Wolfenstein er begrænset således at det kun er lodrette streger der skal skaleres fra bitmaps. Du kan ikke "tilte" dit view på nogen måde, hvilket gør det meget enkelt at render. Det hele var baseret på lodrette streger, således at du for hver x værdi finder den væg der er tættes på og så render præcis én lodret streg.

Doom løsner op for noget af det, men det er først ved Quake at du har fuld frihed.

  • 0
  • 0
Peter Hansen

386'eren i videoen er en 386DX, dvs. med FPU


Nu har jeg selv ejet en 386dx/40, så jeg tror, jeg ved, hvad jeg taler om.

Til din orientering, så havde 386DX'ere ikke indbygget FPU. Det var først med 486'eren, at indbygget FPU blev standard.

Forskellen mellem 386DX og 386SX var hhv. 32- og 16-bit interface til databussen.

Nothing to do with Floating-Point

In the i386 family, the DX vs SX suffixes had nothing to do with the presence or absence of floating-point support - neither chip had it built-in. If you wanted floating-point hardware, you had to install a coprocessor, assuming your motherboard supported it. The 80387DX coprocessor was compatible with the i386DX, and the 80387SX coprocessor was compatible with the i386SX.

The coprocessor differences between DX and SX showed up on the i486 family of CPUs.

When the i486DX was introduced in 1989, it included floating-point support on-chip, and didn’t require a coprocessor.

Then, in 1991, the lower-cost i486SX was introduced without a coprocessor, requiring the addition of a 487SX coprocessor to add floating-point support.

https://www.quora.com/What-is-the-real-difference-between-a-386DX-and-a-...

  • 0
  • 0
Sune Marcher

Fabien Sanglard har skrevet to ret fantastiske bøger, Game Engine Black Book om hhv. Wolfenstein 3D og DOOM. Jeg mener at han arbejder på en om Quake.


Det er et par rigtigt gode bøger, som varmt kan anbefales!

Det er et ret imponerende stykke reverse engineering.


Source koden til begge engines er tilgængeligt, så jeg vil ikke kalde hans arbejde for reverse engineering. Det er nærmere ovre i noget arkæologi – hvor han finder de interessante dele af koden frem... og derudover tilføjer historisk perspektivering :-)

Hvis man er vokset om med Doom, er Masters of Doom også klart værd at læse. Den er i langt højere grad fokuseret på historien, menneskerne, begivenhederne... det er noget af en historie id Software har!

  • 0
  • 0
Log ind eller Opret konto for at kommentere