Важная информация
  • Кое-что о крокодилах, или Oптимизируем рейкастинг

    Автор: Александр Мирошниченко (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;
        }    
    }
    Все тесты и эксперименты я проводил, используя текстовую отладку (вывод лога в консоль). Отслеживал каждый шаг и изменение каждой координаты и переменных. Всё это периодически контролировал Сэм и указывал на ошибки. Некоторые ошибки я сам видел и устранял. В качестве компилятора использовался Hi Tech C v3.09 + эмулятор cp/m (cpm.exe, консольный эмулятор под Windows), в качестве тестовой платформы – Sprinter и его эмулятор (режим эмуляции Спринтера в эмуляторе ZXMAK2).

    Плюсом данного метода является то, что он получает стены не за 2 прохода, а за 1. А значит, будет потрачено гораздо меньше времени и ресурсов на поиск стен. Если добавить сюда разные таблички, всяких синусов, тангенсов и других необходимых вычислений, то оптимизация будет ещё выше, а значит и производительность.

    Минусом данного метода является то, что он требует несколько больше памяти для процедур побочных направлений. Плюс несколько большая сложность кода.

    Под конец хочу внести небольшую ложку дёгтя. К сожалению, я так и не смог до конца реализовать данный метод. Я бился над ним весь декабрь, но наступил Новый Год, начались пьянки, гулянки и другие виды отдыха и ленизма (от слова лень). А потом, началась работа и, меня засыпали задачами, которые и сейчас разгребаю. К счастью, осталось уже не долго. Как только я разгребу рабочие завалы, я сразу продолжу разборы рейкастинга. Благо мой Спринтёр лежит прямо предо мной, на моём рабочем столе

    Надеюсь, приведённая выше инфа кому-то поможет, если кто-то ещё пилит себе «немного дума».

    Комментарии 21 Комментарии
    1. Аватар для krotan
      krotan -
      Спасибо, очень познавательно.
      Статья написана для тех, кто в курсе, про что разговор. Для тех, кто не в курсе стоило бы добавить введение, в котором объяснить, что такое рейкастинг, трассер и т.п.
      С учётом того, что конфигурация для реализации была выбрана довольно экзотичная, хотелось бы увидеть хоть какой-то результат в виде скриншотов или видеоролика теста...
    1. Аватар для Alex Rider
      Alex Rider -
      Да, поддержу, хотелось бы введения с понятными картинками. Я, хоть и читал статью Shuru, все забыл совсем и вспоминал термины в процессе прочтения.
    1. Аватар для Sayman
      Sayman -
      Я планировал вторую статью, но по работе пока не успеваю ничего сделать. Сегодня начальство на месяц в Китай улетело на симпозиумы, вот, месяц времени теперь будет на продолжение разбора, скриншоты, ролики и вторую статью.
    1. Аватар для krt17
      krt17 -
      Подчеркивать не ссылки ...
    1. Аватар для ZXFanat
      ZXFanat -
      Цитата Сообщение от krotan Посмотреть сообщение
      Спасибо, очень познавательно.
      Статья написана для тех, кто в курсе, про что разговор. Для тех, кто не в курсе стоило бы добавить введение, в котором объяснить, что такое рейкастинг, трассер и т.п.
      С учётом того, что конфигурация для реализации была выбрана довольно экзотичная, хотелось бы увидеть хоть какой-то результат в виде скриншотов или видеоролика теста...
      Можно согласится с мнением (комментарием!), что стоило сделать введение, при этом обязательно уточнить, какое конкретно отношение это имеет к ZX Spectrum-у либо к его клона, или к конкретной платформе, упоминаемой на форуме. Статья вроде бы и ничего, читается просто, но вот с середины уже есть ощущение, что хочется узнать, как применить этот метод на клонах ZX. Это к тому, как можно приспособить Ray casting к отрисовке луча монитора и приспособить к экрану Spectrum-а.
    1. Аватар для kostya261
      kostya261 -
      Перечитал статью несколько раз. Точнее уже восемь раз. В целом понравилось. Но на мой скромный взгляд, хотелось бы больше деталей. Как то начали за здравие, а потом раз и скомкали до состояния описания функции, мол и так все понятно. Возможно так и есть, для тех кто в теме. Но вот например я так же хотел бы разобраться.
      ДАЕШЬ ВТОРУЮ ЧАСТЬ!
      И да, так же думал как применить в zx.

      PS а то Cryzis на zx допиливаю, а все в райкаст уперлось
    1. Аватар для Sayman
      Sayman -
      Я Ваши вопросы учту обязательно при написании второй части. от сюда вопрос к CityAce - можно ли во время проведения конкурса прислать ещё одну статью, но не для конкурса, но с её последующей выкладкой здесь?
    1. Аватар для CityAceE
      CityAceE -
      Цитата Сообщение от Sayman Посмотреть сообщение
      можно ли во время проведения конкурса прислать ещё одну статью, но не для конкурса, но с её последующей выкладкой здесь?
      Да, безусловно, после проведения конкурса площадка для публикации статей будет доступна для всех жалеющих.
    1. Аватар для ZXFanat
      ZXFanat -
      Цитата Сообщение от Sayman Посмотреть сообщение
      Я Ваши вопросы учту обязательно при написании второй части. от сюда вопрос к CityAce - можно ли во время проведения конкурса прислать ещё одну статью, но не для конкурса, но с её последующей выкладкой здесь?
      Мое предложение. Разрешить опубликовать и вторую часть, как дополнение к статье. Возможно у автора не было времени, как раз для публикации второй части. Ну не успел отправит, и все тут! А уж результаты по второй части рассматривать вне конкурса, но если автор войдет в тройку призеров, то рассматривать с учетом и второй части. Все же, это честно будет!
    1. Аватар для AlexNN
      AlexNN -
      Интересно было почитать, помню году в 1995 разбирался, как умудрялись "считать синусы" в реальном времени на спектруме)

      Использовать СИ на Z80, не слишком расточительно в плане ресурсов ЦП,
      в таких тяжелых для него задачах?
    1. Аватар для Sayman
      Sayman -
      в данном случае, я использую си на пц с честными синусами, потом по результату генерирую таблички которые подсовываю в исходник под спринтер. в общем и целом, си использую в данном случае для разбора полёта, хотя да. начинал (первые исходники под Спринтер) были с честными синусами (УЖАС как тормозило всё и памяти жрёт немерено, чур меня от этих float и double). самый первый сорец рейкастинга с честными синусами и честным DDA был запущен по методу от lodev. это жесть какая то была, но зато картинка была с залитыми стенами)))
      более подробно во второй части...
    1. Аватар для AlexNN
      AlexNN -
      вот бы современный код был настолько оптимизирован, давно уже не занимаюсь программированием, но понимаю сколько мусора крутится в процессоре современного пк, на спектруме много изящных решений радилось, помню даже книжка была с такими фишками на асме.
    1. Аватар для goodboy
      goodboy -
      Цитата Сообщение от AlexNN Посмотреть сообщение
      понимаю сколько мусора крутится в процессоре современного пк
      в игрушке скомпилированной с си для спека внутри то-же самое.
      хотя обычно прибегают к компромиссу - вывод графики пишут на-асме, логику компилят.
      в результате от избыточного кода страдает объём данных для графики.
      как правило в таких играх примерно 20экранов и пара/тройка врагов.
    1. Аватар для krotan
      krotan -
      Вы не путаете С и С++ ?
    1. Аватар для AlexNN
      AlexNN -
      Цитата Сообщение от krotan Посмотреть сообщение
      Вы не путаете С и С++ ?
      не путаем)
      в с++ всё ещё хуже с сбережение ресурсов цп,
      современные программисты очень расточительные
      в отличии от олдскульных
    1. Аватар для kostya261
      kostya261 -
      Assembler Forever
    1. Аватар для kostya261
      kostya261 -
      Цитата Сообщение от AlexNN Посмотреть сообщение
      современные программисты очень расточительные
      в отличии от олдскульных
      Ну им не приходится за каждый байт бороться, в отличие от олдскульных программистов, и тех, кто кодит для микроконтроллеров, где уже даже не байты а биты на счету, в попытках сэкономить на железе...
    1. Аватар для Pencioner
      Pencioner -
      Полуоффтопик: не LUA а Lua см. http://www.lua.org/about.html

      Like most names, it should be written in lower case with an initial capital, that is, "Lua". Please do not write it as "LUA", which is both ugly and confusing, because then it becomes an acronym with different meanings for different people. So, please, write "Lua" right!

      придрался только из-за того что Lua на данный момент самый любимый ЯП
    1. Аватар для ZXFanat
      ZXFanat -
      Цитата Сообщение от Pencioner Посмотреть сообщение
      Полуоффтопик: не LUA а Lua см. http://www.lua.org/about.html

      Like most names, it should be written in lower case with an initial capital, that is, "Lua". Please do not write it as "LUA", which is both ugly and confusing, because then it becomes an acronym with different meanings for different people. So, please, write "Lua" right!

      придрался только из-за того что Lua на данный момент самый любимый ЯП
      "А ну харэ тут не по нашему говорить. Заграница рядом!".
    1. Аватар для carchip
      carchip -
      Здорово если будет еще статья что-то типа: Основы Трехмерной графики для Спектрум. практическое пособие для начинающих.