Doom работал благодаря статье, которая старше игры на тринадцать лет
https://youtube.com/shorts/qjejcOEpT4w?si=aP_hj_EddkdqMzoj

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

Поэтому порядок посчитали до игры. Уровень режут плоскостью надвое, каждую половину — снова, и так до мелких кусков; разрезы складываются в двоичное дерево. У каждого узла есть ближняя сторона и дальняя — от любой точки, где вы стоите. Дерево одно на весь уровень, а обход у него для каждой точки свой: всю тяжёлую работу делают один раз при сборке уровня, а в игре остаётся быстрый проход по дереву.

Идея не Кармака. Он взял её из научной статьи 1980 года, которую писали вообще не про игры.

#devmath #gamedev #doom #математика #алгоритмы