Рубрика «двоичное разбиение пространства»

в 9:00, , рубрики: AGI, binary space partitioning, DOOM, Heretic, Hexen, id software, quake, ruvds_статьи, Slordax, Wolfenstein 3D, Блог компании RUVDS.com, выгорание, двоичное разбиение пространства, джон кармак, Программирование, разработка игр, сильный ИИ, тайм-менеджмент, управление разработкой, эффективность кода

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


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

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

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

в 8:44, , рубрики: navmesh, Алгоритмы, двоичное разбиение пространства, дерево квадрантов, закон Амдала, Карьера в IT-индустрии, манипулирование, навигационная сетка, офисная политика, поиск A*, психология, техножаргон, технолепет

У программистов есть разные поговорки о трудных проблемах. Наверное, мой любимый вариант: «В информатике две трудные проблемы: недействительность кэша, присвоение имён и ошибки на единицу».

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

А это очень трудно.

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

в 6:12, , рубрики: binary space partitioning, bsp, 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.

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

в 14:27, , рубрики: Алгоритмы, генерация лабиринтов, двоичное разбиение пространства, Дизайн игр, клеточные автоматы, процедурная генерация карт, разработка игр
Генерация подземелий и пещер для моей игры - 1

На этой неделе я начал работать над новой темой: генерацией подземелий и пещер. Я использовал разбиение пространства для генерации комнат, алгоритмы генерации лабиринтов для генерации коридоров и клеточные автоматы для придания пещерам более естествненного внешнего вида.

Разбиение пространства

Существует множество способов генерации комнат для подземелья (случайное размещение, генерация на основе агентов, с использованием separation steering behavior или физического движка, и т.д.). Но мой любимый метод — это разбиение пространства, потому что оно легко контролируется и расширяется.

Способов разбиения пространства тоже очень много: разделение на сетки, двоичное разбиение пространства, разбиение пространства деревом квадрантов, диаграммы Вороного и т.д. Я решил использовать двоичное разбиение пространства, потому что оно хорошо подходит для генерации прямоугольных комнат. Этот метод получил популярность благодаря статье на RogueBasin.

Единственная сложность этого алгоритма — выбор позиции разделения. Если мы не наложим ограничение на позицию разделения, то будем получать странные разбиения пространства:

Генерация подземелий и пещер для моей игры - 2

Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.
Читать полностью »

в 8:44, , рубрики: adaptive tile refresh, binary space partitioning, id software, адаптивное обновление тайлов, двоичное разбиение пространства, разработка игр

От переводчика: эта статья написана Дэвидом Кушнером в 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 высокоскоростных полноцветных графических карт высокого разрешения до появления армии программистов и игроков в онлайновые игры, внёсших вклад в поп-культуру.
Читать полностью »

в 8:44, , рубрики: binary space partitioning, bsp, Алгоритмы, генерация лабиринтов, двоичное разбиение пространства, разработка игр, случайные карты

image

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

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

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

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js