Величайшие программисты 21 века. Джон-Движок Кармак
Джон Кармак вместе с тёзкой Джоном Ромеро стали родоначальниками игрового жанра FPS. На слабеньких 486SX, без видеокарт (!) они выдали настоящий 3D-шутер без лагов с эффектом присутствия, что стало бомбой для 1993 года — в эпоху пошаговых стратегий и отсутствия скроллинга. Казалось, тут вмешалась чёрная магия…
В принципе, примерно так и есть. В разработке Wolfenstein 3D, Doom и движка Quake Джон Кармак действительно использовал кучу нестандартных приёмов вроде конверсии указателей или выхода за границы объектов, чтобы в циклах получать доступ к другому объекту, который гарантировано идёт следом.
Уровень программирования Doom и Quake до сих пор считается непревзойдённым образцом хакерских оптимизаций, а сам Джон Кармак — эталон сверхэффективного разработчика. Благодаря высочайшему качеству программирования Doom стал феноменом, который изменил мир.
▍ Проекты
Чтобы понять уровень легендарности Джона Кармака, достаточно взглянуть на список его разработок, который включает в себя 41 игру, изданную с 1990 по 2012 годы. Некоторые экземпляры:
- Slordax, 1990 год, первая реализация сайд-скроллинга в играх на PC,
- 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 CARMAK"
20 GOTO 10
Вероятно, тогда Джону было около десяти лет. В следующие годы он активно изучал программирование, играл в Ulima, но когда в возрасте 15 лет прочитал книгу Стивена Леви «Хакеры. Герои компьютерной революции», судьба подростка была решена. В книге рассказывалось о вундеркиндах, изменивших мир, и их культуре: экспериментах с мейнфреймами в MIT, самодельных программах, независимых компаниях по разработке игр. Отчисленный из Гарварда Билл Гейтс (автор интерпретатора бейсика для Altair), два Стива, Джобс и Возняк, создатели Apple II и большие любители компьютерных игр. Все они были хакерами, как многие другие. И все любили игры. Юный Джонди думал только о том, как попасть в их ряды, и даже год, проведённый в колонии для трудных подростков, не изменил его мнения.
Больше всего ему нравилось программировать графику, в том числе 3D-модели. Результат сразу был виден на экране. Первая игра Кармака называлась Shadowforge и очень походила на Ultima, хотя содержала несколько дополнительных фишек: например, персонаж мог атаковать не в четырёх направлениях, а в восьми. Джон заработал тысячу долларов, продав игру частной компании. Затем продолжал работать как фрилансер, продавая свои игры разным издателям, а в конце концов согласился принять предложение на работу от Softdisk. Так началась его игровая карьера как профессионального разработчика.
Работая в Softdisk, 19-летний Кармак придумал способ реализовать скроллинг на PC. Это было настолько прорывной и впечатляющей идеей, что коллега по имени Джон Ромеро уговорил вундеркинда забрать из старой фирмы рабочие компьютеры и основать свою компанию, которую они назвали id Software.
id Software, начало 90-х
На КДПВ в начале статьи — рабочий компьютер Кармака в 1995 году. В качестве монитора используется 28» модель Silicon Graphics/Integraph InterView 28hd96 весом 45 кг. Это был один из первых на рынке мониторов с разрешением 1920×1080. В предыдущие годы ему приходилось работать на двух мониторах меньшего размера. К 2011 году рабочее место проапгрейдилось до двух 30-дюймовых мониторов.
▍ Профессиональные хаки
Некоторые профессиональные приёмы Джона Кармака упоминаются в биографических книгах, в статьях и интервью с ним.
Например, Дэвид Кушнер в книге «Повелители Doom» (2003) упоминает о создании 3D-рендерера для Doom. Джон Кармак сразу понял, что написанный им рендерер тормозит при открытии некоторых уровней. И проблема фундаментальная. Поэтому он начал читать научные работы по компьютерным наукам, чтобы найти подходящее решение для оптимизации рендерера и повышения производительности. В итоге он применил технику под названием двоичное разбиение пространства, которая никогда раньше не применялась в видеоиграх, что значительно ускорило работу движка Doom.
Техника двоичного разбиения пространства (или BSP-дерева) — решение задачи отрисовки 3D-сцены. Её иногда называют определением видимой поверхности (visible surface detection, VSD).
VSD и выбраковка (отбрасывание невидимых полигонов) — сложнейшая задача, для решения которой в 90-е годы применялись десятки походов, а вычислительная сложность задачи нарастает как кубическая функция, что очень быстро становится ограничивающим фактором для рендеринга реалистичных миров.
Вкратце техника BSP-дерева описана здесь. Если в двух словах, в Wolfenstein был реализован примитивный рендерер по ограниченной сцене (стены только в двух направлениях, один уровень по высоте, никаких лестниц, тайлы по сетке через фиксированные промежутки), а для Doom пришлось написать принципиально новый рендерер, ориентированный на объекты. Он перебирает объекты в сцене и проецирует каждый из них на экран по очереди.
Джон Ромеро в книге «Doom: Scarydarkfast» (2013) вспоминает, что дизайн уровней в Doom с самого начала был на порядок сложнее, чем в Wolfenstein 3D:
«Три основных компонента дизайна DOOM — три трамплина, позволивших оторваться от Wolfenstein 3D, — уже присутствовали в первой альфе: изменяемое окружение, динамическое освещение и сквозные сектора. Согласно примечаниям к релизу, движущиеся сектора (поднимающиеся и опускающиеся платформы) уже были добавлены на уровни, но пока не функционировали. Наверное, можно сказать, что на данном этапе команда только училась с ними работать. На первом уровне присутствовал расширенный набор спиральных туннелеобразных лестниц, ведущих на выступ с видом на другую комнату, полную импов. Это был ранний вариант соединения секторов, ставший фирменным дизайнерским элементом (на рис. внизу). В конце концов эта карта превратилась в E2M7, хотя изначально полировалась для усиления эффекта масштабности ангара из начала E1M1».
Изначально Кармак пытался решить эту проблему, опираясь на схему уровней (такой подход через три года был реализован в игре Duke Nukem), но в 1993 году процессоры не тянули такой алгоритм, особенно когда сектора были вложены друг в друга, как в круговой лестнице.
Поэтому Кармак начал искать лучший алгоритм. Так он и нашёл алгоритм разбиения двоичного пространства, впервые описанный в научной статье для создания авиасимуляторов ВВС США в 1969 году (R. Schumacher, B. Brand, M. Gilliland, W. Sharp, «Study for Applying Computer-Generated Images to Visual Simulation», Air Force Human Resources Laboratory, December 1969).
В качестве потенциального решения предлагалась так называемая «матрицу приоритетов»:
Матрица показывает отношения между тремя объектами на основе трёх разделяющих плоскостей и расположения точки обзора камеры — если объект 
заслоняет объект 
, тогда запись 
в матрице будет равна 
.
Исследователи предложили реализовать матрицу аппаратно и пересчитывать каждый кадр. Основной недостаток заключается в том, что для представления сцены с 
объектов требуется матрица размером 
. Поэтому исследователи переходят к изучению вопроса о том, возможно ли представить матрицу окклюзии в виде «списка приоритетов» и использовать плоскости разбиения для упорядочивания объектов в сцене для рендеринга.
Только в 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, представляющего простую двумерную сцену. В трёхмерной сцене геометрия сложнее, но идея та же самая:
Первый шаг. Основная линия вдоль стены D разбивает сцену на два множества
Второй шаг. Полупространства по обе стороны D снова разделяются. Стена C — единственная в своём полупространстве, поэтому разбиение не требуется. Стена B образует новую разделительную линию в своём полупространстве. Стену A нужно разбить, потому что она пересекает линию раздела
Третий шаг. Упорядочение стен по отношению к точке обзора в правом верхнем углу, необходимое для алгоритма окраски пикселей. Здесь просто последовательный обход дерева
Замечательная особенность дерева BSP состоит в том, что его достаточно построить один раз, а затем одно и то же дерево BSP можно использовать для рендеринга сцены независимо от того, где находится точка зрения камеры, пока полигоны не перемещаются. Вот почему дерево BSP так полезно для рендеринга в реальном времени — вся тяжёлая работа по построению дерева выполняется заранее, а не во время рендеринга.
Вершина (1), лайндеф (2), сайддеф (3) и часть висплана (4) в DOOM на уровне E1M1, из книги «Doom: Scarydarkfast»
Брюс Нейлор, один из авторов статьи 1980 года, позже напишет об этой проблеме в своей работе 1993 года «Constructing Good Partitioning Trees». По словам Джона Ромеро, возможно, Джон Кармак узнал о BSP-деревьях именно из этой статьи — по крайней мере, он её читал. И затем уже генератор BSP-деревьев был добавлен конкретно в редактор уровней Doom.
Уровень E1M7 «Вычислительный центр». Игрок начинает в точке A и движется мимо точки B к точке C, после чего возвращается и получает доступ к точке D. Там он получает ключ-карточку для открытия точки E и наконец добирается до выхода в точке F. Из книги «Doom: Scarydarkfast»
Джон Кармак не только оценил мощь идеи, но и нашёл способ реализовать BSP-деревья в реальном времени на процессорах, которые даже не могли выполнять операции с плавающей точкой. Это было значительное достижение. И это не единственный хак. О других виртуозных приёмах можно прочитать в «Чёрной книге движка Doom» Фабьена Сангларда.
Некоторые специалисты считают, что именно эпизод с двоичным разбиением пространства — самый лучший наглядный пример того, почему Кармак стал такой легендарной личностью в программировании.
▍ Иммунитет от выгорания?
Хотя Джон какое-то время занимался дзюдо и бразильским джиу-джитсу, его жизнь не совсем соответствует модному ныне принципу «work-life balance». Как он сам говорил, «баланс переоценивают». Бывшая жена Кармака жаловалась, что он взял рабочий компьютер в свадебное путешествие и вообще постоянно «как будто отсутствовал». В вышеупомянутом подкасте Джон сказал, что если спать восемь часов в сутки, то можно работать сто часов в неделю, «правильно расставив приоритеты». Он также отметил, что «если продолжать работать, преодолевая убывающую эффективность, можно добиться большего, чем если остановиться на этом этапе».
Но когда программирование — это страсть, которая охватывает тебя целиком, то что может быть лучше?
Правда, Кармак отметил один важный момент: он всегда был крайне уравновешенным и никогда не испытывал проблем с эмоциональной нестабильностью. Когда мальчика отправляли в колонию, следователь отметил полное отсутствие у него эмпатии («какой-то мозг на ножках»). Похоже, Джон от природы лучшие приспособлен для изматывающей интеллектуальной работы, чем большинство людей в этом мире. По этому поводу фрагмент из книги «Повелители Doom» о возрасте примерно 20–25 лет, за этот период он создал примерно два десятка игр:
Кармак был человеком момента. Его сильной стороной была сосредоточенность. Время существовало для него не в виде какого-то многообещающего будущего или сентиментального прошлого, а в виде настоящего, которое состояло из хитросплетений задач, решений, воображения и кода. Он не хранил ничего, что напоминало бы ему о прошлом, — ни фотографий, ни записей, ни игр, ни компьютерных дискет. Он даже не сохранил копий своих первых игр, Wraith и Shadowforge. У него не было ни школьного альбома, ни журналов с его первыми публикациями. Он не хранил ничего — только то, что могло понадобиться ему здесь и сейчас. В спальне Кармака не было лишних вещей, только лампа, подушка, покрывало и стопка книг. Не было даже матраса. Из дома он забрал только кошку по кличке Митси (подарок от новой семьи), крайне мерзопакостную и готовую обоссать что угодно и когда угодно…Кармак часто говорил ребятам, что его волнуют только работа над программами и деньги на пиццу и диетическую колу, чтобы не помереть от голода и жажды. Ему не интересно было управлять большой компанией. Чем больше становилось деловых обязанностей вроде отправки заказов и маркетинга, тем сильнее они отвлекались от создания отличных игр.
Возможно, заодно с эмоциональной стабильностью Джону достался иммунитет от выгорания?
Рабочий десктоп Кармака на октябрь 2022 года: Titan RTX, 4090 и A100
В 2000-е годы Кармак увлёкся конструированием ракет (Armadillo Aerospace, на фото он на ракетном фестивале X-Prize Cup 2005) и шлемов виртуальной реальности (Oculus Rift). А сейчас применяет свои способности для решения более интересной задачи — создания сильного ИИ (Keen Technologies).
Аргументация такого решения простая и логичная. Джон Кармак считает появление AGI «возможным», а у него лично есть «ненулевой шанс внести свой вклад» в это чрезвычайно ценное изобретение. Исходя из таких условий, согласно логике Паскаля, он «обязан начать работу».
