타일 기반 게임에서 어떤 타일이 켜져 있는지 계산 ("raytracing")

Question

광원을 지원하고 싶은 타일 기반 게임을 작성하고 있습니다. 하지만 알고리즘이 너무 약하므로 도움을 청합니다.

상황은 다음과 같습니다. 타일 기반지도 (2D 배열로 유지)가 있으며 하나의 광원과 여러 항목이 주위에 서 있습니다. 어떤 타일이 광원에 의해 밝혀 졌는지 그리고 어떤 그림자에 있는지를 계산하고 싶습니다.

대략 보이는 모습을 시각적으로 보여줍니다. 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 개발 커뮤니티는 시야 (line-of-sight), 시야 (field-of-view) 알고리즘에 약간의 집착이 있습니다.

가 여기에 주제에 로그 류 위키 기사 링크입니다 : 내 로그 류 게임에 대한 http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

, 파이썬의 그림자 캐스팅 알고리즘 (http://roguebasin.roguelikedevelopment.org/index.php?title=Shadow_casting)을 구현했습니다. 함께 사용하는 것은 다소 복잡했지만 (심지어 순수 Python에서도) 효율적으로 실행되어 멋진 결과를 얻을 수있었습니다. http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

Answer 2

신속하고 더러운 : 라인의 pary가 안타

이

는 각 타일

을 통해

• 루프 (배열이 얼마나 큰지에 따라하는) 빛
• 에 선을 그립니다 X이면 그림자에 있음
• (선택 사항) : 그림자가있는 타일의 비율을 결정하기 위해 선이 지나가는 X의 양을 계산하고 멋진 수학을 계산합니다. 주의 : 타일과 빛 사이의 선을 앤티 앨리어싱 (anti-aliasing)하면됩니다 (따라서 광원을 따라 경로를 따라 다른 타일을 보았을 때). thresholding 절차 중에는 작은 변형으로 나타납니다. 사용 된 논리에 따라 타일이 그림자에 얼마나 많이 있는지 (잠재적으로) 결정할 수 있습니다.

픽셀을 테스트 한 트랙을 유지할 수 있으므로 솔루션을 조금 최적화하고 픽셀을 두 번 다시 테스트하지 마십시오.

이미지 조작을 사용하고 픽셀 (타일) 사이에 직선을 그리면 꽤 잘 될 수 있습니다. 선이 반투명하고 X 블록이 반투명이면 다시 돔이 될 수 있습니다. 선이 'X'를 교차했는지 확인하기 위해 이미지를 임계 값으로 설정할 수 있습니다.

타사 도구를 사용할 수있는 옵션이있는 경우 ID가 가져옵니다. 장기적으로 볼 때 더 빠를 수도 있지만 게임에 대해서는 더 적게 이해할 것입니다.

Answer 3

타일이 그림자에 있는지 확인하려면 광원에 직선을 다시 그려야합니다. 선이 점령 된 다른 타일과 교차하는 경우 테스트중인 타일이 그림자에 있습니다. Raytracing 알고리즘은 뷰의 모든 객체 (사례 타일)에 대해이 작업을 수행합니다.

위키 백과의 Raytracing article에는 의사 코드가 있습니다.

Answer 4

재발견/재 구현하기 위해 시간을 보내고 싶지 않다면 많은 게임 엔진이 있습니다. Ogre3D은 사운드 및 게임 컨트롤뿐만 아니라 조명을 완벽하게 지원하는 오픈 소스 게임 엔진입니다.

Answer 5

occlusion 등을 계산하여 모든 종류의 복잡성을 해결하거나 간단한 무차별 방식을 사용할 수 있습니다. 모든 셀에 대해 Bresenham Line Algorithm과 같은 선 그리기 알고리즘을 사용하여 현재 셀과 광원. 채워진 셀 또는 이미 검사를 마친 그림자에있는 셀이있는 경우 (하나의 광원 만있는 경우) 셀이 그림자에 있습니다. 불이 들어간 셀이 발견되면 셀도 마찬가지로 켜집니다. 이것에 대한 쉬운 최적화는 최종 결과가 무엇이든간에 라인을 따라 마주 치는 셀의 상태를 설정하는 것입니다.

이것은 내 2004 IOCCC winning entry에 사용 된 것입니다. 분명히 그것은 좋은 예제 코드를 만들지 못합니다. ;)

편집 : loren이 지적한 것처럼 이러한 최적화를 사용하면 추적 할지도 가장자리를 따라 픽셀을 선택하면됩니다.

Answer 6

TK의 솔루션은 일반적으로 이러한 종류의 작업에 사용되는 솔루션입니다.

부분 조명 시나리오의 경우 타일을 그림자로 만들면 그 타일을 4 개의 타일로 나눠서 각각의 타일을 테스트 할 수 있습니다. 너는 그걸 원하는만큼 나눌 수 있니?

편집 :

