дела давно минувших лет (компьютерное)
Dec. 21st, 2013 01:45 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaКажется, я никогда не записывал здесь подробной истории того, как я писал движок для игры, подобной 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 с людьми со всего мира.
Игра 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 с людьми со всего мира.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-12-21 12:06 pm (UTC)Помню пост id_aa_carmack про порт игр на мобильные телефоны, там была фраза типа: я не люблю мобильные телефоны и телефоны вообще потому что вся эта болтовня только отнимает драгоценное время.
no subject
Date: 2013-12-21 12:09 pm (UTC)I’m not a cell phone guy. I resisted getting one at all for years, and even now I rarely carry it. To a first approximation, I don’t really like talking to most people, so I don’t go out of my way to enable people to call me. However, a little while ago I misplaced the old phone I usually take to Armadillo, and my wife picked up a more modern one for me. It had a nice color screen and a bunch of bad java game demos on it. The bad java games did it.
http://armadilloaerospace.com/n.x/johnc/Recent%20Updates
второй пост сверху
no subject
Date: 2013-12-21 12:34 pm (UTC)no subject
Date: 2013-12-21 12:46 pm (UTC)no subject
Date: 2013-12-21 01:25 pm (UTC)Генерация кода
Date: 2013-12-21 01:02 pm (UTC)no subject
Date: 2013-12-21 01:20 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:Re: Генерация кода
From:Re: Генерация кода
From:Re: Генерация кода
From:no subject
Date: 2013-12-21 01:03 pm (UTC)no subject
Date: 2013-12-21 03:56 pm (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2013-12-21 01:12 pm (UTC)no subject
Date: 2013-12-21 01:15 pm (UTC)Как вы считаете, что может быть этим X?
no subject
Date: 2013-12-21 03:20 pm (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2013-12-21 01:25 pm (UTC)А еще был на 2Kb кода экзешник mars -- бродилка по случайным нагромождениям камней в 3d, но всего 2KB ассемблерного кода!
Все мы в юности писали игрушки. Мы с прияетелем написали аналог Dune 2, например, только лучше. Со скоростью проблем не было, там проще, и мы все напрямую в видеопамять писали, с переключением страниц, сейчас так не делают.
P.S. Ray casting по-русски переводится как "обратная трассировка луча", если я правильно понимаю.
no subject
Date: 2013-12-21 01:37 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2013-12-21 01:49 pm (UTC)no subject
Date: 2013-12-21 01:57 pm (UTC)no subject
Date: 2013-12-21 02:02 pm (UTC)Для примера погуглите 0x5f3759df - очень много пищи для размышлений.
no subject
Date: 2013-12-21 02:22 pm (UTC)Или же вы сначала делали полный честный raytracing слева-направо и сверху вниз, не догадавшись рисовать прореженными вертикальными линиями текстур?
no subject
Date: 2013-12-21 02:56 pm (UTC)И никакого ассемблера, только заранее рассчитанные тригонометрические таблицы, и все.
(no subject)
From:no subject
Date: 2013-12-21 03:33 pm (UTC)no subject
Date: 2013-12-21 03:38 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2013-12-21 03:47 pm (UTC)no subject
Date: 2013-12-21 04:05 pm (UTC)no subject
Date: 2013-12-21 08:00 pm (UTC)no subject
Date: 2013-12-21 05:49 pm (UTC)Мы тогда учились не то на первом, не то на втором курсе. Однажды он прочитал в какой-то заумной книжке про сигма-дельта-модуляцию. И написал программу, которая при помощи неё проигрывает на PC Speaker звуковые файлы. И стал всем показывать.
Ни на кого, в том числе на меня, она тогда впечатление не произвела. Всем нам тогда был известен метод воспроизведения звука на PC-Speaker при помощи особого режима таймера, основанный на широтно-импульсной модуляции, обычно на частоте 18 кГц, позволяющей оперировать 64 значениями ширины импульса.
А у него была частота дискретизации мегагерцы, что существенно повышало качество воспроизведения -- jн честно дёргал бит порта 0x61. Но попробуй заметить разницу на убогом PC Speaker, если не знаешь что искать. Тем более, из-за различных технических ограничений, всё это подглючивало и сралов звук специфическими артефактами, которые при обычном ШИМ можно было избежать.
Так и остался он тогда непонятый со своей сигма-дельтой.
no subject
Date: 2013-12-21 07:50 pm (UTC)no subject
Date: 2013-12-21 08:43 pm (UTC)no subject
Date: 2013-12-21 09:15 pm (UTC)Микрософт реализовала в GDI исполнение генерируемого налету кода в какиой-то из функций - что-то вроде "отрисовка объекта с побитовой операцией его с фоном".
А вообще, здесь могли быть разные варианты.
В x86 вроде изначально был префикс rep.
Плюс, самый извращённый вариант на ассемблере - сделать одну "дилнную" функцию со множеством точек входа.
no subject
Date: 2013-12-21 11:45 pm (UTC)no subject
Date: 2013-12-22 12:52 am (UTC)http://www.gamedev.net/topic/266373-so-i-finally-took-all-of-carmacks-quakecon-speech-and-put-it-to-text-format/
http://alenacpp.blogspot.de/2005/09/quakecon-2004.html
no subject
Date: 2013-12-22 06:56 pm (UTC)Вот это http://habrahabr.ru/post/170139/ я читал почти буквально с отпавшей челюстью.
no subject
Date: 2013-12-22 07:42 pm (UTC)no subject
Date: 2013-12-23 10:35 am (UTC)no subject
Date: 2013-12-23 10:43 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2013-12-23 03:44 pm (UTC)Интересно, как эти греки объясняли необходимость внешних источников света?
no subject
Date: 2013-12-24 11:17 am (UTC)(no subject)
From: