December 21st, 2013

moose, transparent

дела давно минувших лет (компьютерное)

Кажется, я никогда не записывал здесь подробной истории того, как я писал движок для игры, подобной Wolfenstein 3D. Я читаю сейчас книгу об истории id Software и ее создателей (о книге напишу отдельно), и то и дело вспоминаю эту старую историю. Заодно понял, что многие подробности уже забыл, так что лучше записать, что еще помню.

Игра Wolfenstein 3D появилась весной 92 года. Тем, кто помоложе, придется поверить мне на слово: это была сенсация, потрясшая весь мир компьютерных игр. Очень трудно было поверить, даже глядя прямо на экран, что PC-шки того времени действительно могли так быстро показывать от первого лица движение в трехмерном мире (пусть даже он был лишь условно трехмерным: высота объектов и перспективы не менялась). Ничего подобного никто до этого не видел.



Осенью 93 года я начал учиться на первом курсе факультета компьютерных наук хайфского Техниона. Мне было 17 лет. У меня к тому времени было немало опыта работы с графикой в ассемблере и оптимизации графических алгоритмов и вообще ассемблерного кода. Из языков высшего уровня я все еще предпочитал Турбо Паскаль, хотя уже знал C.

Видимо, в сентябре или октябре - точно вспомнить не могу - параллельно с началом учебы я начал работать над попыткой создания трехмерного движка, равного по возможностям Wolfenstein 3D. Я познакомился через каких-то друзей с владельцами компьютерного магазина в Хайфе, у которых простаивал без использования компьютер с новым и быстрым процессором со странным названием "Пентиум". Он был заметно быстрее моего домашнего компьютера с 486DX-2, к которому у меня в любом случае был доступ только на выходных, он остался дома в Ришон ле-Ционе. Мне хотелось посмотреть, на что способен Пентиум; я договорился с хозяевами магазина, что буду сидеть за ним в свободное время и писать свой движок, а если он когда-то превратится в настоящую игру, то они ее смогут продавать или что-то в этом роде. Не помню подробностей соглашения, которое в любом случае было устным и неформальным. По правде сказать, я не думал о своей работе, как о создании движка, и у меня не было серьезных намерений написать свою игру. Например, я совершенно не умел рисовать текстуры или объекты, и не знал, где найти человека, который умеет, и не собирался его искать. Я хотел воссоздать магию Вульфенштейна - магию свободного хождения по трехмерному лабиринту, с разрисованными стенками и объектами вроде врагов или полезных предметов на земле. Я не понимал, как им удалось это сделать, и надеялся, что хотя бы на быстром Пентиуме я смогу повторить это достижение.

Я нашел небольшую статью на какой-то BBS, которая объясняла основные принципы ray-casting'а, и там был пример простого алгоритма, который вычисляет, какие стенки видит игрок, с помощью рей-кастинга. Алгоритм, кажется, был на C. Я разобрался с его смыслом, переписал его на Паскале, и добавил репрезентацию уровня и простое движение курсорными клавишами. После долгой отладки это заработало, но каждый фрейм рисовался несколько минут, можно было видеть на экране, как код медленно меняет одну вертикальную линию за другой.

Рей-кастинг работает по тому же принципу, по которому, как когда-то считалось, работает зрение. Древние греки думали, что из глаз выходят специальные лучи, долетают до предметов, отражаются от них и возвращаются обратно, и так мы видим (точнее, не все древние греки так думали, была и другая теория, согласно которой предметы излучают свои миниатюрные копии, и они доходят до глаз). При рей-кастинге программа следит за тем, где находится игрок на карте уровня, и куда смотрит, какое у него поле обзора. Это поле делится на 320 (например) вертикальных линий, и мы как бы запускаем из точки, в которой находится игрок, 320 гипотетических лучей по всем 320 направлениям, и смотрим, до какого объекта на карте долетает каждый луч. Если какой-то луч долетает, например, до стенки, то мы знаем, какая эта стенка, какая на ней должна быть нарисована текстура (картинка), и какая именно вертикальная линия из этой текстуры должна стоять в этом месте. И самое главное, зная расстояние, которое прошел луч, мы вычисляем, какой должен быть размер
этой линии на экране. Мы берем нужную линию из текстуры фиксированного размера (например, 64x64 пикселя), и увеличиваем ее или уменьшаем до нужного размера: если стенка далеко от игрока, ее линия может занимать 6 пикселей на экране, а если близко, то 100.

Это и есть основной принцип. Когда к стенкам добавляют объекты, возникают дополнительные сложности, потому что объект, например, враг, не занимает целиком квадрат на карте, как стенка. Он частично прозрачен: в зависимости от того, где в его квадрат попадает луч от игрока, нужно или рисовать его, или вести луч дальше. Или можно в любом случае довести луч до дальней стенки, в процессе собирая информацию об объектах на дороге, и отрисовать их поверх стенки. Можно по-разному к этому подходить. Но у меня еще и до объектов, с одними голыми стенками, все рисовалось очень медленно.

Я переписал основную функцию рендеринга на ассемблере, и это заработало намного быстрее, но все еще невыносимо медленно: на Пентиуме перерисовка экрана занимала несколько секунд. Я оптимизировал код на ассемблере, как мог, используя всякие хитрые трюки, но это все равно было намного, намного медленнее на Пентиуме, чем Wolfenstein 3D вообще даже на 386-м.

Это меня сильно озадачило. Где-то неделю я тыкался в разные места, пробовал то тут, то там что-то сократить и убыстрить, и ничего не получалось. Например, я переписал на ассемблере гораздо больший кусок кода, не только собственно перерисовку, а и весь главный цикл, но, как и ожидал, это ничего не дало. Мое мнение о всемогуществе создателей Вульфенштейна подтверждалось, но как-то все равно было обидно, и хотелось добиться большего.

Наконец в один из выходных я запустил Wolfenstein 3D на своем домашнем компьютере под отладчиком SoftICE (очень хороший был отладчик в эпоху DOS и раннего Windows). Мне хотелось попробовать понять, как же все-таки они делают перерисовку экрана, и на каком языке написан движок. После нескольких часов блужданий по машинному коду я нашел куски, которые выглядели как копирование данных текстуры на экран, с одновременным увеличиванием/уменьшением. Это были короткие куски кода, явно написанные на ассемблере (они использовали регистры не по стандартным конвенциям C или Паскаля). Я решил, что движок Вульфенштейна написан на чистом ассемблере, что меня не очень удивило. Но когда я попытался разобраться, как они оптимизировали копирование, чтобы оно было быстрым, меня удивило отсутствие условных прыжков. Похоже было на то, что одна такая функция копировала 64-пикселевую линию, например, ровно в 40 пикселей на экране, не больше и не меньше, а другая копировала в 42, и так далее. Поэтому каждой функции не надо было собственно подсчитывать, куда ставить какой пиксель из текстуры, каждая из них заранее знала свою работу, не проверяла ничего, не держала никаких счетчиков, а просто раскидывала пиксели туда-сюда. Но это ж адская была бы работа, подумал я, писать вручную на ассемблере отдельную функцию копирования текстуры для каждой возможной высоты на экране. И тут до меня дошло, что движок Вульфенштейна генерирует эти функции на машинном коде прямо во время работы программы.

Я позаимствовал эту идею оптимизации, но не сам код из Вульфенштайна - мне хотелось сделать это самому. Через несколько дней напряженной работы (в основном отладки, потому что ошибки в сгенерированном машинном коде часто означали, что нужно перезагрузить компьютер) у меня был готов код на Паскале, который в начале работы программы генерировал функции для копирования текстур во все возможные размеры. Во время отрисовки экрана эти функции вызывались через таблицу ссылок, проиндексированную размером линии на экране. Когда я запустил все это, скорость работы кода меня ошеломила. На Пентиуме движок работал так быстро, что мне пришлось добавить замедление движения - иначе при нажатой клавише движения вперед игрок летел с ненатуральной скоростью. На 486-м дома, и даже на 386-м процессоре, движение в текстурном лабиринте работало так же быстро и гладко, как в самом Вульфенштейне.

Затем я добавил ограничение движения - чтобы игрок не мог проходить сквозь стены (это легко), и поддержку объектов (вот это было тяжело, возился еще несколько недель, пока не заработало достаточно быстро). Сделал отдельный файл-демку, который позволял игроку бегать по простому лабиринту, и показал нескольким друзьям и знакомым. И... забросил все это.

А через несколько недель, в декабре 93-го согласно Википедии, появился Doom, в котором была (ограниченная, но все равно круто) поддержка высоты, а также освещение, меняющееся с размером. id Software не сидели на месте полтора года со времени выпуска Вульфенштейна, и опять поразили весь мир, добившись на первый взгляд невозможного. Я поразмышлял немного о том, как мой движок улучшать в эту сторону, но работать над этим не стал. Более интересно было проводить время в университете, знакомиться с другими студентами и студентками, а также общаться по IRC с людьми со всего мира.