Величайшие программисты 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

Вероятно, тогда Джону было около десяти лет. В следующие годы он активно изучал программирование, играл в Ultima, но когда в возрасте 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 «возможным», а у него лично есть «ненулевой шанс внести свой вклад» в это чрезвычайно ценное изобретение. Исходя из таких условий, согласно логике Паскаля, он «обязан начать работу».