Рубрика «binary space partitioning»

Величайшие программисты 21 века. Джон-Движок Кармак - 1


Джон Кармак вместе с тёзкой Джоном Ромеро стали родоначальниками игрового жанра FPS. На слабеньких 486SX, без видеокарт (!) они выдали настоящий 3D-шутер без лагов с эффектом присутствия, что стало бомбой для 1993 года — в эпоху пошаговых стратегий и отсутствия скроллинга. Казалось, тут вмешалась чёрная магия…

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

Уровень программирования Doom и Quake до сих пор считается непревзойдённым образцом хакерских оптимизаций, а сам Джон Кармак — эталон сверхэффективного разработчика. Благодаря высочайшему качеству программирования Doom стал феноменом, который изменил мир.
Читать полностью »

Действительно ли использование BSP в Doom стало гениальным ходом? - 1

Вершина технологий того времени.

В 1993 году id Software выпустила шутер от первого лица Doom, который быстро превратился в феномен. Сегодня считается, что это одна из игр, оказавших самое большое влияние за всю историю.

Десять лет спустя после выпуска Doom, в 2003 году, журналист Дэвид Кушнер опубликовал книгу об id Software под названием Masters of Doom, которая с тех пор стала каноническим описанием процесса создания Doom. Я прочитал Masters of Doom несколько лет назад и почти ничего уже не помню, но одна история из книги о ведущем программисте Джоне Кармаке сохранилась в моей памяти. Моё описание будет не совсем точным (подробнее см. ниже), но если вкратце, то на раннем этапе разработки Doom Кармак осознал, что написанный им для игры 3D-рендерер при рендеринге отдельных уровней начинал тормозить. Это было неприемлемо, потому что Doom должен был стать активной и даже бешеной игрой. Осознав, что проблема рендерера была настолько фундаментальной, что ему придётся искать более оптимальный алгоритм рендеринга, Кармак начал читать исследовательские статьи. В результате он реализовал технику под названием «двоичное разбиение пространства» (binary space partitioning, BSP), которая раньше никогда не применялась в видеоиграх, и значительно ускорил таким образом движок Doom.

Эта история о том, как Кармак применил передовые научные исследования к видеоиграм, всегда впечатляла меня. По-моему, именно благодаря этому Кармак стал такой легендарной фигурой. Он заслуживает быть известным в качестве архетипичного гениального программиста видеоигр по множеству причин, но в качестве главной мне всегда вспоминается эпизод с чтением научных статей и двоичным разбиением пространства.
Читать полностью »

image

Программист Майкл Абраш, в середине 90-х приглашённый Джоном Кармаком для работы над движком первого Quake, написал в процессе разработки серию статей. Это вторая колонка из данной серии. Перевод первой находится здесь.

Должен признаться: меня достал классический рок. В последний раз я с радостью слушал что-нибудь из Cars или Boston довольно давно, около 20 лет назад. Кроме того, меня никогда особо не привлекали Боб Сигер и Queen, не говоря уже об Элвисе, так что здесь мало что изменилось. Но я понимал, что нечто изменилось, когда мне хотелось переключить радио, услышав Allman Brothers, или Steely Dan, или Pink Floyd, или, господи, прости, Beatles (но только на таких вещах, как «Hello Goodbye» и «I’ll Cry Instead», а не «Ticket to Ride» или «A Day in the Life»; я ещё не зашёл настолько далеко). Долго искать причины этого не пришлось; я слушал одни и те же песни четверть века, и просто от них устал.

Я рассказываю это всё таким образом потому, что когда мы с моей дочерью однажды вечером ехали из кафе, в машине впервые была включена радиостанция «Альтернативы нет».

Мы говорим о десятилетней девочке, росшей на постоянной диете из старых хитов. Ей нравятся мелодии, легко запоминающиеся песни и хорошие певцы. Ничего из этого не найдёшь, слушая станцию про альтернативный рок. Поэтому неудивительно, что когда я включил радио, она первым делом сказала «Фу!»

Но вот что меня удивило: послушав какое-то время, она сказала: «Знаешь, папа, а на это на самом деле интересно».

Это не только намекнуло мне о том, какая музыка будет грохотать по всему дому, когда она станет тинейджером. Её быстрое принятие альтернативного рока (по сравнению с моим длящимся десяток лет увлечением музыкой собственной юности) напомнило мне кое о чём, что легко забывается, когда становишься старше и образ жизни становится устоявшимся. Это напомнило мне, что необходимо сохранять открытость сознания и быть готовым — более того, стремиться — пробовать новые вещи.Читать полностью »

От переводчика: эта статья написана Дэвидом Кушнером в 2002 году, годом позже он издал известную книгу «Masters of Doom». Статья показалась мне интересной, потому что в ней есть подробности реализации технологий id, почему-то отсутствующие в книге.

За кулисами экшена и агрессии игр id скрыта революция в технологии настольных компьютеров

image
В течение последних 12 лет эволюция реализма графики Id Software поднимает планку для всей отрасли видеоигр. Среди игр-новаторов находятся [снизу вверх, справа налево] Commander Keen (1990) [прим. пер.: на самом деле на скриншоте Dangerous Dave in the Haunted Mansion], Hovertank (1991), Wolfenstein 3D (1992), Doom (1993), Quake (1996) [прим. пер.: на самом деле Quake II] и Return to Castle Wolfenstein (2001).

После полуночи начинается схватка. Солдаты преследуют нацистов по коридорам замка. Огнемёт изрыгает чудовищный язык пламени. Это Return to Castle Wolfenstein, компьютерная игра, ставшая не только спинномозговым приключением, но и чудом науки. Она же — последний продукт Id Software (Мескит, штат Техас). Благодаря своим технологически инновационным играм id оказала огромное влияние на мир компьютерных вычислений: от привычных в современных PC высокоскоростных полноцветных графических карт высокого разрешения до появления армии программистов и игроков в онлайновые игры, внёсших вклад в поп-культуру.
Читать полностью »

image

При заполнении области объектами (например, комнатами в подземелье) в случайном порядке вы рискуете тем, что всё будет слишком случайным. Результат может оказаться абсолютно бесполезным хаосом. В этом туториале я покажу, как использовать для решения этой проблемы двоичное разбиение пространства (Binary Space Partitioning, BSP).

Я подробно и по этапам расскажу об использовании BSP для создания простой двухмерной карты, к примеру, схемы подземелья. Я покажу, как создать простой объект Leaf, который мы используем для разделения области на маленькие сегменты. Затем мы займёмся генерированием в каждом Leaf случайной комнаты. И, наконец, узнаем, как соединить все комнаты коридорами.

Примечание: хоть код примеров и написан на AS3, концепцию можно использовать практически в любом другом языке.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js