컴퓨터 게임 환경에서 일반화 가시성 그래프를 이용한 경로찾기

유견아,전현주,Yu, Kyeon-Ah,Jeon, Hyun-Joo 한국시뮬레이션학회 2005 한국시뮬레이션학회 논문지 Vol.14 No.3

In state-of-the-art games, characters can move in a goal-directed manner so that they can move to the goal position without colliding obstacles. Many path-finding methods have been proposed and implemented for these characters and most of them use the A* search algorithm. When .the map is represented with a regular grid of squares or a navigation mesh, it often takes a long time for the A* to search the state space because the number of cells used In the grid or the mesh increases for higher resolution. Moreover the A* search on the grid often causes a zigzag effect, which is not optimal and realistic. In this paper we propose to use visibility graphs to improve the search time by reducing the search space and to find the optimal path. We also propose a method of taking into account the size of moving characters in the phase of planning to prevent them from colliding with obstacles as they move. Simulation results show that the proposed method performs better than the grid-based A* algorithm in terms of the search time and space and that the resulting paths are more realistic.

가중치 학습과 결합된 전술적 경로 찾기의 구현

유견아,Yu, Kyeon-Ah 한국시뮬레이션학회 2010 한국시뮬레이션학회 논문지 Vol.19 No.2

Conventional path-finding has focused on finding short collision-free paths. However, as computer games become more sophisticated, it is required to take tactical information like ambush points or lines of enemy sight into account. One way to make this information have an effect on path-finding is to represent a heuristic function of a search algorithm as a weighted sum of tactics. In this paper we consider the problem of learning heuristic to optimize path-finding based on given tactical information. What is meant by learning is to produce a good weight vector for a heuristic function. Training examples for learning are given by a game level-designer and will be compared with search results in every search level to update weights. This paper proposes a learning algorithm integrated with search for tactical path-finding. The perceptron-like method for updating weights is described and a simulation tool for implementing these is presented. A level-designer can mark desired paths according to characters' properties in the heuristic learning tool and then it uses them as training examples to learn weights and shows traces of paths changing along with weight learning.

컴퓨터 게임에서 전술적 경로 찾기를 위한 휴리스틱 학습

유견아 ( Kyeon Ah Yu ) 한국멀티미디어학회 2009 멀티미디어학회논문지 Vol.12 No.9

일반화 가시성그래프에 의해 계획된 경로이동 시뮬레이션

유견아,전현주,Yu, Kyeon-Ah,Jeon, Hyun-Joo 한국시뮬레이션학회 2007 한국시뮬레이션학회 논문지 Vol.16 No.1

최근 컴퓨터 게임에서 중대성이 부각되고 있는 NPC(NonPlayer Character)는 게임의 기본이 되는 이동에 있어서 스스로 장애물과 다른 캐릭터들을 인지하고 자신의 임무를 수행하여야 한다. NPC들의 자연스러운 이동을 위해 고정된 장애물 환경에서 일반화 가시성그래프를 이용하여 경로를 계획하는 방법이 제안된 바 있는데 본 논문에서는 이렇게 생성된 경로를 따라 효율적으로 이동할 수 있게 하기 위한 실행 모듈을 개발한다. 일반화 가시성그래프의 특성에 따라, 계획된 경로는 직선과 원의 호로 이루어져 있는데 본 실행 모듈에서는 이 특성에 적합하고 NPC의 움직임이 자연스럽도록 직선이동 동작, 원 이동 동작, 도착하기 등의 기본 조타 동작을 정의하여 실제 경로 이동의 실행에 이용한다. 또한 이동 중에 나타나는 동적 장애물을 감지하기 위해 충돌감지 기능을 실행 모듈에 포함시키며 감지된 장애물의 종류에 따라 선택적으로 대처하기 위해 의사결정나무를 이용한다. 실행 모듈을 테스트하기 위해 NPC의 경로 이동을 방해하는 다른 NPC가 등장하도록 예제 시나리오를 작성하여 시뮬레이션한다. The importance of NPC's role in computer games is increasing. An NPC must perform its tasks by perceiving obstacles and other characters and by moving through them. It has been proposed to plan a natural-looking path against fixed obstacles by using a generalized visibility graph. In this paper we develop the execution module for an NPC to move efficiently along the path planned on the generalized visibility graph. The planned path consists of line segments and arc segments, so we define steering behaviors such as linear behaviors, circular behaviors, and an arriving behavior for NPC's movements to be realistic and utilize them during execution. The execution module also includes the collision detection capability to be able to detect dynamic obstacles and uses a decision tree to react differently according to the detected obstacles. The execution module is tested through the simulation based on the example scenario in which an NPC interferes the other moving NPC.

출발점과 목표점을 일반화 가시성그래프로 표현된 맵에 포함하기 위한 빠른 알고리즘

