Вычисление того, какие плитки подсвечиваются в игре на основе плиток (“трассировка лучей”)
https://stackoverflow.com/questions/174659
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пишу небольшую игру на основе плиток, для которой я хотел бы поддерживать источники света.Но мой алгоритм-фу слишком слаб, поэтому я обращаюсь к вам за помощью.
Ситуация примерно такая:Существует карта на основе плиток (в виде 2D-массива), содержащая один источник света и несколько предметов, расположенных вокруг.Я хочу вычислить, какие плитки освещены источником света, а какие находятся в тени.
Наглядное пособие, приблизительно показывающее, как это будет выглядеть.Буква L - источник света, Xs - элементы, блокирующие свет, 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 - - - - - - -
Конечно, дробная система была бы еще лучше, когда плитка может находиться в полутени из-за того, что она частично затемнена.Алгоритм не обязательно должен быть совершенным - просто не заведомо неправильным и достаточно быстрым.
(Конечно, было бы несколько источников света, но это всего лишь цикл.)
Есть желающие?
Решение
В сообществе разработчиков 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
Другие советы
Вы можете столкнуться со всевозможными сложностями с вычислением окклюзии и т. д., или вы можете воспользоваться простым методом грубой силы: для каждой ячейки используйте алгоритм рисования линий, такой как Алгоритм линии Брезенхема , чтобы исследовать каждую ячейку между текущей и источником света. Если какие-либо ячейки заполнены или (если у вас только один источник света) уже проверены и находятся в тени, ваша ячейка находится в тени. Если вы встретите ячейку, которая, как известно, горит, ваша клетка также будет освещена. Легкая оптимизация заключается в том, чтобы установить состояние всех ячеек, с которыми вы сталкиваетесь на линии, до конечного результата.
Это более или менее то, что я использовал в своей победившей записи IOCCC 2004 года , Очевидно, что это не хороший пример кода, хотя. ;)
Редактировать. Как указывает Лорен, с помощью этих оптимизаций вам нужно только выбрать пиксели вдоль края карты для трассировки.
Представленные здесь алгоритмы, как мне кажется, выполняют больше вычислений, чем я считаю нужными. Я не проверял это, но думаю, что это сработает:
Сначала отметьте все пиксели как подсвеченные.
Для каждого пикселя на краю карты: как подсказал Арахнид, используйте Брезенхем, чтобы проследить линию от пикселя до источника света. Если эта линия ударяется о препятствие, пометьте все пиксели от края до непосредственно за препятствием как находящиеся в тени.
Быстро и грязно:
(В зависимости от того, насколько велик массив)
- Прокручивайте каждую плитку
- нарисуйте линию к Свету
- Если какая-либо часть линии попадает на X, то она находится в тени
- (Необязательно):вычислите величину X, через которую проходит линия, и выполните сложные математические вычисления, чтобы определить долю плитки в тени.Примечание:Это может быть сделано путем сглаживания линии между плиткой и источником света (поэтому при просмотре других плиток вдоль обратного пути к источнику света) во время процедуры определения порога они будут отображаться как небольшие аномалии.В зависимости от используемой логики вы потенциально можете определить, насколько сильно (если вообще) плитка находится в тени.
Вы также могли бы отслеживать, какие пиксели были протестированы, поэтому немного оптимизируйте решение и не проводите повторное тестирование пикселей дважды.
Это можно было бы сделать довольно хорошо, используя манипуляции с изображениями и рисуя прямые линии между пикселями (плитками) Если линии полупрозрачны, а блоки X снова полупрозрачны.Вы можете ограничить изображение, чтобы определить, пересекла ли линия букву "X"
Если у вас есть возможность использовать сторонний инструмент, то я, вероятно, воспользуюсь им.В долгосрочной перспективе это может оказаться быстрее, но вы будете меньше понимать свою игру.
Это просто для развлечения:
Вы можете повторить подход Doom 3 в 2D, если сначала сделаете шаг, чтобы преобразовать свои плитки в линии. Например,
- - - - -
- X X X -
- X X - -
- X - - -
- - - - L
... будет уменьшено до трех линий, соединяющих углы твердого объекта в треугольнике.
Затем сделайте то, что делает движок Doom 3: с точки зрения источника света рассмотрите каждую «стенку»; это сталкивается со светом. (В этой сцене будет рассматриваться только диагональная линия.) Для каждой такой линии спроецируйте ее в трапецию, передний край которой является исходной линией, стороны которой лежат на линиях от источника света через каждую конечную точку, а задняя часть далеко, мимо всей сцены. Таким образом, это трапеция, которая "указывает на" свет. Он содержит все пространство, на которое отбрасывает тень стена. Заполните каждую плитку в этой трапеции темнотой.
Перейдите по всем таким строкам, и в результате вы получите "трафарет". это включает в себя все плитки, видимые из источника света. Заполните эти плитки светлым цветом. Возможно, вы захотите осветить плитку немного меньше, когда будете уходить от источника («затухание») или делать другие причудливые вещи.
Повторите эти действия для каждого источника света в вашей сцене.
Чтобы проверить, находится ли плитка в тени, необходимо нарисовать прямую линию обратно к источнику света. Если линия пересекает другую занятую плитку, то тестируемая плитка находится в тени. Алгоритмы трассировки лучей делают это для каждого объекта (в вашем случае) в представлении.
В статье о трассировке лучей в Википедии есть псевдокод.
Вот очень простой, но довольно эффективный подход, который использует линейное время в количестве плиток на экране. Каждая плитка либо непрозрачна, либо прозрачна (это нам дано), и каждая может быть видимой или затененной (это то, что мы пытаемся вычислить).
Мы начинаем с того, что помечаем аватар как «видимый».
Затем мы применяем это рекурсивное правило, чтобы определить видимость оставшихся плиток.
<Ол>Для того чтобы эта работа работала, плитки должны проверяться в определенном порядке, чтобы убедиться, что рекурсивные случаи уже вычислены. Вот пример рабочего порядка, начиная с 0 (который является самим аватаром) и считая:
9876789
8543458
7421247
6310136
7421247
8543458
9876789
Плитки с одинаковым номером могут быть проверены в любом порядке между собой.
В результате получается не красивое отбрасывание теней, а вычисление правдоподобной видимости плитки.
Решение TK - это то, которое вы обычно используете для подобных целей.
Для сценария с частичным освещением вы могли бы сделать так, чтобы, если плитка оказывалась в тени, эта плитка затем разделялась на 4 плитки, и каждая из них тестировалась.Тогда вы могли бы разделить это столько, сколько захотите?
Редактировать:
Вы также можете немного оптимизировать его, не тестируя ни одну из плиток, прилегающих к источнику света - я думаю, это было бы более важно сделать, когда у вас несколько источников света...
Я только недавно написал эту функцию в один из моих проектов.
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 позиция для удобства.
Функция line взята из Википедии с очень небольшими изменениями. Вместо того, чтобы печатать координаты x y, я изменил его, чтобы он возвращал вектор места со всеми точками на линии. Функция CheckPlaceLOS просто возвращает истину или ложь, основываясь на том, есть ли на плитке объект. С этим можно сделать еще несколько оптимизаций, но это хорошо для моих нужд.
Я знаю, что это вопрос нескольких лет, но для любого, кто ищет этот стиль, я хотел бы предложить решение, которое я однажды использовал для собственного мошенничества; вручную "предварительно рассчитан" FOV. Если ваше поле зрения источника света имеет максимальное внешнее расстояние, на самом деле не так уж и много усилий, чтобы нарисовать тени, созданные блокированием объектов. Вам нужно только нарисовать 1/8 круга (плюс прямое и диагональное направления); Вы можете использовать Symmerty для других восьмых. У вас будет столько же теневых карт, сколько у вас будет квадратов в этой 1/8 части круга. Тогда просто или их вместе в соответствии с объектами.
Три главных плюса для этого: 1. Это очень быстро, если реализовано правильно 2. Вы сами решаете, как отбрасывать тень, не сравнивая, какой алгоритм обрабатывает, какая ситуация лучше 3. Никаких странных алгоритмов, порождающих крайние случаи, которые вы должны как-то исправить
Дело в том, что вы не можете реализовать забавный алгоритм.
Я реализовал поле обзора на основе плитки в одной функции C. вот: https://gist.github.com/zloedi/9551625
Если вы не хотите тратить время на то, чтобы заново изобретать / реализовывать это, существует множество игровых движков. Ogre3D - это игровой движок с открытым исходным кодом, полностью поддерживающий освещение, а также управление звуком и игрой.
