| движемся к новому колдету |
[May. 7th, 2019|06:26 pm] |
идея с beveled bsp оказалась сложнее, чем думалось. штука в том, что в отличие от квачей, где мы бегаем в пустоте, окружённой солидами, в думе всё наоборот: технически мы бегаем в солиде, из которого вырезаны дырки-пустоты. это не особая проблема, но несколько геморройно выворачивать всю логику (и легко таки наебаться).
но! можно зайти с другой стороны. нам, по сути, надо определить время (и сам факт) столкновения axis-algned box и line. для чего можно надуть линию при помощи minkowski sum, и потом просто сделать рэйкаст. звучит страшно? bear with me.
за страшным «надуванием» на самом деле лежит… всё тот же старый добрый алгоритм проверки столкновений ящика и выпуклого мэша, который задан ограничивающими плоскостями. то есть, точно тот самый алгоритм, который используется в кваках (и всех прочих 3д-игрушках) для трассировки ящичков.
потому как — что такое наша линия? это дегенерировавший выпуклый мэш! он ограничен шестью плоскостями (четырьмя для линий, параллельных осям координат). поскольку линия у нас бесконечная по высоте, то достаточно создать две плоскости для самой линии, две вертикальных плоскости для ограничения линии справа и слева, и ещё две горизонтальных для верха и низа (если смотреть на линию сверху, как мы видим автомап; очевидно, что z top и z bottom плоскости не нужны, потому что мы никогда не сможем об них удариться). всё, у нас готов объём, который можно скормить совершенно стандартному алгоритму. и этот объём можно «надуть», чтобы «сдуть» ящик в точку. проблема решена.
почему так, а не более классическим путешествием по bsp, с проверкой листьев? ну, в принципе разница небольшая (санс «вывернутая логика», см. выше), но у нас, вообще-то, 2д чертёж. который вдобавок разложен в блокмапе. то есть, мы можем собирать линии и предметы одновременно, тупо шагая по блокмапу, и проверяя столкновения со всем собраным. тем более, что предметы отлично обрабатываются точно тем же алгоритмом, потому что это всё те же самые шесть плоскостей. и 3д-полы тоже, потому что… да-да, те же самые шесть плоскостей. и обычные полы с потолками, потому что… опять две ограничивающие плоскости. и всё это отлично работает для 3д-пути, хотя карта и 2д. и ещё у нас есть нормаль точки столкновения, так что можно сделать слайд. да, имеем небольшой оверхэд, но зато единообразный код для всего (одна функция свипа), и никаких дополнительных данных хранить не надо (все нужные плоскости игра уже посчитала и использует в других местах, а недостающие — тупо axis-aligned, и создаются даже без дот-продукта).
на самом деле это открывает и другие интересные возможности. например, проверка столкновений с md2/md3 моделями не просто по bounding box, а по их конкретной форме (строим для них бсп при загрузке, докидывем axial planes — бинго!), полиобъекты любой сложности и ориентации, в том числе ограниченые сверху и снизу, автоматическая обработка слопов… и всё это одним и тем же кодом. ну не прелесть ли?
ах, да. вращающиеся/движущиеся полидвери и прочие сложные штуки, которые должны отталкивать игрока — это снова таки всё тот же код. нам без разницы, считать ли время до столкновения, или минимально необходимое усилие для выталкивания одного объекта из другого: алгоритм может посчитать и это.
правда, оригинальный думокод по дороге делает ещё кучу всякого другого говна, и это надо будет бережно вытащить оттуда. но в итоге получим красивый универсальный код для трассировки ящиков, и код, который будет использовать трасер чтобы посчитать реальный путь, слайд, активировать лайндефы и ты пы. сам трасер останется в крестах, а остальное можно (и нужно!) вытащить в вавумцэ — и вуаля: моды смогут создавать кастомную физику. да хоть полноценный физический движок — все нужные примитивы есть, и колдет больше не ограничен рамками «ящик-ящик».
а ещё трэйсер отлично пригодится в создании navigational meshes для ботов: наконец-то можно будет надёжно определить, можно ли из одной точки субсектора попасть в другую. можно делать сложно, но можно и просто: каждый субсектор — нода. проверяем, можно ли (с учётом слайдов и прыжков) дойти из центра одного субсектора до центра другого — и вуаля: готова инфа по проходимости., даже с примерной оценкой стоимости. потом a-star, твики навигации — опа, вполне разумно бегающие боты без вручную расставленых вэйпоинтов.
тут очень кстати «вывернутая логика» дума: в ку3 приходилось делать сложные вычисления, чтобы построить карту «пустот», а в думе субсекторы уже предоставляют эту карту, и каждый субсектор гарантировано выпуклый. are we cool yet? ain't it cool? |
|
|
![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small}