타일 기반 게임에서 켜진 타일 계산 ( "Raytracing")
https://stackoverflow.com/questions/174659
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 작은 타일 기반 게임을 작성하고 있습니다. 광원을 지원하고 싶습니다. 그러나 내 알고리즘 -FU는 너무 약해서 도움을 청합니다.
상황은 다음과 같습니다. 타일 기반 맵 (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 Development Community는 시야의 노선 분야 알고리즘에 대한 약간의 집착을 가지고 있습니다.
다음은 주제에 관한 Roguelike Wiki 기사에 대한 링크입니다.http://roguebasin.roguelikedevelopment.org/index.php?title=field_of_vision
로게 같은 게임의 경우 그림자 캐스팅 알고리즘을 구현했습니다.http://roguebasin.roguelikedevelopment.org/index.php?title=shadow_casting) 파이썬에서. 정리하는 것은 약간 복잡했지만 합리적으로 효율적으로 (순수한 파이썬에서도) 실행되었으며 멋진 결과를 생성했습니다.
"허용적인 시야"도 인기를 얻고있는 것 같습니다.http://rogebasin.roguelikedevelopment.org/index.php?title=permissive_field_of_view
다른 팁
폐색 등을 계산하여 모든 종류의 복잡성에 들어가거나 간단한 무차별 힘 방법을 사용할 수 있습니다. 모든 셀의 경우 다음과 같은 선 그리기 알고리즘을 사용하십시오. Bresenham 라인 알고리즘 현재 셀과 광원 사이의 모든 셀을 검사합니다. 채워진 세포 또는 (광원이 하나만있는 경우) 이미 테스트되어 그림자에있는 것으로 밝혀진 세포가있는 경우, 세포는 그림자에 있습니다. 조명으로 알려진 세포가 발생하면 셀이 켜집니다. 이에 대한 쉬운 최적화는 최종 결과가 무엇이든 줄을 따라 겪는 셀의 상태를 설정하는 것입니다.
이것은 내가 내에서 사용한 것입니다. 2004 IOCCC 우승 항목. 그러나 그것은 좋은 예제 코드를 만들지 않습니다. ;)
편집 : Loren이 지적한 것처럼 이러한 최적화로 맵의 가장자리를 따라 픽셀을 선택하여 추적으로 만 가져야합니다.
여기에 제시된 알고리즘은 내가 필요하다고 생각하는 것보다 더 많은 계산을하고있는 것 같습니다. 나는 이것을 테스트하지 않았지만 효과가 있다고 생각합니다.
처음에는 모든 픽셀을 조명으로 표시합니다.
맵의 가장자리에있는 모든 픽셀에 대해 : Arachnid가 제안한 것처럼 Bresenham을 사용하여 픽셀에서 빛으로 선을 추적하십시오. 그 선이 장애물에 부딪 치면 모든 픽셀을 가장자리에서 그림자에있는 장애물 너머로 표시하십시오.
빠르고 더러운 :
(배열이 얼마나 큰지에 따라)
- 각 타일을 통해 루프
- 빛에 선을 그립니다
- 라인의 전쟁이 X에 닿으면 그림자에 있습니다.
- (선택 사항) : 선이 통과하는 X의 양을 계산하고 그림자의 타일의 비율을 결정하기 위해 멋진 수학을합니다. NB : 임계 값 절차 중에 타일과 빛 사이의 선을 방지하여 타일과 빛 사이의 선을 방지하여 수행 할 수 있습니다. 사용 된 논리에 따라 타일이 그림자에있는 경우 (전혀) 잠재적으로 결정할 수 있습니다.
또한 테스트 된 픽셀을 추적 할 수 있으므로 솔루션을 조금 최적화하고 픽셀을 두 번 다시 테스트하지 않습니다.
라인이 반 투명하고 X 블록이 다시 반 트랜스 펜트 인 경우 이미지 조작을 사용하고 Pixles (타일) 사이에 직선을 그리는 것으로 돔일 수 있습니다. 이미지를 임계하여 라인이 'x'교차했는지 확인할 수 있습니다.
제 3 자 도구를 사용하는 옵션이 있으면 ID를 가져 가면됩니다. 장기적으로는 더 빨리 나타날 수 있지만 게임에 대해 덜 이해할 수 있습니다.
이것은 단지 재미를위한 것입니다 :
처음에 타일을 라인으로 변환하기위한 단계를 수행하면 Doom 3 접근 방식을 2D로 복제 할 수 있습니다. 예를 들어,
- - - - -
- X X X -
- X X - -
- X - - -
- - - - L
... 삼각형의 단단한 물체의 모서리를 연결하는 3 줄로 축소됩니다.
그런 다음 Doom 3 엔진이하는 일을하십시오. 광원의 관점에서 빛을 향한 각 "벽"을 고려하십시오. (이 장면에서는 대각선 만 고려 될 것입니다.) 그러한 각 선에 대해, 전면 가장자리가 원래 선인 사다리꼴로 투사하고, 그의 측면은 각 끝점을 통해 라이트 소스에서 라인에 놓여 있고 뒤쪽 인 멀리, 전체 장면을 지나서. 따라서 빛을 "가리키는"사다리꼴입니다. 벽이 그림자를 던지는 모든 공간이 들어 있습니다. 이 사다리꼴의 모든 타일을 어둠으로 채우십시오.
그러한 모든 라인을 진행하면 광원에서 볼 수있는 모든 타일이 포함 된 "스텐실"으로 끝납니다. 이 타일을 밝은 색으로 채 웁니다. 출처에서 벗어나 ( "감쇠") 다른 멋진 일을 할 때 타일을 조금 덜 조명 할 수 있습니다.
장면의 모든 광원에 대해 반복하십시오.
타일이 그림자인지 확인하려면 광원에 직선을 그려야합니다. 선이 점유 된 다른 타일을 교차 시키면 테스트중인 타일이 그림자에 있습니다. Raytracing 알고리즘은보기의 모든 객체 (케이스 타일)에 대해이 작업을 수행합니다.
그만큼 레이 트레이싱 기사 위키 백과에는 의사 코드가 있습니다.
다음은 화면 타일 수에서 선형 시간을 사용하는 매우 간단하지만 상당히 효과적인 접근 방식입니다. 각 타일은 불투명하거나 투명하며 (우리에게 주어진), 각각은 보이거나 음영 처리 될 수 있습니다 (즉, 우리가 계산하려는 것입니다).
우리는 아바타 자체를 "가시적"으로 표시하는 것으로 시작합니다.
그런 다음이 재귀 규칙을 적용하여 나머지 타일의 가시성을 결정합니다.
- 타일이 아바타와 동일한 행이나 열에있는 경우 아바타에 가까운 인접 타일이 보이고 투명한 경우에만 보입니다.
- 타일이 아바타에서 45도 대각선에있는 경우, 아바타쪽으로 이웃 대각선 타일이 보이고 투명한 경우에만 보입니다.
- 다른 모든 경우에, 해당 타일보다 아바타에 더 가까운 세 개의 인접 타일을 고려하십시오. 예를 들어,이 타일이 (x, y)에 있고 아바타의 오른쪽과 오른쪽에있는 경우 고려해야 할 3 개의 타일은 (x-1, y), (x, y-1) 및 (x-입니다. 1, y-1). 문제의 타일이 보입니다 어느 이 세 타일 중에서 눈에 띄고 투명합니다.
이 작업을 수행하려면 타일을 특정 순서로 검사하여 재귀 사례가 이미 계산되도록해야합니다. 다음은 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;
}
}
}
}
당신이 자신의 용도로 적응할 때 필요하지 않을 여분의 추가 물건이 있습니다. 유형 장소는 편의를 위해 X 및 Y 위치로 정의됩니다.
라인 함수는 매우 작은 수정으로 Wikipedia에서 가져옵니다. XY 좌표를 인쇄하는 대신 라인의 모든 지점이있는 장소 벡터를 반환하도록 변경했습니다. CheckPlacelos 함수는 타일에 객체에 객체가 있는지에 따라 true 또는 false를 반환합니다. 이것으로 수행 할 수있는 더 많은 최적화가 있지만 이것은 내 요구에 적합합니다.
나는 이것이 오래된 질문이라는 것을 알고 있지만,이 스타일의 물건을 검색하는 사람에게는 내 자신의 로관과 같은 솔루션을 한 번 사용하고 싶습니다. 수동으로 "사전 계산 된"FOV. 광원의 시야가 최대 외부 거리를 가지고 있다면 물체를 차단하여 생성 된 그림자를 손으로 끌어들이는 노력은 그리 많지 않습니다. 원의 1/8만을 그리면됩니다 (직선 및 대각선 방향). 다른 지그에 Symmerty를 사용할 수 있습니다. 원의 1/8 번째에 사각형이있는 Shadowmaps만큼 많은 Shadowmaps가 있습니다. 그런 다음 물체에 따라 그냥 또는 함께.
이에 대한 세 가지 주요 장점은 다음과 같습니다. 1. 제대로 구현 된 경우 매우 빠릅니다. 어떻게 든 수정
CON은 당신이 실제로 재미있는 알고리즘을 구현하지 않는다는 것입니다.
단일 C 함수에서 타일 기반 시야를 구현했습니다. 여기있어:https://gist.github.com/zloedi/9551625
이를 재창조/재 구현하기 위해 시간을 보내고 싶지 않다면 많은 게임 엔진이 있습니다. OGRE3D 사운드 및 게임 컨트롤뿐만 아니라 조명을 완전히 지원하는 오픈 소스 게임 엔진입니다.
