2D에서 가시성을 결정하는 방법

Question

저는 AI 샌드 박스를 개발 중이며 모든 살아있는 엔티티가 볼 수있는 것을 계산하고 싶습니다.

규칙은 엔티티의 관점에서 모양의 가장자리 뒤에있는 것을 단순히 숨기는 것입니다. 나는 인공 지능에 대한 입력으로 하나 필요

alt text http://img231.imageshack.us/img231/2972/shadows.png

중 하나가 이동하면서 그래픽, 특정 기업을 위해 그것을 보여 ..

어떤 멋진 아이디어 : 이미지는 모든 것을 명확히?

가 가로 또는 세로로 이동할 수 VisionWave 객체를 생성 :

Answer 1

당신이 기업의 뷰를 차단하는 간단한 모양을 사용하는 경우는, 내가 구현 한 것을 이렇게 쉬운 방법이있다. 소스 좌표, 해당 점과 교차하는 두 선 및 소스 점으로부터의 거리를 사용하여 VisionWave을 정의 할 수 있습니다.

파도가 하나 있어야합니다. 하나는 위로, 하나는 아래로, 다른 하나는 오른쪽으로, 다른 하나는 오른쪽으로 기울어 져야하며,이를 정의하는 선은 1과 -1 (즉, X)의 기울기를 가져야합니다. 아래의 내 원유 도면은 > 문자로 표시된 하나의 웨이브 (오른쪽으로 이동)를 보여줍니다.

\ /
    \ /> 
    \/> 
    @ > 
    /\ > 
/ \> 
/ \ 

각 파도를 한 번에 한 픽셀 씩 전파하는 루프를 만듭니다. 웨이브를 전파하면 다음 작업을 수행하려고합니다.

1. 웨이브가 보이는 모든 픽셀을 표시로 표시합니다.
2. 파도가 닿는 픽셀 중 하나가 빛을 차단하면 파도를 2 개로 분할하고 각각을 재귀 적으로 전파하려고합니다.

나는 Roguelike에서 이와 같은 시스템을 구현했으며 매우 빠릅니다. 병목 현상에 대한 코드를 프로파일 링해야합니다.

당신이 매우 똑똑하다면 직선 대신 원형 파를 시도해 볼 수는 있지만 삼각법 계산으로 인해 더 빨라지는지 나는 알 수 없습니다.

Answer 2

사용자의 시점에 보이는 꼭지점을 결정한 다음 해당 꼭지점을 직선의 시점에 다시 투영하여 새로운 꼭지점을 만듭니다. 모양을 닫으면 보이지 않는 영역을 나타내는 다각형이 생성됩니다.

해당하는 3D에 대해서는 shadow volumes을 참조하십시오.

Answer 3

이 가장 빠른 알고리즘이 아니라 당신의 AI가 추가 분석을 위해 유용 할 수 있습니다 다각형 생산 : 각 선분에 대한

1. 엔티티와 두 끝점 사이의 각도를 계산합니다.
2. 각도별로 정렬하십시오.
3. 스위프 라인과 교차하는 선분을 추적하면서 360 ° 주변에서 "스윕"합니다. 세그멘트 시작 지점을 교차 할 때 해당 세그먼트를 세트에 추가합니다. 세그먼트 끝 지점을 넘으면 해당 세그먼트가 집합에서 제거됩니다.
4. 가장 가까운 선분은 보이는 것의 다각형을 형성합니다.다각형은 삼각형 슬라이 버의 합집합입니다.

나는이 설명이 잘되지 않습니다 실현,하지만 난 당신이 어떻게 작동하는지에 대한 감각을 얻기 위해 함께 재생할 수 있습니다 an online demo here 있습니다. 서클과 함께 작동하도록 확장하면 아마도 나쁘지 않습니다 (유명한 마지막 단어).