Calculando quais ladrilhos são iluminados em um jogo baseado em ladrilhos ("Raytracing")
https://stackoverflow.com/questions/174659
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou escrevendo um pequeno jogo baseado em azulejos, para o qual gostaria de apoiar fontes de luz. Mas meu algoritmo-fu é muito fraco, por isso eu vim a você em busca de ajuda.
A situação é assim: há um mapa baseado em ladrilhos (mantido como uma matriz 2D), contendo uma única fonte de luz e vários itens em pé. Quero calcular quais ladrilhos são iluminados pela fonte de luz e quais estão na sombra.
Uma ajuda visual de como seria, aproximadamente. O L é a fonte de luz, os Xs são itens bloqueando a luz, os 0s são ladrilhos iluminados e os -s são telhas na sombra.
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 - - - - - - -
Um sistema fracionário seria ainda melhor, é claro, onde um ladrilho pode ser de meia sombra devido a ser parcialmente obscurecido. O algoritmo não precisaria ser perfeito - apenas não obviamente errado e razoavelmente rápido.
(Claro, haveria várias fontes de luz, mas isso é apenas um loop.)
Algum dinâmico?
Solução
A comunidade de desenvolvimento de roguelike tem um pouco de obsessão por algoritmos de campo de visão e campo de visão.
Aqui está um link para um artigo da Wiki da Roguelike sobre o assunto:http://roguebasin.roguelikedevelopment.org/index.php?title=field_of_vision
Para o meu jogo de roguelike, implementei um algoritmo de elenco de sombras (http://roguebasin.roguelikedevelopment.org/index.php?title=shadow_casting) em Python. Foi um pouco complicado montar, mas corra razoavelmente eficiente (mesmo em python puro) e gerou bons resultados.
O "campo de visão permissivo" também parece estar ganhando popularidade:http://roguebasin.roguelikedesenvolvimento.org/index.php?title=permissive_field_of_view
Outras dicas
Você pode entrar em todos os tipos de complexidades com o cálculo da oclusão etc., ou pode optar pelo método de força bruta simples: para cada célula, use um algoritmo de desenho de linha, como o Algoritmo de linha de Bresenham Examinar todas as células entre a atual e a fonte de luz. Se houver células preenchidas ou (se você tiver apenas uma fonte de luz) que já foram testadas e encontradas na sombra, sua célula está na sombra. Se você encontrar uma célula conhecida por ser acesa, sua célula também será acesa. Uma otimização fácil para isso é definir o estado de qualquer célula que você encontrar ao longo da linha para qualquer que seja o resultado final.
Isso é mais ou menos o que usei no meu 2004 Entrada vencedora da IOCCC. Obviamente, isso não faz um bom código de exemplo. ;)
EDIT: Como Loren aponta, com essas otimizações, você só precisa escolher os pixels ao longo da borda do mapa para rastrear.
Os algoritmos que estão sendo apresentados aqui parecem estar fazendo mais cálculos do que eu acho que são necessários. Eu não testei isso, mas acho que funcionaria:
Inicialmente, marque todos os pixels como iluminados.
Para cada pixel na borda do mapa: como Arachnid sugeriu, use Bresenham para rastrear uma linha do pixel até a luz. Se essa linha atingir uma obstrução, marque todos os pixels da borda para logo além da obstrução como estando na sombra.
Rapido e sujo:
(Dependendo do tamanho da matriz)
- Loop através de cada ladrilho
- Desenhe uma linha para a luz
- Se qualquer pary da linha atingir um x, então está na sombra
- (Opcional): Calcule a quantidade de x a linha passa e faça matemática sofisticada para determinar a proporção do ladrilho na sombra. NB: Isso pode ser feito anti-aliasing a linha entre o ladrilho e a luz (portanto, olhando para outros ladrilhos ao longo da rota de volta à fonte de luz) durante o procedimento de limiar, eles aparecerão como pequenas anomólias. Dependendo da lógica usada, você pode determinar quanto (se é que existe), o ladrilho está na sombra.
Você também pode acompanhar quais pixels foram testados, otimizando a solução um pouco e não o teste de pixels duas vezes.
Isso pode ser muito bem cúpula usando a manipulação da imagem e desenhando linhas retas entre pixes (ladrilhos) se as linhas forem semi-transparentes e os blocos x são semi-transparentes novamente. Você pode limiar a imagem para determinar se a linha cruzou um 'x'
Se você tiver a opção de usar uma ferramenta de terceiros, provavelmente a aceitará. A longo prazo, pode ser mais rápido, mas você entenderia menos sobre o seu jogo.
Isso é apenas para se divertir:
Você pode replicar a abordagem do Doom 3 em 2D se fizer uma etapa para converter seus ladrilhos em linhas. Por exemplo,
- - - - -
- X X X -
- X X - -
- X - - -
- - - - L
... seria reduzido em três linhas conectando os cantos do objeto sólido em um triângulo.
Em seguida, faça o que o motor Doom 3 faz: da perspectiva da fonte de luz, considere cada "parede" que enfrenta a luz. (Nesta cena, apenas a linha diagonal seria considerada.) Para cada uma dessas linhas, projete -a em um trapézio cuja borda frontal é a linha original, cujos lados estão nas linhas da fonte de luz através de cada ponto final e cuja parte de trás está longe, além de toda a cena. Então, é um trapézio que "aponta para" a luz. Ele contém todo o espaço em que a parede lança sua sombra. Encha todos os ladrilhos deste trapézio com escuridão.
Prossiga em todas essas linhas e você acabará com um "estêncil" que inclui todos os ladrilhos visíveis da fonte de luz. Encha esses ladrilhos com a cor clara. Você pode iluminar o ladrilho um pouco menos à medida que se afasta da fonte ("atenuação") ou fazer outras coisas sofisticadas.
Repita para todas as fontes de luz em sua cena.
Para verificar se um ladrilho está na sombra, você precisa traçar uma linha reta de volta à fonte de luz. Se a linha cruzar outro ladrilho que está ocupado, o ladrilho que você estava testando está em sombra. Os algoritmos de Raytracing fazem isso para todos os objetos (no seu caso) na visualização.
o Artigo de Raytracing na Wikipedia tem pseudocódigo.
Aqui está uma abordagem muito simples, mas bastante eficaz, que usa tempo linear no número de ladrilhos na tela. Cada ladrilho é opaco ou transparente (que é dado a nós) e cada um pode ser visível ou sombreado (é isso que estamos tentando calcular).
Começamos marcando o próprio avatar como "visível".
Em seguida, aplicamos essa regra recursiva para determinar a visibilidade dos ladrilhos restantes.
- Se o ladrilho estiver na mesma linha ou coluna que o avatar, só será visível se o ladrilho adjacente mais próximo ao avatar for visível e transparente.
- Se o ladrilho estiver em uma diagonal de 45 graus do avatar, só será visível se o ladrilho diagonal vizinho (em direção ao avatar) for visível e transparente.
- Em todos os outros casos, considere os três azulejos vizinhos que estão mais próximos do avatar do que o ladrilho em questão. Por exemplo, se este ladrilho estiver em (x, y) e estiver acima e à direita do avatar, então os três ladrilhos a serem considerados são (x-1, y), (x, y-1) e (x- 1, y-1). O ladrilho em questão é visível se algum Desses três ladrilhos são visíveis e transparentes.
Para fazer isso funcionar, os ladrilhos devem ser inspecionados em uma ordem específica para garantir que os casos recursivos já sejam calculados. Aqui está um exemplo de ordem de funcionamento, a partir de 0 (que é o próprio avatar) e contando:
9876789
8543458
7421247
6310136
7421247
8543458
9876789
Ladrilhos com o mesmo número podem ser inspecionados em qualquer ordem entre si.
O resultado não é bonito, mas calcula a visibilidade de ladrilhos críveis.
A solução de TK é a que você geralmente usaria para esse tipo de coisa.
Para o cenário de iluminação parcial, você pode tê -lo para que, se um ladrilho resultar em sombra, esse ladrilho seja dividido em 4 azulejos e cada um deles é testado. Você poderia dividir isso o quanto quisesse?
Editar:
Você também pode otimizá -lo um pouco, não testando nenhum dos ladrilhos adjacentes a uma luz - isso seria mais importante quando você tiver várias fontes de luz, eu acho ...
Na verdade, eu recentemente escrevi essa funcionalidade em um dos meus projetos.
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;
}
}
}
}
Há algumas coisas extras que você não precisaria se estiver adaptando -as para seu próprio uso. O local do tipo é definido apenas como uma posição x e y por causa das conveniências.
A função de linha é retirada da Wikipedia com modificações muito pequenas. Em vez de imprimir coordenadas XY, mudei para devolver um vetor de local com todos os pontos da linha. A função CheckPlacelos apenas retorna verdadeira ou falsa com base se o ladrilho tiver um objeto nele. Há mais algumas otimizações que podem ser feitas com isso, mas isso é bom para minhas necessidades.
Sei que esta é uma pergunta de anos, mas para quem procura esse estilo de coisas, eu gostaria de oferecer uma solução que usei uma vez para uma mala direta; manualmente "pré -calculado" Fov. Se você o campo de visão da fonte de luz tiver uma distância externa máxima, não é realmente muito esforço para desenhar manualmente as sombras criadas bloqueando objetos. Você só precisa desenhar 1/8 do círculo (mais as direções retas e diagonais); Você pode usar o Symmerty para os outros resultados. Você terá tantos shadowmaps quanto quadrados naquele círculo 1/8 de um círculo. Então apenas ou eles juntos de acordo com os objetos.
Os três principais profissionais para isso são: 1. É muito rápido se implementado corretamente 2. Você decide como a sombra deve ser lançada, sem comparar qual algorith lida com qual situação é a melhor 3. Nenhum algorito estranho induziu casos de borda que você deve de alguma forma consertar
O golpe é que você realmente não pode implementar um algoritmo divertido.
Eu implementei campo de visão baseado em ladrilhos em uma única função C. aqui está:https://gist.github.com/zloedi/9551625
Se você não deseja gastar tempo para reinventar/reimplementar isso, há muitos motores de jogo por aí. OGRE3D é um mecanismo de jogo de código aberto que suporta totalmente a iluminação, além de controles de som e jogo.
