Най-добрите програмисти на века: Джон Кармак и неговите геймърски енджини

Джон Кармак, заедно със своя съименник Джон Ромеро, са пионерите в жанра на FPS игрите. На слаб компютър с процесор 486SX, без графични карти (!), те създадоха 3D шутър без лагове и с ефект на присъствие, който през 1993 г., в ерата на походовата стратегия и липсата на скролване, се превърна в истинска бомба. Изглежда, че тук се е намесила някаква черна магия…

По принцип това наистина е така. При разработването на Wolfenstein 3D, Doom и енджина на Quake Джон Кармак наистина използва куп неконвенционални трикове като преобразуване на указателите и излизане извън границите на обектите, за да може в циклите да получи достъп до друг обект, който със сигурност следва първия.

Нивото на програмиране на Doom и Quake и до днес се счита за най-съвършения модел на хакерска оптимизация, а самият Джон Кармак е еталон за свръхефективен разработчик. Благодарение на отличното качество на програмирането Doom се превърна във феномен, който промени света.

Проектите

За да разберем нивото на легендарност на Джон Кармак, е достатъчно да погледнем списъка му с разработки, който включва 41 игри, публикувани между 1990 и 2012 г.

Ето няколко примера:

• Slordax, 1990 г., първото прилагане на side-scrolling (странично превъртане) в компютърните игри
• Wolfenstein 3D, 1992 г., мапинг на текстури
• Doom, 1993 г., BSP дървета (за това по-долу), отказ от музиката в полза на околния игрови шум (идея на Кармак)
• Doom II, 1994 г
• Heretic, 1994 г
• Hexen: Beyond Heretic, 1995 г
• Quake, 1996 г
• Quake II, 1997 г
• Quake III Arena, 1999 г
• Принос в редица проекти с отворен код, включително първия порт на X Window System на Mac OS X Server и проекта Utah GLX за финализиране на OpenGL драйверите за Linux.

В следващите игри (след 1999 г.) той вече не работи като водещ програмист, а като технически директор.

Всъщност той разработва игровия енджин почти еднолично, докато останалите служители се концентрират върху дизайна, нивата и другите игрови механики. През 2014 г. е публикуван сорс кодът на ранните игри Hovertank 3D и Commander Keen. Първите игри са написани на Borland Turbo Pascal и Borland C++ 2.0. Изходният код на Wolfenstein 3D е открит през 1995 г., а на Doom – през 1997 г.

Заради репутацията си на запален техничар в id Sofware Кармак е наричан Джон-Енджина. И наистина той на практика съвсем самостоятелно разработва игровите енджини, докато останалите програмисти се занимават с дизайна, нивата и други подобни.

Когато става дума за разработването на игри, то в жанра на шутерите Джон Кармак не е просто легенда, а по-скоро Бог.

Детството пред компютъра

Джон Кармак е роден на 20-ти август 1970 г. и започва да се интересува от компютърни игри още в ранна възраст. В подкаст с Лекс Фридман на 4-ти август 2022 г. той си спомня, че с часове е седял пред монитора. В училище един учител му показва Apple II и момчето моментално се влюбва в него. Компютърът бил нещо вълшебно, което изпълнявало команди точно както са написани. Тогава е нямало интернет; отначало малкият Джонди (Джон Д. Кармак Втори) отишъл в библиотеката, потърсил няколко книги за програмиране и се е учил от тях.

Първата си програма пише в компютърен магазин, където намира работещ модел и въвежда следното:

10 PRINT "JOHN CARMACK"
20 GOTO 10

По онова време Джон вероятно е бил на около десет години. През следващите години той активно изучава програмиране и играе Ultima, но когато на 15-годишна възраст прочита книгата на Стивън Леви „Хакери. Героите на компютърната революция„, съдбата на тийнейджъра е предрешена. В книгата се говори за вундеркинди, които са променили света и културата си: експерименти с мейнфреймове в MIT, самоделен софтуер, независими компании за разработка на игри. Отпадналият от Харвард Бил Гейтс (автор на интерпретатора на BASIC за Altair), двамата Стиви – Джобс и Возняк – създателите на Apple II и големи фенове на компютърните игри. Всички те са били хакери, както и още много други. И всички обичат игрите. Младият Джонди мислел единствено как да се присъедини към техните редици и дори едната година, прекарана в затвор за непълнолетни, не променила решението му.

Най-много му харесва да програмира графика, включително 3D модели. Резултатът веднага се вижда на екрана. Първата игра на Кармак се нарича Shadowforge и е много подобна на Ultima, въпреки че съдържа няколко допълнителни функции: например героят може да атакува в осем посоки вместо в четири. Джон печели хиляда долара, като продава играта на частна компания. След това продължава да работи на свободна практика, като продава игрите си на най-различни издатели, преди накрая да приеме предложение за работа от Softdisk. Така започва кариерата му на професионален разработчик на игри.

Докато работи в Softdisk, 19-годишният Кармак измисля начин за прилагане на скролиране в компютрите. Това е толкова пробивна и впечатляваща идея, че неговият колега Джон Ромеро убеждава вундеркинда да вземе работните компютри от старата си компания и да създаде своя собствена компания, която те наричат id Software.

