Модифицируем алгоритм Брезенхэма для рейкаста в стиле Wolf3D
Недавняя статья о рендеринге полигонов для «Денди» завершилась (уже в камментах) небольшой интрижкой: «хочу реализовать 2.5D, но не уверен, что получится плавная камера». Естественно, мимо такого я пройти не мог :) и сейчас прикладываю максимум усилий к тому, чтобы плавная камера на этом несуразном железе таки получилась. По мне, шутер (даже 2.5 D) без мышки, хотя бы пополамной или RS232, и плавной камеры с высокими FPS — не шутер, а вот остальное можно смело принести в жертву драйву (и принесём!)
Наивный алгоритм, он же DDA, знают все. Но ветвления на каждом шаге, с делениями, умножениями и сравнениями — это явно не про «Денди» сказано. К счастью, у нас есть намного более быстрый алгоритм — алгоритм рисования линий Брезенхэма. Нужно только его немножко доработать напильником, чтобы он годился для того, для чего мы его собираемся использовать!
Оригинального «Брезентыча» я особо подробно расписывать не буду. Если ещё его не знаете — просто прочитайте, а я сразу перейду к тому, чем он нам неугоден в его каноничном виде.
Оригинальный «Брезентыч» шагает «по бо́льшей координате» на целую ячейку, после чего шагает «по меньшей координате» на величину, определяемую тангенсом угла — ну и после этого заполняет пиксел (пусть будет жёлтым, чтобы не мешал разглядеть остальное). Что будет, если вместо заполнения мы просто проверим, есть там стенка или нет? Будет большой облом, потому что те стенки, которые отмечены большим вопросительным знаком, он проверять не будет и пропустит стенку, если она там есть. То есть пересечения с этими потенциальными стенками, отмеченные синими нормалями к лучу, будут пропущены.
Поэтому первое, что мы сделаем — поменяем порядок шагов. Шаг по той координате, по которой луч имеет меньшую «дельту», мы будем делать первым (назовём его «смещением»), а шаг по той координате, по которой «дельта» больше — вторым (его так и будем называть «шаг», потому что он строго равен целой ячейке). И, конечно, будем дважды проверять карту: после смещения и потом после шага тоже.
Возьмём для определённости целочисленные двухбайтовые координаты и лабиринт 256×256, состоящий из ячеек 256×256 пикселов (то и другое вчетверо больше, чем в Wolf3D, но мы и не собираемся ничего клонировать в точности). Итак, в начале мы определяемся, какая «дельта» больше (разумеется, по модулю), и выбираем, какая координата будет координатой шага, а какая — координатой смещения. Дальше мы начинаем нашу замечательную парочку действий «смещение‑шаг, смещение‑шаг», добавляя к координате смещения — смещение, а к координате шага — ровно 256, чтобы она «скакнула» в следующую ячейку. Тут есть пикантный момент — если в DDA мы проверяли каждую ячейку один раз, то тут в результате смещения можно прийти ровно в ту же ячейку, в которой закончился прошлый шаг. Детали реализации зависят от процессора: если это какой‑нибудь 386-й с зачаточным кэшем, то лучше ничего не трогать и не делать лишних ветвлений. Старший байт не изменился (смещение не привело нас в другую ячейку), поэтому обращения к памяти не будет — будет повторная проверка закэшированного значения, что по скорости примерно равно обращению к регистру. А вот если кэша нет от слова «совсем» (например, какой‑нибудь микроконтроллер) — после смещения мы не лезем сразу проверять, есть ли там стенка, а сначала смотрим, был ли перенос из младшего байта в старший. Если не было — то и проверять нечего, сразу переходим к шагу.
Зашагала лесенка, заиграла песенка! Думаете, теперь всё хорошо? Как бы да, да не совсем… внимательный читательский взгляд, конечно, уже заметил проблему: третье смещение влезает в проверяемую ячейку намного сильнее, чем ожидается. Ведь луч её задевает буквально за самый краешек, уголком…, а если бы совсем не задевал?
Ладно, хватит играть в загадки. Внимательному читателю уже совершенно ясно, как исправить этот косяк — да и я, честно говоря, не сталкивался с ним в коде просто потому, что он очевиден намного раньше, чем будет написана первая реальная строчка. Мы просто должны начинать шагать «по Брезу» строго с начального пиксела ячейки (нулевого, если шагаем в положительную сторону, и 255-го, если в отрицательную). При этом все шаги «прилипнут к стенке» (они же строго 256), а смещения будут приводить ровно туда, куда надо! Нам потребуются всего‑навсего два шага методом DDA максимум (если мы сразу же влетим в стенку по координате смещения, то никуда уже и не шагаем, а если не влетим — то потребуется досместиться по координате шага). Да и те — не чистый DDA, а какой‑то «продукт DDA‑содержащий», потому что проблема возникает не из‑за ненулевой начальной точки, а из‑за ненулевой конечной (ну или «не-255-й», если мы шагаем в сторону минуса). То есть первый шаг, по сути, тоже «Брезенхэм модифицированный», только не на полные 256, а ровно на такую величину, чтобы оказаться в нужной позиции. Делить, умножать, сравнивать, до какой стенки ближе — не придётся.
Теперь перейдём к демо‑коду. Рендер как таковой я пока не делал — у меня есть свои планы на него, но специально для @Swamp_Dok распишу, что именно я выложил и как оно работает.
Эта штука просто показывает на экране карту, на которой трассируется ровно один луч, и отмечает кружочком место, где он впервые нашёл стену (правда, если кастинг начинается уже в стене, благо клиппинга там нет, начинает забавно глючить, и я пока не выяснил, почему, хотя в теории глючить он не должен). Чёрточка‑козявочка — это вектор самого луча, а точки разной степени серости мы только что разобрали в самой статье. Поскольку места на экране мало, делает оно всего 5 шагов — естественно, для игры это «ни о чём». Все синусы и косинусы для наглядности даны открытым текстом, а оптимизированные под дохлые процессоры можно подсмотреть тут (серьёзно, эта байда предполагалась к работе на 8086 с CGA‑монитором, правда, не удалось выяснить, тянет ли; при этом там оптимизация ещё не сказала своего последнего слова, в частности, там реально DDA работает, хотя предмет этой статьи — первое, что туда надо было бы вбросить). Обратите особое внимание, что синусы и косинусы в знаменателях не проверяются на ноль! До них доходит дело только в тех случаях, когда на шаге 256 смещение было как минимум 1. То есть их величина не просто ненулевая — она достаточная, чтобы в целочисленной арифметике (не страдающей проблемами округления) набежала как минимум единица. Делить на такие величины можно смело.
Разберём, какая переменная что означает, дальше уже сопоставить код и статью будет тривиальной задачей. PlayerX и PlayerY — очевидно, координаты игрока. Что неочевидно — из‑за описанной выше зацикленности карты там будет видно её часть и левее игрока, и выше, хотя он в ячейке 1×1. PlayerA — угол, под которым смотрит луч. Чтобы не было проблемы модуля по двум пи — я просто приравнял 65 536 попугаев к двум пи, пусть само «закольцуется». Менее очевидно то обстоятельство, что считаем мы всё «как математики», а рисуем — сверху вниз, а не снизу вверх (вот такая вот VGAшная адресация). Поэтому на экране мы видим картинку, отзеркаленную по вертикали относительно той, которую мы себе представили в своём вышколенном (и «выинститутенном») теоретической тригонометрией воображении. BrezStep, BrezShift — величины шага и смещения. Зачем под шаг переменная? А у нас знак бывает разный. +256 и -256. BrezToStart — это сколько осталось координате шага до старта. Лекарство от косяка с третьего рисунка, по сути — обкусанный до нужной длины BrezStep. А вот у координаты смещения такой переменной нет — мы вычисляем её значение «на лету» и сразу используем. BrezToFinish — это сколько осталось координате смещения до найденной наконец‑то стенки. Используется только в том случае, если мы влипли в стенку сразу после смещения, не доходя до шага. Аналогично, её пара, соответствующая координате шага — вычисляется «на лету». BrezPos — наше текущее положение по координате смещения. BrezPrev — это же положение, которое мы запоминаем до того, как добавить смещение. Ведь это только если в стенку нас привёл шаг, мы оказываемся сразу в точных координатах пересечения луча и стенки! А вот если туда нас привело смещение — мы оказались где‑то в недрах стены, а не на её поверхности, и надо снова добрать остатки при помощи «продукта DDA‑содержащего». Поэтому мы берём значение координаты до смещения и «доползаем» при помощи уже точных вычислений. BrezCell — это, как нетрудно догадаться, текущее положение по координате шага, потому что указывает, по сути, на ячейку (хоть и с пиксельной точностью). От координаты пиксела внутри ячейки мы в самом начале избавляемся и дальше он — константа, вместе с младшим байтом этой переменной. MapX и MapY можно было бы обрубить до байта — это, естественно, координаты уже в буквальном смысле «с точностью до ячейки». Применяются только для рисования карты, дальше я не размножаю лишние сущности и беру старшие байты от координат шага и смещения сообразно с тем, кому из них выпало быть горизонтальной, а кому — вертикальной.
Насчёт ProcessSuccess я должен, конечно, покаяться. Дело в том, что я там сразу, прямо в параметрах вызова, вычисляю истинные координаты коллизии (если это, конечно, требуется — если всё закончилось шагом, они у нас уже есть «как есть») и тут же перевожу их в экранные. Выдирать их оттуда кому‑то будет не так удобно, как если бы я сделал всё «по‑уму» — передал координаты коллизии, а всё остальное бы совершил уже внутри функции. Но меня обуяла лень и нетерпячка. Простите. С другой стороны, это место всё равно по‑хорошему требует ещё большой работы, чтобы вытащить не только координаты, но и угол, под которым кастуемый луч нашёл свою текстуру. Зачем угол‑то, наверняка уже спросил внимательный читатель? Мы же один столбец рисуем?
В том‑то и дело, что не один. В «дендях» экран состоит из 32×30 тайлов, каждый тайл — 8×8. Поэтому для плавности рендера мы не можем позволить себе рендерить стены, даже однотонные, в 32 столбца — в CGAStein 3D и то я сделал 80, и это ещё LOD1 (а центр поля зрения рендерится вообще в восьмикратном разрешении, весь экран в таком был бы 640! Этого бы хватило не то что 8086 — 80286 уложить в «пошаговую стратегию» с пятью кадрами в секунду). Нам (ну то есть «мы пахали», не мне, конечно — коллеге, если ему захочется сие сотворить) потребуется набор спрайтов с косо срезанными торцами, чтобы перебрать все варианты наклона верха и низа столбца.
Геометрия при таком несоответствии разрешений будет, конечно, противненько прыгать (я попробую это отмоделировать потом отдельно, благо движок‑то — вот он, и даже два, если вспомнить про CGAStein). Но в крайнем случае, если будет слишком бесяче — можно просто придать спрайтам «расплывчатый» вид а‑ля «я у мамки силовое поле, а вовсе не кирпичная стена» :) Ну, и у нас есть плавный горизонтальный скроллинг тайлового бэкграунда, так что всё в наших руках ;)
Ещё одна штука, которая должна быть в ProcessSuccess — это обработка мобов (в оригинальном движке Wolf3D они назывались в коде ещё не «MOb», а «MObj», из‑за чего я ласково величал их то «мобжами», то, естественно, «бомжами»). Но она, разумеется, дальнейший каст не прерывает. Просто в нашем крошечном (один прозрачный объект и одна непрозрачная стена) z‑буфере появляется не только последняя, но и первый. Они у коллеги уже готовы, и, как мы все помним — они (вообще супер!) полигональные! Как связать карту и объект — опять же, см. CGAStein 3-D. Тут ничего не изменилось со времён Wolf3D, если не «Катакомб». Ставим ссылки, подчищаем ссылки, реальные координаты считаем, если «выстрелила» ссылка. Итого потенциально (если хватит производительности слониковой приставки, конечно) имеем плавнейшую камеру! А поскольку полигоны объектов пересчитываются ну ооочень редко, возможно, и вовсе выходим на 50 FPS.
Что же касается моих собственных планов и почему «VGA» там »16». Я хотел потестить эффект «ночного теплового прицела»: с нормальным оружием игра играется в 320×200, но как только мы берём снайперку — VGA переключается в 640×480×16 (во времена Wolf3D экран при этом не гасился, было такое промежуточное «блым» с корявой картинкой, но зато очень быстро) и рендер начинает идти по одному плану за кадр. А чтобы артефакты были «правильными» — палитра строго RGBW. То есть в первый кадр рендерим все красные цвета, во второй — все зелёные, в третий — все синие, в четвёртый — все белые добавочные и снова‑заново, а поскольку игровой процесс на месте не стои́т, всё начинает оставлять за собой «хвосты» типа «я такое послесвечение у ночного прицела, а вовсе не нехватка процессорной мощности отрисовать 640×480». Ну, разумеется, тормозов всё равно не избежать, потому что даже один план от 640×480 на «двушке» собрать — не сахар :) В основном это «эффект ради эффекта», мне даже не особо‑то и хочется это тестировать на быстродействие, просто увидеть хочу, как это — остановиться, поймать момент, когда моб замер, прицелиться тщательно…
В общем, развлекайтесь :)
