Вычисление того, какие плитки освещены в игре на основе плиток ("raytracing")

Question

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

Ситуация выглядит следующим образом: есть карта на основе тайлов (хранится в виде двумерного массива), содержащая один источник света и несколько предметов, стоящих вокруг. Я хочу рассчитать, какие плитки освещены источником света, а какие находятся в тени.

Наглядное пособие о том, как это будет выглядеть приблизительно. L - это источник света, X - это элементы, блокирующие свет, 0 - освещенные плитки, а -s - плитки в тени.

0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -

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

(Конечно, было бы несколько источников света, но это просто петля.)

Кто-нибудь принимает?

Answer 1

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

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

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

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

Answer 2

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

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

Редактировать: Как указывает Лорен, с этими оптимизациями вам нужно всего лишь выбрать пиксели вдоль края карты для трассировки.

Answer 3

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

Это просто для удовольствия:

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

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

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

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

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

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

Answer 6

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

Мы начинаем с пометки самого аватара как «видимого».

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

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

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

9876789
8543458
7421247
6310136
7421247
8543458
9876789

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

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

Answer 7

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

Статья Raytracing в Википедии имеет псевдокод.

Answer 8

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

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

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

Answer 9

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

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 просто возвращает истину или ложь, основываясь на том, есть ли на плитке объект. С этим можно провести еще несколько оптимизаций, но это хорошо для моих нужд.

Answer 10

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

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

Edit:

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