Trükkös számítások a háromdimenziós térben
A Quake 3 világában minden mozog, forog, változik – ehhez pedig rengeteg matematikára van szükség: vektorok segítségével mérik fel a tárgyak, játékosok, golyók helyzetét és irányát. Ezeket a vektorokat gyakran normalizálni kell, vagyis ugyanakkora hosszúságúra kell hozni, amit az úgynevezett normalizálás tesz lehetővé. Ez alatt azt kell érteni, hogy minden vektor hosszát 1-re változtatják. Ehhez viszont ki kell számolni az inverz négyzetgyököt, azaz 1-et kell osztani a négyzetgyökkel.
Ez elsőre nem tűnik nehéznek, de amikor erre másodpercenként akár több ezerszer is szükség van, egy lassú megoldás máris belassítja az egész játékot. Emiatt a fejlesztőknek muszáj volt hatékonyabb megoldást kitalálniuk a hagyományos eljárás helyett, amely túlzott processzorteljesítményt igényelt volna.
A „varázsszám”, ami átírta a matematikát
A Quake 3 programjában egy különösen furcsa megoldást használtak: egy rejtélyes, 0x5f3759df nevű számot. Ez a szám hexadecimális formában jelenik meg a kódban, de valójában egy 1 597 463 007-es decimális érték. Az algoritmus működése elképesztően egyszerű, mégis zseniális: először a kívánt szám számítógépes ábrázolását másképp értelmezik (gyakorlatilag a memóriában tárolt biteket egész számként kezelik), majd ezt az értéket megfelezik, és kivonják belőle a titokzatos varázsszámot. Ez egy becsült kiindulóértéket ad, amellyel a Newton–Raphson-módszer egyetlen lépése után már szinte tűpontos eredményt kapnak. Ennek a különös trükknek köszönhetően kevesebb számítási lépésre van szükség, emiatt a Quake 3 villámgyorsan tudta elvégezni ezt a műveletet – anélkül, hogy komoly kompromisszumokra kényszerült volna.
Honnan jön a kódban szereplő furcsa szám?
A közösség igazi legendát teremtett a varázsszámból, miután a Quake 3 kódja nyílt forráskóddá vált és mindenki számára elérhető lett. Sokan próbálták visszafejteni, miért éppen ezt a bizonyos számot használták a fejlesztők. 2003-ban Chris Lomont informatikus alaposan utánajárt a válasznak. Megvizsgálta, hogyan tudnánk a lehető legpontosabban (milliónyi esetre kiszámolva) eltalálni az inverz négyzetgyök közelítő értékét. Az ő számításai kicsit eltérő, de hasonlóan hatékony eredményt adtak.
Ez lényegében azt jelenti, hogy Lomont matematikailag optimalizálta ugyanezt a konstans értéket. Kiderült, hogy bár elméletben egy még picit pontosabb szám is található, a Quake 3-ban használt 0x5f3759df így is elképesztően hatékony. A maximális hiba mindössze 0,15%. A „mágikus” számot tehát valószínűleg nem egzakt matematikai levezetés, hanem sok-sok próbálkozás, tapasztalat, esetleg szerencse szülte.
Ki a rejtélyes algoritmus szerzője?
Egy internetes rajongó, Tom Forsyth még John Carmackhoz, a Quake 3 legendás vezető fejlesztőjéhez is eljutott, de ő sem tudta egészen biztosan megmondani, ki készítette ezt a kódrészletet. Több fejlesztőt is megszólaltattak, végül úgy tűnik, hogy egy Greg Walsh nevű programozó, aki még az 1980-as évek végén dolgozott hasonló algoritmusokon, indította útjára ezt a sajátos trükköt. Innen vándorolt tovább a Quake 3 kódjába, és többek – köztük Carmack – közreműködésével elterjedt a játékfejlesztők világában. Maga az algoritmus gyökere és a 0x5f3759df pontos eredete mindmáig rejtély.
A zseniális korszak öröksége
A Quake 3 inverz négyzetgyökös algoritmusa a számítástechnika egyik legendás szelete lett – nem véletlenül. Ez az apró, de ördögi részlet mutatja meg, mennyi kreativitás és lelemény kellett ahhoz, hogy a játékok igazán dinamikusak lehessenek szerény hardveren is. Ma, amikor szinte korlátlan számítási kapacitás áll rendelkezésre, már ritkábban bukkanunk hasonlóan trükkös, kézzel optimalizált megoldásokra. A Quake 3 varázsszámának titka viszont örök emlékeztető marad arra, milyen furfangokkal írtak hatékony szoftvert a digitális hőskorban.