유견아,전현주,Yu, Kyeon-Ah,Jeon, Hyun-Joo 한국시뮬레이션학회 2006 한국시뮬레이션학회 논문지 Vol.15 No.2

가시성그래프는 최소 탐색 공간으로 게임환경을 모델링하여 효과적으로 길을 찾을 수 있도록 하는 방법으로 잘 알려져 있다. 일반화 가시성그래프는 가시성그래프의 가장 큰 단점으로 지적되는 "벽-껴안기" 문제를 해결하기 위해 확장된 장애물의 경계 위에 생성된 가시성그래프이다. 일반화 가시성그래프에 의해 구해진 경로는 근사 최적이며 자연스럽게 보이는 장점이 있다. 본 논문에서는 변화하는 출발점과 목표점과 정적인 장애물 사이를 움직이는 게임 캐릭터에 효과적으로 일반화 가시성그래프를 적용하는 방법을 제안한다. 일반화 가시성그래프는 일단 생성되면 최소 탐색공간을 보장하지만 그 생성 자체는 노드사이의 링크의 교차 여부론 일일이 체크하여야 하므로 시간이 많이 소요된다. 아이디어는 먼저 정적인 장애물만으로 지도를 생성해 놓고 출발점과 목표점을 빠르게 포함시키는 것이다. 출발점과 목표점의 포함 부분이 여러 번 반복되어야 하는 과정이므로 출발점과 목표점을 빠르게 포함시키는데에 연산 기하학 분야의 회전 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.

로드맵 기반 경로에서의 그룹 이동 시뮬레이션

유견아,조수진,김경혜,Yu, Kyeon-Ah,Cho, Su-Jin,Kim, Kyung-Hye 한국시뮬레이션학회 2011 한국시뮬레이션학회 논문지 Vol.20 No.4

The roadmap-based planning is a path planning method which is used widely for a goal-directed movement in Robotics and has been applied to the world of computer animation such as computer games. However it is unnatural for computer characters to follow the path planned by the roadmap method as it is performed in Robotics. Flocking which is used for realistic and natural movements in computer animation enables character's movement by using a few simple rules without planning unlike the roadmap method. However it is impossible to achieve a goal-directed movement with flocking only because it does not keep states. In this paper we propose a simulation method which combines planning based on the road map with reactive actions for natural movements along the path planned. We define and implement steering behaviors for a leader which are needed to follow the trajectory naturally by analysing characteristics of roadmap-based paths and for the rest of members which follow the leader in various manners by detecting obstacles. The simulations are performed and demonstrated by using the implemented steering behaviors on every possible combination of roadmap-based path planning methods and models of configuration spaces. We also show that the detection of obstacle-collisions can be done effectively because paths are planned in the configuration space in which a moving object is reduced to a point. 로드맵 기반 계획은 목표 지향적인 이동을 위해 로보틱스 분야에서 많이 사용되는 경로 계획 방식이며 최근 컴퓨터 게임과 같은 컴퓨터 애니메이션 세계에서 많이 응용되고 있다. 그러나 컴퓨터 캐릭터가 로드맵 방식으로 계획된 경로 이동을 기존의 로보틱스 분야와 같은 방식으로 하면 자연스럽게 보이지 않는 단점이 있다. 컴퓨터 애니메이션 분야에서 실제적이고 자연스러운 이동을 가능하게 하는 플로킹은 로드맵과는 달리 계획에 의존하지 않고 몇 가지 규칙만으로 빠르게 캐릭터의 이동을 가능하게 하지만 상태를 갖지 않으므로 목표 지향적인 이동은 불가능하다. 그러므로 본 논문에서는 로드맵에 의해 경로를 계획하고 계획된 경로를 그룹이 자연스럽게 이동하도록 반응적 행동과 결합하여 시뮬레이션하는 방법을 제안한다. 이를 위해 로드맵 기반 경로의 특징을 분석하여 그룹의 리더가 자연스럽게 궤적을 추종하는데 필요한 조타 행동들과 나머지 멤버들이 주변 장애물 상태를 파악하면서 다양한 방법으로 리더를 따르도록 하는 조타 행동을 정의하고 구현하도록 한다. 구현된 조타 행동들을 이용하여 로드맵 기반 계획 방법들과 형상공간 모델링의 가능한 조합에 대해 이동 시뮬레이션하고 결과를 보여준다. 또한 경로 계획이 움직이는 물체는 점을 환산한 형상공간에서 이루어져 장애물 충돌 감지를 효과적으로 할 수 있음을 보여준다.

동적 장애물 회피를 위한 2단계 경로 계획 알고리즘

