Вычисление того, какие плитки освещены в игре на основе плиток («трассировка лучей»)

Быстро и грязно:

(В зависимости от размера массива)

• Прокрутите каждую плитку
• проведи линию к Свету
• Если какая-либо часть линии попадает в X, значит, она находится в тени.
• (Необязательно): подсчитайте количество X, через которое проходит линия, и выполните причудливые математические вычисления, чтобы определить долю плитки в тени. NB: это можно сделать с помощью сглаживания линии между плиткой и источником света (поэтому при просмотре других плиток на пути обратно к источнику света) во время процедуры определения порога они будут отображаться как небольшие аномалии. В зависимости от используемой логики вы потенциально можете определить, насколько (если вообще) плитка находится в тени.

Вы также можете отслеживать, какие пиксели были протестированы, поэтому немного оптимизируйте решение и не проверяйте пиксели дважды.

Это может быть довольно хорошо куполообразно, используя манипуляции с изображениями и рисование прямых линий между пикселями (плитками). Если линии полупрозрачны, а блоки X снова полупрозрачны. Вы можете установить порог изображения, чтобы определить, пересекла ли линия значок «X».

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

Чтобы проверить, находится ли плитка в тени, вам нужно провести прямую линию обратно к источнику света. Если линия пересекает другую занятую плитку, то тестируемая вами плитка находится в тени. Алгоритмы трассировки лучей делают это для каждого объекта (в вашем случае плитки) в представлении.

Статья о трассировке лучей в Википедии имеет псевдокод.

Если вы не хотите тратить время на то, чтобы заново изобрести / заново реализовать это, существует множество игровых движков. Ogre3D - это игровой движок с открытым исходным кодом, который полностью поддерживает освещение, а также звук и управление игрой.

Вы можете столкнуться со всевозможными сложностями с вычислением окклюзии и т. д., Или вы можете использовать простой метод грубой силы: для каждой ячейки используйте алгоритм рисования линии, такой как Алгоритм линии Брезенхема, чтобы исследовать каждую ячейку между текущей и источником света. Если есть заполненные ячейки или (если у вас только один источник света) ячейки, которые уже были протестированы и оказались в тени, ваша ячейка находится в тени. Если вы столкнетесь с заведомо освещенной камерой, ваша камера также будет освещена. Простая оптимизация для этого - установить состояние любых ячеек, с которыми вы сталкиваетесь на линии, независимо от конечного результата.

Это примерно то, что я использовал в своем 2004 победитель IOCCC. Однако очевидно, что из этого не получится хороший пример кода. ;)

Обновлено: как указывает Лорен, с этой оптимизацией вам нужно только выбрать пиксели по краю карты, чтобы отследить их.

Решение TK - это то, что вы обычно используете для такого рода вещей.

Для сценария частичного освещения вы можете сделать так, чтобы, если плитка оказывается в тени, эта плитка затем разделяется на 4 плитки, и каждая из них проверяется. Затем вы могли бы разделить это столько, сколько захотите?

Редактировать:

Вы также можете немного оптимизировать его, не тестируя ни одну из плиток, прилегающих к источнику света - я думаю, это будет важнее сделать, когда у вас есть несколько источников света ...

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

Изначально пометьте все пиксели как светящиеся.

Для каждого пикселя на краю карты: как предложил Арахнид, используйте Брезенхема, чтобы провести линию от пикселя до источника света. Если эта линия встречается с препятствием, пометьте все пиксели от края до границы, находящейся сразу за препятствием, как находящиеся в тени.

Сообщество разработчиков roguelike в некоторой степени одержимо алгоритмами прямой видимости и поля зрения.

