가시성그래프는 최소 탐색 공간으로 게임환경을 모델링하여 효과적으로 길을 찾을수있도록 하는 방법으로 잘 알려져 있
다.일반화 가시성그래프는 가시성그래프의 가장 큰 단점으로 지적되는“벽-껴안기” 문제를 해결하기 위해 확장된 장애물의
경계 위에 생성된 가시성그래프이다. 일반화 가시성그래프에 의해 구해진 경로는 근사 최적이며 자연스럽게 보이는 장점이
있다. 본 논문에서는 변화하는 출발점과 목표점과 정적인 장애물 사이를 움직이는 게임 캐릭터에 효과적으로 일반화 가시성그
래프를 적용하는 방법을 제안한다. 일반화 가시성그래프는 일단 생성되면 최소 탐색공간을 보장하지만 그 생성 자체는 노드
사이의 링크의 교차 여부를 일일이 체크하여야 하므로 시간이 많이 소요된다. 아이디어는 먼저 정적인 장애물만으로 지도를
생성해 놓고 출발점과 목표점을 빠르게 포함시키는 것이다. 출발점과 목표점의 포함 부분이 여러 번 반복되어야 하는 과정이므
로 출발점과 목표점을 빠르게 포함시키는데에 연산 기하학 분야의 회전 plane-sweep 알고리즘을 이용할 것을 제안한다. 시뮬레
이션 결과는 전체 그래프를 매번 생성하는 것보다 제안한 방법의 실행시간이 39%-68% 정도 향상되었음을 보여준다.The visibility graph is a well-known method for efficient path-finding with the minimum search space modelling
the game world. The generalized visibility graph is constructed on the expanded obstacle boundaries to eliminate
the “wall-hugging” problem which is a major disadvantage of using the visibility graph. The paths generated by the
generalized visibility graph are guaranteed to be near optimal and natural-looking. In this paper we propose the
method to apply the generalized visibility graph efficiently for game characters who moves among static obstacles
between varying start and goal points. Even though the space is minimal once the generalized visibility graph is
constructed, the construction itself is time-consuming in checking the intersection between every two links connecting
nodes. The idea is that we build the map for static obstacles first and then incorporate start and goal nodes quickly.
The incorporation of start and goal nodes is the part that must be executed repeatedly. Therefore we propose to use
the rotational plane-sweep algorithm in the computational geometry for incorporating start and goal nodes efficiently.
The simulation result shows that the execution time has been improved by 39%-68% according to running times
in the game environment with multiple static obstacles.