선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 캐릭터가 시작지점에서 목표지점까지 장애물을 포함한 지형에서 가시성 검사를 수행하며, 장애물의 정점들을 이용하여 가시선을 생성한다. 가시성 검사는 장애물의 정점을 찾아 현재의 위치를 기반으로 목표지점에 가장 효율적으로 이동할 수 있는 위치를 탐색하는 것을 목적으로 한다. 가시성 검사에 의해 효율적인 정점이라고 판단된 위치는 현재의 위치에 연결선을 생성하여 가시선을 만든다.
- 본 논문에서는 3차원 게임에서 효율적인 경로 탐색을 위한 방법으로 가시성 검사를 이용한 경로 탐색기법을 제안한다. 본 논문에서 제안한 가시성 검사를 이용한 경로 탐색 기법은 3차원 게임이나 가상현실에서 경험적 탐색 기법보다 빠른 탐색 시간을 보장한 匸上 본 논문에서는 이동망으로 표현된 3차원 게임 지형에서의 효율적인 경로 탐색 방법을 제시한다.
- 본 논문에서는 이와 같은 문제를 해결하기 위해 이동망으로 표현된 3차원 장애물 지형에서 효율적인 경로 탐색을 수행할 수 있는 가시성 검사를 이용한 탐색 알고리즘을 제안한다. 가시성 검사를 이용한 탐색 알고리즘은 3차원 장애물 지형에 적합한 가시성 검사를 수행하여 3차원 장애물 지형의 탐색 공간을 축소시키며, 3차원 장애물 지형에서 캐릭터의 경로 탐색 속도를 향상시키고 빠른 탐색 연산을 위해 3차원 지형을 2차원으로 표현할 수 있도록 이동망을 구성한다.
제안 방법
- 데모 프로그램에서 3차원 지형과 장애물은 3DMax를 이용하여 생성하였고, 지형 공간은 다각형집합으로 표현하였다. 3차원 지형과 장애물들은 3DMax로 생성한 후, OpenGL상의 좌표 체계에 맞게 변환하였으며, 이렇게 생성된 3차원 지형을 이동망으로 활용하여 실험을 수행하였다.
- 있다. 가시성 검사를 이용한 탐색 알고리즘은 경로 탐색에 가장 많이 활용되는 경험적 탐색 알고리즘보다 효율적인 탐색 알고리즘이란 것을 몇 가지실험을 통해 확인하였다.
- 두 정점 V와 w가 서로 가시적이면 V와 w 를 연결했을 때 어떤 장애물도 통과하지 않는다. 가시성을 결정하기 위해서 평면상의 모든 정점들을 대상으로 가시성 검사를 수행한다. 만약에 정점 V에서 w 방향으로 가시선을 생성했을 때, 이 가시선이 정점 w에 이를 때까지 장애물의 내부와 교차하지 않는다면 정점 V와 W 사이에 가시적인 연결이 생성된다.
- 본 논문에서도 유사한 개념을 사용했다. 각각의 상태에 대해서 가시성을 테스트하고 두 정점 간의 가중치 정보는 경험적 탐색 기법의 추정 함수를 이용하여 계산하였다.
- 데모 프로그램에서 3차원 지형과 장애물은 3DMax를 이용하여 생성하였고, 지형 공간은 다각형집합으로 표현하였다. 3차원 지형과 장애물들은 3DMax로 생성한 후, OpenGL상의 좌표 체계에 맞게 변환하였으며, 이렇게 생성된 3차원 지형을 이동망으로 활용하여 실험을 수행하였다.
- 첫 번째 실험에서 장애물 지형을 생성할 때 다각형의 수량을 서로 다르게 하여 다각형의 수량에 따른 탐색성능을 비교 실험한다. 두 번째 실험에서는 지형을 생성할 때 사용하는 장애물의 사용 수량을 서로 다르게 하여 장애물 사용량에 따른 탐색 성능을 비교 실험한다.
- 본 논문에서 제시한 알고리즘은 기존의 가시성 그래프를 기초로 하고 있지만, 다양한 3차원 지형에 적용하기 위해서 기존의 방법처럼 간단하게 가시성 그래프를 생성하지 않는다. 또한 본 논문에서 제시한 알고리즘은 다양한 3차원 장애물 지형에서 경로 탐색을 수행하여 경로 계획을 수립한다.
- 가시성 검사를 이용한 탐색 알고리즘은 3차원 장애물 지형에 적합한 가시성 검사를 수행하여 3차원 장애물 지형의 탐색 공간을 축소시키며, 3차원 장애물 지형에서 캐릭터의 경로 탐색 속도를 향상시키고 빠른 탐색 연산을 위해 3차원 지형을 2차원으로 표현할 수 있도록 이동망을 구성한다. 또한, 시작지점에서 목표지점까지 효율적인 경로 탐색을 수행할 수 있도록 가시성 검사를 이용한 탐색에서는 지형에 대한 정보를 추정 함수에 적용하였으며, 지형 정보를 추정 함수에 적용시킨 가시성 검사를 이용한 탐색 알고리즘은 경험적 탐색 알고리즘보다 탐색 영역을 대폭 축소하면서 목표지점까지 효율적인 경로 탐색을 수행한다.
- 결과이다. 복합 장애물 지형 실험에서는 장애물의 수량을 변경하면서 경험적 탐색과 가시성 검사탐색에 대한 성능을 측정하였다. 지형T을 생성할 때 사용된 다각형은 2, 276개이고 장애물은 1개이다.
- 그러나 본 논문에서 제안한 알고리즘은 3차원 지형에서 경로 탐색을 수행할 수 있다. 본 논문에서 제시한 알고리즘은 기존의 가시성 그래프를 기초로 하고 있지만, 다양한 3차원 지형에 적용하기 위해서 기존의 방법처럼 간단하게 가시성 그래프를 생성하지 않는다. 또한 본 논문에서 제시한 알고리즘은 다양한 3차원 장애물 지형에서 경로 탐색을 수행하여 경로 계획을 수립한다.
- 제안한다. 본 논문에서 제안한 가시성 검사를 이용한 경로 탐색 기법은 3차원 게임이나 가상현실에서 경험적 탐색 기법보다 빠른 탐색 시간을 보장한 匸上 본 논문에서는 이동망으로 표현된 3차원 게임 지형에서의 효율적인 경로 탐색 방법을 제시한다. 기본적인 개념으로 가시성 그래프를 사용하였다[10-131 가시성 검사를 사용하여 탐색 공간을 축소시키면 많은 폴리곤을 사용하여 상세하게 지형을 표현했더라도 캐릭터는 매우 빠르게 이동경로를 탐색할 수 있다.
- 이러한 방법을 경로 탐색에 이용하면 경험적 탐색 기법보다 방문한 상태 수가 현저하게 줄어든다. 본 논문에서 제안한 가시성 검사를 이용한 경로 탐색 기법을 경험적 탐색 기법과 몇 가지 비교 실험을 통해 탐색의 효율성을 확인하였다.
- 본 논문에서 제안한 가시성 검사를 이용한 탐색기법을 적용한 캐릭터가 3차원 장애물 지형에서 이동할 때 경로 탐색 방법은 다음과 같다. 가시적인 점들 중 인접한 다음 상태에 도달하지 않는 점에서는 후속 상태(자식 상태)로 분기하지 않으며, 가시성 검사도 수행하지 않는다.
- 본 논문에서 제안한 알고리즘을 실험하기 위해 C++와 OpenGL을 사용하여 데모 프로그램을 구현하였다. 데모 프로그램에서 3차원 지형과 장애물은 3DMax를 이용하여 생성하였고, 지형 공간은 다각형집합으로 표현하였다.
- 첫 번째 실험은 여러 3차원 장애물 지형들에서 경험적 탐색 알고리즘과 본 논문에서 제안한 가시성 검사를 이용한 탐색알고리즘의 경로 탐색량에 대한 비교 실험이다. 첫 번째 실험에서 장애물 지형을 생성할 때 다각형의 수량을 서로 다르게 하여 다각형의 수량에 따른 탐색성능을 비교 실험한다. 두 번째 실험에서는 지형을 생성할 때 사용하는 장애물의 사용 수량을 서로 다르게 하여 장애물 사용량에 따른 탐색 성능을 비교 실험한다.
- 실험은 크게 두 가지로 나뉜다. 첫 번째 실험은 여러 3차원 장애물 지형들에서 경험적 탐색 알고리즘과 본 논문에서 제안한 가시성 검사를 이용한 탐색알고리즘의 경로 탐색량에 대한 비교 실험이다. 첫 번째 실험에서 장애물 지형을 생성할 때 다각형의 수량을 서로 다르게 하여 다각형의 수량에 따른 탐색성능을 비교 실험한다.
- 이와 같은 가시선을 기준으로 캐릭터는 최적화된 경험적 경로 탐색을 수행한다. 캐릭터가 가시선의 종점에 위치했을 때, 목표지점까지 최단 경로에 나타난 가장 가까운 다음 장애물의 정점을 찾아 가시선을 확장하고 가시성 검사를 수행하여 최적화된 경험적 경로 탐색을 수행한다. 이렇게 목표지점까지 가시성 검사와 가시선 생성 및 경로 탐색이라는 행위를 반복함으로써 캐릭터는 시작지점에서 목표지점까지 빠르게 이동할 수 있다.
- 본 논문에서 제안한 경로 계획 방법은 다음과 같다. 캐릭터가 시작지점에서 목표지점까지 장애물을 포함한 지형에서 가시성 검사를 수행하며, 장애물의 정점들을 이용하여 가시선을 생성한다. 가시성 검사는 장애물의 정점을 찾아 현재의 위치를 기반으로 목표지점에 가장 효율적으로 이동할 수 있는 위치를 탐색하는 것을 목적으로 한다.
대상 데이터
- 복합 장애물 지형 실험에서는 장애물의 수량을 변경하면서 경험적 탐색과 가시성 검사탐색에 대한 성능을 측정하였다. 지형T을 생성할 때 사용된 다각형은 2, 276개이고 장애물은 1개이다. 지형-1에서 경험적 탐색 알고리즘에서 탐색에 사용한 다각형의 총수는 1, 242개이고, 가시성 검사를 이용한 탐색 알고리즘에서 탐색에 사용한 다각형의 총수는 126개로 가시성 검사를 이용한 탐색이 우수한 성능을 나타냈다.
성능/효과
- 05%만을 활용하여도 목표지점까지 도달한다는 것을 나타낸다. 7개의 모든 지형에서 본 논문에서 제안한 가시성 검사를 이용한 탐색 알고리즘이 경험적 탐색 알고리즘보다 우수하게 나타났다.
- 이와 같은 문제점 때문에 가시성 그래프는 2차원 지형에서 주로 활용되었다. 그러나 본 논문에서 제안한 알고리즘은 3차원 지형에서 경로 탐색을 수행할 수 있다. 본 논문에서 제시한 알고리즘은 기존의 가시성 그래프를 기초로 하고 있지만, 다양한 3차원 지형에 적용하기 위해서 기존의 방법처럼 간단하게 가시성 그래프를 생성하지 않는다.
- 비교 실험한 결과 화면이다. 그림 9의 결과를 보더라도 본 논문에서 제안한 가시성 검사를 이용한 탐색 알고리즘이 경험적 탐색 알고리즘보다 다양한 형태의 장애물 지형들에서 많은 수의 불필요한 탐색을 줄여준다는 것을 알 수 있다.
- 본 논문에서 제안한 가시성 검사를 이용한 경로 탐색 기법은 3차원 게임이나 가상현실에서 경험적 탐색 기법보다 빠른 탐색 시간을 보장한 匸上 본 논문에서는 이동망으로 표현된 3차원 게임 지형에서의 효율적인 경로 탐색 방법을 제시한다. 기본적인 개념으로 가시성 그래프를 사용하였다[10-131 가시성 검사를 사용하여 탐색 공간을 축소시키면 많은 폴리곤을 사용하여 상세하게 지형을 표현했더라도 캐릭터는 매우 빠르게 이동경로를 탐색할 수 있다. 본 논문에서 제안한 가시성 검사를 이용한 경로 탐색 기법은 먼저 3차원 지형에 나타난 장애물의 가시적인 정점을 찾고, 이 정점을 경유한 목적지까지의 거리를 추정 함수(heuristic function)로 정의한다.
- 상태 총수에 따른 방문 횟수 비교실험에서 상태 총수가 증가하면 경험적 탐색은 상태방문 횟수가 매우 빠르게 증가하지만, 가시성 검사를 이용한 탐색은 완만하게 나타났다. 복합 장애물 지형에서의 방문 횟수 비교 실험에서는 경험적 탐색 알고리즘에 대한 가시성 검사를 이용한 탐색 알고리즘의 탐색 량 비율은 평균 9.38%를 나타냈으며, 장애물의 개수를 증가하여도 가시성 검사를 이용한 탐색 알고리즘은 효과적인 탐색 성능을 나타낸다는 것을 복합장애물 실험에서 확인하였다.
- 탐색 량은 메모리 사용과 탐색 시간에 많은 영향을 미치는 요소로, 탐색 량은 7개의 모든 지형 에서가 시성 검사를 이용한 탐색 알고리즘과 경험적 탐색알고리즘은 극심한 차이를 나타냈다. 본 논문에서 제안한 가시성 검사를 이용한 탐색 알고리즘은 다각형의 사용 수량이 증가하여도 탐색에 활용하는 다각형의 수량은 경험적 탐색 알고리즘에 비해 매우 적었다. 그림 10에 나타난 바와 같이 다각형 총수가 증가하면 경험적 탐색 알고리즘의 탐색량도 급격히 증가한다.
- 자세한 지형 생성에 따른 탐색 시간의 증가는 지형 생성에 강한 제약 조건으로 작용한다. 본 논문에서 제안한 가시성 검사를 이용한 탐색 알고리즘은 장애물이 설치된 3차원 장애물 지형에서 경험적 탐색에 비해 적은 탐색량으로 경로 탐색을 수행한다는 것을 본 실험으로 확인하였다.
- 본 논문에서 제안한 가시성 검사를 이용한 탐색알고리즘은 가시적인 영역에 있는 장애물의 정점을 먼저 탐색하기 때문에 불필요한 탐색을 줄여주는 장점이 있다. 가시성 검사를 이용한 탐색 알고리즘은 경로 탐색에 가장 많이 활용되는 경험적 탐색 알고리즘보다 효율적인 탐색 알고리즘이란 것을 몇 가지실험을 통해 확인하였다.
- 상태 총수에 따른 방문 횟수 비교 실험에서 가시성 검사를 이용한 탐색은 경험적 탐색에 비해 적은 상태 방문으로 목표지점에 도달하였으며, 경험적 탐색에 대한 가시성 검사를 이용한 탐색의 비율은 평균 9.41%를 나타냈다. 상태 총수에 따른 방문 횟수 비교실험에서 상태 총수가 증가하면 경험적 탐색은 상태방문 횟수가 매우 빠르게 증가하지만, 가시성 검사를 이용한 탐색은 완만하게 나타났다.
- 41%를 나타냈다. 상태 총수에 따른 방문 횟수 비교실험에서 상태 총수가 증가하면 경험적 탐색은 상태방문 횟수가 매우 빠르게 증가하지만, 가시성 검사를 이용한 탐색은 완만하게 나타났다. 복합 장애물 지형에서의 방문 횟수 비교 실험에서는 경험적 탐색 알고리즘에 대한 가시성 검사를 이용한 탐색 알고리즘의 탐색 량 비율은 평균 9.
- 83%를 나타내었다. 장애물의 수량이 증가되어도 가시성 검사를 이용한 탐색은 경험적 탐색에 비해 높은 탐색 효율을 나타낸다는 것을 복합 장애물 실험을 통해 알 수 있었다.
- 지형T을 생성할 때 사용된 다각형은 2, 276개이고 장애물은 1개이다. 지형-1에서 경험적 탐색 알고리즘에서 탐색에 사용한 다각형의 총수는 1, 242개이고, 가시성 검사를 이용한 탐색 알고리즘에서 탐색에 사용한 다각형의 총수는 126개로 가시성 검사를 이용한 탐색이 우수한 성능을 나타냈다. 지형T에서 경험적 탐색에 대한 가시성 검사 탐색 비율은 10.
- 지형Te 가장 적은 수량의 다각형들을 사용하였고, 지형-7은 가장 많은 수량의 다각형을 사용하여 생성하였다. 지형T에서 경로 탐색을 수행할 경우에 경험적 탐색 알고리즘은 전체 다각형 총수의 2585%를 활용하였고, 가시성 검사를 이용한 탐색 알고리즘은 전체 다각형 총수의 2.34%를 활용하였다. 탐색 량은 메모리 사용과 탐색 시간에 많은 영향을 미치는 요소로, 탐색 량은 7개의 모든 지형 에서가 시성 검사를 이용한 탐색 알고리즘과 경험적 탐색알고리즘은 극심한 차이를 나타냈다.
- 지형-1에서 경험적 탐색 알고리즘에서 탐색에 사용한 다각형의 총수는 1, 242개이고, 가시성 검사를 이용한 탐색 알고리즘에서 탐색에 사용한 다각형의 총수는 126개로 가시성 검사를 이용한 탐색이 우수한 성능을 나타냈다. 지형T에서 경험적 탐색에 대한 가시성 검사 탐색 비율은 10.14%로 나타났으며, 지형-6과 지형-7에서 경험적 탐색에 대한 가시성 검사 탐색 비율은 각각 9.29%와 9.83%를 나타내었다. 장애물의 수량이 증가되어도 가시성 검사를 이용한 탐색은 경험적 탐색에 비해 높은 탐색 효율을 나타낸다는 것을 복합 장애물 실험을 통해 알 수 있었다.
- 이용한 탐색의 방문 횟수를 비교 실험한 결과이다. 지형T을 생성할 때 사용된 다각형의 수량은 940개이며, 지형-1에서 경험적 탐색 알고리즘이 경로 탐색에 이용한 다각형 수량은 243개로 가시성 검사를 이용한 탐색 알고리즘보다 221개가 더 많았다. 즉, 가시성 검사를 이용한 탐색 알고리즘은 경험적 탐색 알고리즘에서 탐색한 상태의 9.
- 34%를 활용하였다. 탐색 량은 메모리 사용과 탐색 시간에 많은 영향을 미치는 요소로, 탐색 량은 7개의 모든 지형 에서가 시성 검사를 이용한 탐색 알고리즘과 경험적 탐색알고리즘은 극심한 차이를 나타냈다. 본 논문에서 제안한 가시성 검사를 이용한 탐색 알고리즘은 다각형의 사용 수량이 증가하여도 탐색에 활용하는 다각형의 수량은 경험적 탐색 알고리즘에 비해 매우 적었다.
후속연구
- 향후에는 가시성 검사를 이용한 탐색 알고리즘을 다면 경사도에서 적용할 수 있는 연구와 효율적인 경로 탐색을 위해 경로 탐색 시 에너지 대사율을 적용할 수 있는 연구가 필요하다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.