Навигация по разделам
Последние записи дневников
Последние комментарии статей
Последние сообщения
Автор: Александр Мирошниченко (Sayman)
После того, как тема на форуме затихла, я начал активно рыскать по просторам интернета в поисках нужных мне ответов на некоторые алгоритмические вопросы. Кроме того, было жутко интересно – какие в мире бывают методы и алгоритмы реализации рейкастинга. Да, на форуме я выкладывал ссылки (про которые многие и без того уже знали) на первоисточник статьи от Ширу – метод Permadi. В оригинале данных чуть побольше, хоть и на английском языке. Так же была вариация рейкастинга от Lodev. Но там сильно всё завязано на типах данных float и double (как описывает этот метод автор, он основан на неком DDA). Примечательно, но для MSX2/TR был выбран именно это метод и реализован так же на си (с некоторыми оптимизациями на асме, автор порта ARTRAG, найти можно на форуме msx.org). В остальном, по миру ходит метод от Permadi. Собственно, этот вариант более понятен и его проще оптимизировать под слабые машины, отличные от мощных ПЦ. Вариантов реализации оказалось так много. Куда его только не впихнули – и в qbasic, и на turbo pascal (для ms-dos), и на python, и С#, блин, его засунули даже в LUA. Но при всём разнообразии реализаций, они все между собой оказались похожими. Различия касаются в основном методов оптимизации - генерация и использование некоторых табличек, а так же в количестве трассеров (лучей) бросаемых на карту. Чтобы сократить нагрузку при сканировании, например, когда fov = 64 градусам (это когда окружность описываем «типа 256 градусами, этот угол fov будет примерно «типа 90» градусов), вместо 64 трассеров кидаем только лишь каждый 8й трассер. Пропущенные трассеры подлежат интерполяции (например, методом половинного деления). На этом основные различия заканчиваются. Все вариации как один используют стандартное описание от Permadi. Напомню основной алгоритм – окружность поделена на 4 части (по градусам) – 0-90-180-270-360. Получается 4 основных направления – влево-вверх, вправо-вверх, вправо-вниз и влево-вниз. При сканировании карты используют стандартную двухпроходную модель – сначала пускают горизонтальные трассеры (чтобы найти горизонтальные пересечения/стены/клетки), а потом вертикальные. Для каждой из четвертей есть только одно основное направление (один основной проход), второе направление (проход) уже является побочным. Что значит основное направление? Вспоминаем из оригинального описания: для углов больше 180гр и меньше 180гр (if angle > FIXED(180) … else … ) = основное направление горизонтальное (поиск горизонтальных пересечений, луч идёт вверх/вниз), а для углов 90-270 (if(angle > FIXED(90) && angle < FIXED(270) … else …) = основное направление вертикальное (луч идёт влево/вправо).
Каждый раз бросается 2 трассера. Но, как я уже сказал, основная оптимизация во всех реализациях довольно стандартна – таблички вместо реалтайм расчёта и бросание меньшего количества трассеров с последующей интерполяцией пропущенных. Это всё, конечно, даёт прирост производительности, но такой ли он большой?
В переписке с Alone Coder`ом по вопросам о рейкастинге он выдал мне несколько комментариев с некоторыми расчётами и формулами. НО, поскольку я в математике ни в зуб ногой, для меня это всё было как чёрная магия, а Alone был как колдун, подлежащий сожжению на большом костре
Не поняв ни слова из его логарифмов я обратился к ещё одному спецу (ну как спецу, вроде больше меня шарит в этих вопросах и разжевывает неплохо) – к Sam Style`у. Недолго думая он начал сыпать меня формулами, картинками, идеями (крокодилами, как он это всё называл). На одном из таких крокодилов мы и остановились. Если откинуть все мои затупы и прочие подробности, то суть его идеи по оптимизации заключается в следующем:
1. Окружность разбивается так же на 4 части, но с другими градусами – 32-96-160-224. Подробно изображено на картинке 1. Как видно, старые направления заменяются. Было влево-вверх, стало отдельно влево и отдельно вверх. Так и с другими направлениями.
2. Каждому направлению соответствует своя формула расчёта для Xa и Ya (использую оригинальные названия переменных из статьи Ширу/Permadi).
3. Для каждой из четвертей соответствует своё основное направление. Для сканирования влево и вправо это горизонтальное направление (трассеры), для сканирования вверх и вниз – вертикальное направление.
1:
Xa = 64
Ya = -64 * tan(ra)
2:
Xa = -64
Ya = 64 / tan(ra)
3:
Xa = -64
Ya = 65 * tan(ra)
4:
Xa = 64
Ya = -64 / tan(ra)
ra = угол нашего трассера/луча.
При этом для сканирования каждой из четвертей нужно кидать не 2 трассера, а 1. Т.е. метод однопроходный. Ну, или почти однопроходный. Тут есть шанс на пропуск клеток. Чтобы этого избежать нужно каждый раз, когда увеличивается шаг трассера, проверять переменные.
Если это направление влево или вправо, тогда проверяем переменную координаты Y.
Если направление вверх или вниз, тогда это координата X.
Когда происходит переход на следующую клетку по «побочному направлению», это говорит о том, что мы, скорей всего, пропустили клетку. Но, есть ли там стена? Нужно ли нам всегда кидать трассер тогда, когда мы обнаружили пропущенную клетку? Нет, не нужно. Достаточно проверить, прям по карте по нужным координатам, есть ли там «стена» или нет. В моём варианте используется макрос MAP():
#define MAP(x,y) (MapData[(x) + ((y) * mapWidth)])
Соответственно, я делаю:
if((MAP(mapX-1, mapY)) != 0) тогда запускаю побочный трассер.
Следить за координатами лучше до того, как трассер шагнёт дальше по карте. Тогда не придётся каждый раз делать возврат трассера и запускать его по новой для пропущенной клетки. Чтобы было понятней о том, как мы можем пропустить клетку, приведу пример, изображённый на второй картинке.
В данном примере под цифрой 1 – изначальная точка, из которой исходят трассеры (проще говоря – наш персонаж). Пока идёт трассер, мы находим вертикальные линии (пересечения, зелёные точки на линиях) наших «стен». Но, малиновая точка указывает на горизонтальную линию стены, которую мы, двигаясь по основному направлению, никогда не найдём. Вот тут нам и потребуется заранее проверить координату, если она изменилась (в нашем примере при переходе к последней точке она будет изменена), проверить по карте на пустотность клетки и, если она не пустая, запустить побочный трассер. После нахождения стены, продолжать двигаться в направлении этого трассера нет нужды, нужно переходить к следующему углу (т.е. к следующему трассеру).
К слову говоря, по стандартному методу, если запускается сначала вертикальное сканирование, то именно эта точка будет найдена только после запуска второго прохода – горизонтального. Можно их поменять местами, но тогда большую часть времени будет потрачено в холостую.
В данном методе примерно 70% стен получаем одним проходом по основному направлению. Остальные 30% получаем побочным сканированием. Учитывая, что большая часть стен находится гораздо быстрее, чем в стандартном методе от Ширу/Permadi то думаю, что данный алгоритм даёт больше оптимизации, чем остальные. Ниже я привожу кусок кода на си, всего одна процедура одного из направлений. Просьба сильно не пинать за фуфлокод:
Код:
void dirRight(angle_t pa)
{
register int ax, ay;
static int Xa, Ya;
static u16_t ls, dx;
static int mapX, mapY, omy;
Xa = 64;
Ya = vTanTable[pa & 0x7f];
ax = player->posX + 64 - (player->posX & 0x3f);
ay = player->posY - (ax - player->posX)*TanTable[pa & 0x7f]/256;
dx = ax - player->posX;
ls = vStep[pa];
dst.rayLenght = ls*dx/64;
omy = player->posY/64;
while(1) {
mapX = ax/64;
mapY = ay/64;
if(mapX < 0 || mapY < 0 || mapX > mapWidth || mapY > mapHeight) break;
if(mapY != omy) {
if((MAP(mapX-1, mapY)) != 0) {
if(Ya > 0) {
if(dst.rayLenght < ls) reverseLeftRightDown(pa, player->posX, player->posY, true);
else reverseLeftRightDown(pa, (ax-Xa), (ay-Ya), false);
} else {
if(dst.rayLenght < ls) reverseLeftRightDown(pa, player->posX, player->posY, false);
else reverseLeftRightDown(pa, (ax-Xa), (ay-Ya), false);
}
break;
}
omy = mapY;
}
if(MAP(mapX, mapY) > 0) {
dst.color = MAP(mapX, mapY);
break;
}
ax+=Xa;
ay+=Ya;
dst.rayLenght += ls;
}
}
Плюсом данного метода является то, что он получает стены не за 2 прохода, а за 1. А значит, будет потрачено гораздо меньше времени и ресурсов на поиск стен. Если добавить сюда разные таблички, всяких синусов, тангенсов и других необходимых вычислений, то оптимизация будет ещё выше, а значит и производительность.
Минусом данного метода является то, что он требует несколько больше памяти для процедур побочных направлений. Плюс несколько большая сложность кода.
Под конец хочу внести небольшую ложку дёгтя. К сожалению, я так и не смог до конца реализовать данный метод. Я бился над ним весь декабрь, но наступил Новый Год, начались пьянки, гулянки и другие виды отдыха и ленизма (от слова лень). А потом, началась работа и, меня засыпали задачами, которые и сейчас разгребаю. К счастью, осталось уже не долго. Как только я разгребу рабочие завалы, я сразу продолжу разборы рейкастинга. Благо мой Спринтёр лежит прямо предо мной, на моём рабочем столе
Надеюсь, приведённая выше инфа кому-то поможет, если кто-то ещё пилит себе «немного дума».
Yandex.Direct
Сообщение форума