조수진(Su-Jin Cho),김경혜(Kyung-Hye Kim),유견아(Kyeon-Ah Yu) 한국정보과학회 2012 한국정보과학회 학술발표논문집 Vol.39 No.1B

본 논문에서는 로보틱스나 컴퓨터 게임 등의 다양한 분야에서 일반적으로 존재하는 동적인 환경에서 장애물 회피를 위한 경로 계획 알고리즘을 연구하였다. 제안하는 알고리즘은 전역 경로계획과 지역 경로계획의 두 단계로 이루어져 있고, A*와 가시성 그래프에 의해 구해진 전역 경로를 이동할 때에 동적 장애물을 감지하게 되면 이를 회피하기 위해 포텐샬장으로 지역 경로를 구성한다. 이 알고리즘은 포텐샬장을 A*와 결합함으로써 지역 최적화 문제를 해결하고 포텐샬장만으로 이동하는 경우에 비해 시간적인 측면에서도 더욱 효율적이다.

특징 추출 계층 재사용에 의한 효율적인 감성분석 앱의 개발

최수빈(Soo-Bin Choi),이지은(Ji-Oun Lee),이지은(Ji-Eun Lee),유견아(Kyeon-Ah Yu) 한국정보과학회 2018 한국정보과학회 학술발표논문집 Vol.2018 No.12

HUMAN : 분산 프로그래밍을 위한 이동에이전트 플랫폼

강미연(Mi-Yeon Kang),문미경(Mi-Kyung Moon),유견아(Kyeon-Ah Yu),정원호(Won-Ho Chung) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1A

이동 에이전트는 분산 응용에 있어서 네트워크의 부하와 대기시간을 줄일 수 있는 좋은 기술 중 하나이며, 다양한 네트워크 환경에 대한 유연성과 보안성 좋아 향후 기대되는 분산 응용 기반 기술이라 할 수 있다. 본 논문에서는, 이동 에이전트 기반의 다양한 분산 응용에 효율적으로 적용할 수 있는 이동 에이전트 플랫폼인 HUMAN이 설계 구현되었다. 이동 에이전트 플랫폼, HUMAN은 파일 탐색, 그룹 어드레싱, 다양한 여정 모드, 유연 응답 기능 등의 고급 유틸리티 등을 지원하고 있어, 에이전트 프로그래밍에 있어서 높은 수월성을 제공하고 있으며, 불법파일 탐색 등과 같은 분산 응용에 특히 유용할 수 있다. 또한 에이전트 등록, 해지 등을 위한 관리 서버 등을 제공하고 있어, peer-to-peer 관련 분산 응용 시스템의 개발에도 용이하게 적용할 수 있다는 장점을 가지고 있다.

그리드 기반 맵에서 꼭지점 정보를 이용한 휴리스틱의 설계

김지혜(Ji-Hyui Kim),정예원(Ye-Won Jung),유견아(Kyeon-Ah Yu) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.1

컴퓨터 게임 배경이 정교하게 표현되면서 그리드 기반으로 표현된 게임 맵에서 A* 알고리즘을 이용한 경로 찾기는 전체 게임 성능을 저해하는 요인이 되고 있다. 셀 단위의 세밀한 표현으로 상태 공간이 커져 탐색 시간이 증가하기 때문이다. 본 논문에서는 정규 그리드로 표현된 컴퓨터 게임 배경을 꼭지점 리스트로 된 다각형 기반 맵으로 변환하고 다각형의 꼭지점에 대한 가시성 정보를 이용하여 효율적인 경로 찾기가 가능하게 하는 방법을 제안한다. 다각형 기반 맵으로의 변환은 오프라인으로 전처리하여 실시간 쿼리에는 영향을 미치지 않도록 하며 꼭지점의 가시성 정보를 이용하는 휴리스틱을 설계함으로서 추정의 정확도를 높여 경로 탐색 시에 방문하는 노드수를 획기적으로 감소시키도록 한다. 시뮬레이션에서는 제안한 방법들이 그리드 기반 방식의 장점을 유지하면서 탐색 공간과 탐색 시간을 효율적으로 감소시킴을 확인한다. As computer game maps get more elaborate, path-finding by using A* algorithm in grid-based game maps becomes bottlenecks of the overall game performance. It is because the search space becomes large as the number of nodes increases with detailed representation in cells. In this paper we propose an efficient pathfinding method in which the computer game maps in a regular grid is converted into the polygon-based representation of the list of vertices and then the visibility information about vertices of polygons can be utilized. The conversion to the polygon-based map does not give any effect to the real-time query process because it is preprocessed offline. The number of visited nodes during search can be reduced dramatically by designing heuristics using visibility information of vertices that make the accuracy of the estimation enhanced. Through simulations, we show that the proposed methods reduce the search space and the search time effectively while maintaining the advantages of the grid-based method.