당신은 또한 빛에 인접한 타일 중 하나를 테스트하지하여 조금을 최적화 할 수 있습니다 -이 여러 광원이있을 때 어떻게하는 것이 더 중요 할 것 같아요 ...

Answer 7

여기에 제시되는 알고리즘은 필자에게 생각보다 많은 계산을 수행하는 것으로 보인다. 나는 이것을 테스트하지는 않았지만 작동한다고 생각합니다 :

처음에는 모든 픽셀을 켜짐으로 표시하십시오.

지도 가장자리의 모든 픽셀에 대해 : 거미류가 제안했듯이, Bresenham을 사용하여 픽셀에서 빛까지의 선을 추적합니다. 그 선이 방해물에 부딪치게되면 그 가장자리에서부터 방해물 바로 위에있는 모든 픽셀을 그림자로 표시하십시오.

Answer 8

이 단지 재미를위한 것입니다 :

"보기의 관대 한 필드는"뿐만 아니라 인기를 얻고있는 것 같다

처음 단계를 할 경우 2D에서 둠 3 (Doom 3) 접근 방식을 복제 할 수 있습니다

타일을 선으로 변환합니다. 예를 들어,

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

...은 삼각형의 솔리드 오브젝트 모서리를 연결하는 3 줄로 축소됩니다.

그러면 둠 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 위치로 정의됩니다.

줄 기능은 아주 작은 수정으로 위키 백과에서 가져 왔습니다. xy 좌표를 출력하는 대신 라인의 모든 점을 가진 위치 벡터를 반환하도록 바 꾸었습니다. CheckPlaceLOS 함수는 타일에 객체가 있는지에 따라 true 또는 false를 반환합니다. 이것으로 할 수있는 몇 가지 더 많은 최적화가 있지만 이것이 내 요구에 잘 맞습니다.

Answer 10

다음은 화면의 타일 수에 선형 시간을 사용하는 매우 간단하지만 효과적인 방법입니다. 각 타일은 불투명하거나 투명합니다 (우리에게 제공됨). 각 타일은 시각적으로나 음영으로 표시 될 수 있습니다 (우리가 계산하려고하는 것).

먼저 아바타 자체를 "표시"로 표시합니다.

그런 다음이 재귀 규칙을 적용하여 나머지 타일의 가시성을 결정합니다. 타일 ​​아바타 동일한 행 또는 열이면 아바타 인접 타일 가까이 볼 투명한 경우

1. 후 만 볼 수있다.
2. 타일이 아바타에서 45 도의 대각선에있는 경우 인접한 대각선 타일 (아바타쪽으로)이 보이고 투명하면 표시됩니다.
3. 다른 모든 경우에는 해당 타일보다 아바타에 더 가까운 3 개의 인접한 타일을 고려하십시오. 예를 들어,이 타일이 (x, y)에 있고 아바타의 오른쪽 위에있는 경우 고려할 세 타일은 (x-1, y), (x, y-1) 및 (x- 1, y-1). 문제의 타일은 인 경우 해당 타일 3 개 중이 보이고 투명하면 표시됩니다.

이 작업을 수행하려면 재귀 적 사례가 이미 계산되었는지 확인하기 위해 특정 순서로 타일을 검사해야합니다. 동일한 번호

9876789 
8543458 
7421247 
6310136 
7421247 
8543458 
9876789 

타일 자체 사이에 임의의 순서로 검사 될 수있다 : 다음과 카운트 업 (아바타 자체 임) 0부터 작업 순서의 예이다.

결과는 아름다운 그림자 - 주조가 아니지만 믿을만한 타일 가시성을 계산합니다.

Answer 11

단일 C 함수에서 tilebased 시야를 구현했습니다. 여기에 그것이있다 : https://gist.github.com/zloedi/9551625

Answer 12

나는 이것이 오래 된 질문 인 것을 안다. 그러나이 물건 스타일을 찾고있는 누군가를 위해 나는 나의 자신의 roguelike를 위해 한 번 사용했던 해결책을 제공하고 싶다. 수동으로 "미리 계산 된"FOV. 광원의 시야에 최대 외곽 거리가있는 경우 객체를 차단하여 생성 된 그림자를 손으로 그리는 데별로 노력하지 않습니다. 원의 1/8 (그리고 직선 및 대각선 방향)을 그려야합니다. 당신은 다른 것들을 위해 대머리를 사용할 수 있습니다. 당신은 1/8의 원에서 사각형을 가지고있는만큼 많은 그림자 맵을 갖게 될 것입니다. 그런 다음 객체에 따라 함께 OR합니다. 이것에 대한

세 가지 주요 장점은 다음과 같습니다 당신은 그림자를 캐스팅 할 방법을 결정받을 권리 2를 구현하는 경우 1. 그것은, 결코 핸들을 algorith하는 비교를 매우 빠르다없는 상황 최고의 3. 아니 이상한 algorith 당신이 어떻게 든 고쳐야 만하는 유도 된 엣지 경우

재미있는 알고리즘을 실제로 구현하지 않아도됩니다.