Подтвердить что ты не робот

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

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

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

Наглядное пособие, как это будет выглядеть примерно. L - источник света, Xs - это элементы, блокирующие свет, 0s - горящие плитки, а -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 - - - - - - -

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

(Конечно, было бы много источников света, но это всего лишь цикл.)

Любые участники?

4b9b3361

ОТВЕТЫ

Ответ 1

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

Здесь ссылка на статью о викторине 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

Ответ 2

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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

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

Ответ 5

Это просто весело:

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

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

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

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

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

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

Ответ 6

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

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

Ответ 7

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

Мы начинаем с обозначения самого аватара как "видимого".

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

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

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

9876789
8543458
7421247
6310136
7421247
8543458
9876789

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

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

Ответ 8

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

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

Edit:

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

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

Ответ 10

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

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

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

Ответ 11

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