Lata 90. wymagały od twórców gier brutalnej wydajności. Ograniczona moc obliczeniowa oznaczała, że każda linia kodu musiała zostać zoptymalizowana pod kątem szybkości. Doskonałym przykładem jest strzelanka pierwszoosobowa Quake III Arena (Quake 3), wydana w 1999 roku, która pozostawiła niezatarty ślad w branży nie ze względu na swoją historię, ale ze względu na innowacyjny tryb wieloosobowy i zaskakująco elegancki kod.
Niewidzialna moc grafiki 3D
U podstaw Quake 3 leżała potrzeba renderowania świata 3D w czasie rzeczywistym. Wymagało to sprytnego podejścia do obliczeń grafiki 3D, z uwzględnieniem szczególnie trudnego problemu: obliczenia odwrotności pierwiastka kwadratowego. Obliczenie tego oznaczało podzielenie jedności przez pierwiastek kwadratowy z tej liczby, co nawet dzisiaj wymaga znacznej mocy obliczeniowej. Programiści Quake 3 szukali szybszego sposobu, a ich rozwiązanie pozostaje niesamowite.
Kod, który później został otwarty, ujawnił genialny algorytm, który do dziś fascynuje naukowców i programistów. Algorytm skutecznie określa orientację obiektów i znaków w przestrzeni 3D poprzez normalizację wektorów – matematycznych strzałek wskazujących kierunek. Obliczanie odwrotnego pierwiastka kwadratowego ma kluczowe znaczenie w tym procesie, a metoda Quake 3 ominęła tradycyjne wąskie gardła obliczeniowe.
„Magiczna liczba” i jej tajemnicze pochodzenie
Istota efektywności kryje się w tajemniczej liczbie 0x5f3759df, zwanej obecnie „liczbą magiczną”. Ta wartość szesnastkowa, odpowiadająca liczbie dziesiętnej 1 597 463 007, pozwala Quake 3 na przybliżenie odwrotności pierwiastka kwadratowego w zaledwie jednym kroku optymalizacji. Zwykle algorytmy takie jak metoda Newtona-Raphsona wymagają czterech do pięciu iteracji, aby osiągnąć wiarygodny wynik. Magiczna liczba Quake 3 ogranicza to do jednej iteracji.
Pochodzenie tej liczby było długo dyskutowane. Informatyk Chris Laumont opublikował w 2003 roku artykuł techniczny, w którym próbował przeprowadzić inżynierię wsteczną. Lomont stwierdził, że stała po podstawieniu do metody Newtona-Raphsona daje błąd nie większy niż 0,175%. Jego własne obliczenia wykazały nawet nieco bardziej efektywną wartość, ale pierwotna stała nadal działała dobrze.
Wyszukaj nieznanego autora
Tajemnica pogłębiła się, gdy społeczności internetowe rozpoczęły nieustanne poszukiwania programisty, który wymyślił magiczną liczbę. John Carmack, główny twórca Quake 3, nie był w stanie z całą pewnością zidentyfikować autora. Trop ostatecznie doprowadził do Grega Walsha, programisty w Ardent Computer pod koniec lat 80. XX wieku, który być może wprowadził tę stałą do wcześniejszego algorytmu. Jednak dokładna ścieżka od dzieła Walsha do Quake 3 pozostaje niejasna.
Dziedzictwo inteligentnej optymalizacji
Historia odwrotnego pierwiastka kwadratowego w Quake 3 jest świadectwem pomysłowości wczesnych twórców gier. Optymalizacja zrodziła się z konieczności wynikającej z ograniczeń sprzętowych lat 90-tych. Dziś, przy znacznie większych możliwościach obliczeniowych, tak ekstremalna wydajność jest mniej krytyczna. Ale ta historia służy jako przypomnienie, że eleganckie rozwiązania mogą wyłonić się z ograniczeń i że czasami najbardziej znaczące innowacje są ukryte w pozornie przyziemnym kodzie.
Wydajność algorytmu Quake 3 to nie tylko notatka historyczna; pokazuje zaangażowanie w optymalizację, która zdefiniowała epokę. Próba zrozumienia jej magicznej liczby pokazuje, jak nawet najmniejsze szczegóły mogą pozostawić trwały ślad w świecie informatyki.