На изображението по-горе се вижда работният компютър на Кармак. Използваният монитор е 28-инчов Silicon Graphics/Integraph InterView 28hd96 с тегло 45 kg. Това е един от първите монитори на пазара с разделителна способност 1920×1080 пиксела. През предишните години му се е налагало да работи с два по-малки монитора. Към 2011 г. работната станция е обновена до два 30-инчови монитора.

Професионалистът

Някои от професионалните техники на Джон Кармак се споменават в биографичните книги, статиите и интервютата с него.

Така например Дейвид Кушнер в Lords of Doom (Повелителите на Doom, 2003 г.) споменава за създаването на 3D рендера за Doom. Джон Кармак веднага разбира, че рендерът, който е написал, се забавя при отварянето на някои нива. И че проблемът е фундаментален. Затова той започва да чете статии по компютърни науки, за да намери най-подходящото решение за оптимизиране на рендера и подобряване на производителността. В крайна сметка той прилага техника, наречена двоично разделяне на пространството (binary space partitioning), която никога дотогава не е използвана във видеоигрите и която значително ускорява енджина на Doom.

Техниката за двоично разделяне на пространството или BSP-tree е решението на проблема с визуализирането на 3D сцена. Понякога се нарича определяне на видимата повърхност (VSD).

VSD и изчистването (отстраняването на невидимите полигони) е трудна задача, за която през 90-те години са използвани десетки подходи, а изчислителната сложност на проблема се увеличава като кубична функция, което много бързо се превръща в ограничаващ фактор за визуализирането на реалистични светове.

Накратко, Wolfenstein разполага с примитивен рендер за ограничена сцена (стени само в две посоки, едно ниво на височина, никакви стълби, плочки върху стена на фиксирани интервали), докато за Doom е трябвало да напише изцяло нов рендер, ориентиран към обекти. Той обхожда обектите в сцената и последователно проектира всеки от тях върху екрана.

Джон Ромеро в книгата си Doom: Scarydarkfast (2013 г.) си спомня, че дизайнът на нивата в Doom от самото начало е бил над десет пъти по-сложен, отколкото във Wolfenstein 3D:

„Трите основни компонента на дизайна на DOOM, трите опорни точки, които дадоха възможност да се откъснем от Wolfenstein 3D, присъстваха още в първата алфа версия: променяща се среда, динамично осветление и проходни сектори. Според бележките към първото издание на играта движещите се сектори (издигащите се и падащи платформи) вече са добавени към нивата, но все още не са функционални. Предполагам, че може да се каже, че на този етап екипът просто се е учил да работи с тях. Първото ниво включваше разширен набор от спираловидни стълби, подобни на тунели, които водеха до перваз с изглед към друга стая, пълна с импове. Това бе ранна версия на свързващите сектори, които се превърнаха в характерен елемент на дизайна (на изображението по-горе). Тази карта в крайна сметка се превърна в E2M7, въпреки че първоначално бе ошлайфана, за да се подобри ефектът на мащабиране на хангара от началото на E1M1“.

Първоначално Кармак се опитва да реши този проблем, като използва схема на нивата (такъв подход е приложен три години по-късно в играта Duke Nukem), но през 1993 г. процесорите не могат да се справят с такъв алгоритъм, особено когато секторите са вложени един в друг, като например в кръгова стълба.

Като потенциално решение е предложена така наречената „матрица на приоритетите“:

Матрицата показва връзката между трите обекта въз основа на трите разделителни равнини и местоположението на гледната точка на камерата – ако обектът a(i) закрива обекта a(j), тогава записът a(ij) в матрицата ще бъде  равен на 1.

Изследователите предлагат матрицата да се реализира хардуерно и да се преизчислява на всеки кадър. Основният недостатък е, че представянето на сцена с n обекта изисква матрица с размер n². Затова изследователите проучват дали е възможно матрицата да се представи като „списък с приоритети“ и да се използват разделителни плоскости, за могат правилно да се подредят обектите в сцената за рендиране.

Едва през 1980 г. в статия, озаглавена „За генерирането на видими повърхности чрез априорни дървовидни структури“ е показан конкретния алгоритъм за постигането на тази цел. (Henry Fuchs, Zvi Kedem, Bruce Naylor, «On Visible Surface Generation By A Priori Tree Structures», ACM SIGGRAPH Computer Graphics, July 1980).

В тази статия за първи път е ясно представено BSP дърво (с препратка към идеята от 1969 г.). Конструираното BSP дърво може лесно да се използва за осигуряване на приоритетно подреждане на обектите в дадена сцена. По-долу е представена примерна схема за построяване и обхождане на BSP дърво, представящо елементарна двуизмерна сцена. При триизмерна сцена геометрията е по-сложна, но идеята е същата:

Хубавото на BSP дървото е, че то трябва да се изгради само веднъж и след това същото BSP дърво може да се използва за визуализиране на сцената, независимо от това къде се намира гледната точка на камерата, стига полигоните да не са преместени. Ето защо BSP дървото е толкова полезно за рендирането в реално време – цялата трудна работа по изграждането на дървото се извършва предварително, а не по време на рендирането.

Край на първа част. Джон Кармак е толкова гениален, че не може да се събере в една единствена статия. Във втората част ще продължим с редактора на нивата на Doom и с другите идеи на  един от най-добрите програмисти на нашия век.