Вот ссылка на вики-статью по теме roguelike: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Для моей рогаликовой игры я реализовал алгоритм отбрасывания теней (http://roguebasin.roguelikedevelopment.org/index.php?title=Shadow_casting) на Python. Его было немного сложно собрать, но он работал достаточно эффективно (даже на чистом Python) и давал хорошие результаты.

«Разрешительное поле зрения», похоже, также набирает популярность: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

Это просто для развлечения:

Вы можете воспроизвести подход Doom 3 в 2D, если сначала сделаете шаг по преобразованию ваших плиток в линии. Например,

- - - - -
- X X X -
- X X - -
- X - - -
- - - - L

... будет сокращен до трех линий, соединяющих углы твердого объекта в треугольнике.

Затем сделайте то, что делает движок Doom 3: с точки зрения источника света рассмотрите каждую «стену», обращенную к свету. (В этой сцене будет рассматриваться только диагональная линия.) Для каждой такой линии спроецируйте ее в трапецию, передний край которой является исходной линией, стороны которой лежат на линиях, идущих от источника света через каждую конечную точку, а обратная сторона - далеко, мимо всей сцены. Итак, это трапеция, которая «указывает на» свет. Он содержит все пространство, на которое стена отбрасывает свою тень. Заполните каждую плитку этой трапеции тьмой.

Пройдите по всем таким линиям, и вы получите «трафарет», который включает в себя все плитки, видимые от источника света. Залейте эти плитки светлым цветом. Возможно, вы захотите осветить плитку немного меньше по мере удаления от источника («затухание») или заняться другими причудливыми вещами.

Повторите эти действия для каждого источника света в вашей сцене.

На самом деле я совсем недавно добавил эту функцию в один из своих проектов.

void Battle::CheckSensorRange(Unit* unit,bool fog){
    int sensorRange = 0;
    for(int i=0; i < unit->GetSensorSlots(); i++){
        if (unit->GetSensorSlot(i)->GetSlotEmpty() == false){
            sensorRange += unit->GetSensorSlot(i)->GetSensor()->GetRange()+1;
        }
    }
    int originX = unit->GetUnitX();
    int originY = unit->GetUnitY();

    float lineLength;
    vector <Place> maxCircle;

    //get a circle around the unit
    for(int i = originX - sensorRange; i < originX + sensorRange; i++){
        if (i < 0){
            continue;
        }
        for(int j = originY - sensorRange; j < originY + sensorRange; j++){
            if (j < 0){
                continue;
            }
            lineLength = sqrt( (float)((originX - i)*(originX - i)) + (float)((originY - j)*(originY - j)));
            if (lineLength < (float)sensorRange){
                Place tmp;
                tmp.x = i;
                tmp.y = j;
                maxCircle.push_back(tmp);
            }
        }
    }

    //if we're supposed to fog everything we don't have to do any fancy calculations
    if (fog){
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
        }
    }else{

        bool LOSCheck = true;
        vector <bool> placeCheck;

        //have to check all of the tiles to begin with 
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            placeCheck.push_back(true);
        }

        //for all tiles in the circle, check LOS
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            vector<Place> lineTiles;
            lineTiles = line(originX, originY, maxCircle[circleI].x, maxCircle[circleI].y);

            //check each tile in the line for LOS
            for(int lineI = 0; lineI < (int) lineTiles.size(); lineI++){
                if (false == CheckPlaceLOS(lineTiles[lineI], unit)){
                    LOSCheck = false;

                    //mark this tile not to be checked again
                    placeCheck[circleI] = false;
                }
                if (false == LOSCheck){
                    break;
                }
            }

            if (LOSCheck){
                Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
            }else{
                LOSCheck = true;
            }
        }
    }

}

Там есть некоторые дополнительные вещи, которые вам не понадобятся, если вы адаптируете их для собственного использования. Тип Place определяется просто как координаты x и y для удобства.

Функция линии взята из Википедии с очень небольшими изменениями. Вместо того, чтобы печатать координаты x y, я изменил его, чтобы вернуть вектор места со всеми точками в строке. Функция CheckPlaceLOS просто возвращает истину или ложь в зависимости от того, есть ли на плитке объект. С этим можно было бы сделать еще несколько оптимизаций, но это подходит для моих нужд.

Вот очень простой, но довольно эффективный подход, который использует линейное время для определения количества плиток на экране. Каждая плитка непрозрачна или прозрачна (это дано нам), и каждая может быть видимой или затененной (это то, что мы пытаемся вычислить).

Начнем с того, что отметим сам аватар как «видимый».

Затем мы применяем это рекурсивное правило, чтобы определить видимость оставшихся плиток.

1. Если плитка находится в той же строке или столбце, что и аватар, то она видна только в том случае, если соседняя плитка ближе к аватару видна и прозрачна.
2. Если плитка находится под углом 45 градусов по диагонали от аватара, она видна только в том случае, если соседняя диагональная плитка (по направлению к аватарам) видна и прозрачна.
3. Во всех остальных случаях рассмотрите три соседних плитки, которые ближе к аватару, чем рассматриваемая плитка. Например, если эта плитка находится в (x, y) и находится выше и правее аватара, то следует рассмотреть три плитки (x-1, y), (x, y-1) и (x- 1, у-1). Рассматриваемая плитка видна, если Любые этих трех плиток видимы и прозрачны.

Чтобы это работало, плитки должны быть проверены в определенном порядке, чтобы убедиться, что рекурсивные случаи уже вычислены. Вот пример рабочего упорядочивания, начиная с 0 (это сам аватар) и заканчивая подсчетом:

9876789
8543458
7421247
6310136
7421247
8543458
9876789

Плитки с одинаковым номером можно осматривать в любом порядке между собой.

В результате получается не красивое отбрасывание тени, но вычисляется правдоподобная видимость плитки.

Я реализовал поле зрения на основе плитки в одной функции C. вот: https://gist.github.com/zloedi/9551625

Я знаю, что это многолетний вопрос, но всем, кто ищет такой стиль, я хотел бы предложить решение, которое я однажды использовал для своего собственного рогалика; "предварительно рассчитанный" вручную угол обзора. Если ваше поле зрения от источника света имеет максимальное внешнее расстояние, на самом деле не так уж и много усилий, чтобы вручную нарисовать тени, созданные блокировкой объектов. Вам нужно нарисовать только 1/8 часть круга (плюс прямое и диагональное направления); вы можете использовать симмерти для остальных восьмых. У вас будет столько карт теней, сколько квадратов в этой 1/8 круга. Затем просто ИЛИ их вместе по объектам.

Три основных плюса для этого: 1. Это очень быстро, если все сделано правильно. 2. Вы сами решаете, как отбрасывать тень, не сравнивая, какой алгоритм обрабатывает лучшую ситуацию. 3. Никаких странных алгоритмов, вызванных крайними случаями, которые нужно как-то исправить.

Минус в том, что у вас действительно нет возможности реализовать забавный алгоритм.