최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기한국게임학회 논문지 = Journal of Korea Game Society, v.17 no.5, 2017년, pp.123 - 132
고정운 (공주대학교 게임디자인학과) , 이동엽 (공주대학교 게임디자인학과)
The path-finding algorithm refers to an algorithm for navigating the route order from the current position to the destination in a virtual world in a game. The conventional path-finding algorithm performs graph search based on cost such as A-Star and Dijkstra. A-Star and Dijkstra require movable nod...
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
A* 알고리즘의 문제점은 무엇인가? | A* 알고리즘은 출발노드에서 현재노드까지의 거리 g(goal)와 현재노드에서 목표노드까지의 추정거리 h(heuristic)의 합이 가장 작은 경로를 선택하기 때문에 사용자에게 최단거리의 경로를 제공할 수 있다. 하지만 맵에 존재하는 노드와 에지 정보를 데이터 공간으로 구성하여야 하며, 맵의 크기가 크면 A*가 경로 탐색에 사용하는 열린 목록(Open List)과 닫힌 목록(Close List)에 수천에서 수만 개의 노드들을 저장하기 위한 데이터 공간을 요구하기 때문에 많은 메모리 용량을 필요로 하며, CPU에 큰 부담이 가서 게임의 다른 연산에 제약적일 수 있다[7,8]. | |
경로 탐색 알고리즘은 무엇인가? | 경로 탐색 알고리즘은 이동 가능한 에이전트가 게임 내의 가상 월드에서 현재 위치로부터 목적지까지 가는 경로를 탐색하는 알고리즘을 뜻한다. 기존의 경로 탐색 알고리즘은 A*, Dijkstra와 같이 비용기반으로 그래프 탐색을 수행한다. | |
A* 알고리즘은 어떤 방식으로 최적의 경로를 탐색하는가? | A* 알고리즘은 월드 맵에 존재하는 에이전트가 현재 위치에서 목표지점으로 가는 경로 중 비용이 가장 적게 드는 경로를 탐색하는 알고리즘이다. A* 알고리즘은 비용 기반 그래프 탐색 알고리즘으로 월드에 있는 노드와 에지의 정보들을 비교하여 최적의 경로를 탐색한다. A* 알고리즘은 경로를 탐색하는 동안 출발 노드로부터 현재 머물고 있는 노드 n까지의 경로 비용을 나타내는 g(goal)와 노드 n으로부터 목표 노드까지의 경로 비용 추정치 h(heuristic) 값의 합 f(fitness)를 끊임없이 계산하여 f 값이 가장 적게 나온 경로를 선택한다[9]. |
J. E. Laird, "Using a computer game to develop advanced AI", 2001 IEEE Computer, July 2001.
Hyung-il Kim, "State based Context Awareness Method for Non-Player Character", Journal of Korea Game Society 2014, pp.93-102, Feb 2014.
Sung-lok Choi, "Fast Any-angle Path Planning on Grid Maps with Non-collision Pruning", 2010 IEEE International Conference, Dec 2010.
A. Nash, K. Daniel, S. Koenig, and A. Felner, "Theta*: Any-angle path planning on grids", in Proceedings of AAAI Conference on Artificial Intelligence(AAAI), 2007.
Myoun-jae Lee, "An Artificial Intelligence Evaluation on FSM-Based Game NPC", Journal of Korea Game Society 2014, pp.127-136, Oct 2014.
Eun-sol Kim, Hye-yeon Kim, Kyeon-ah Yu, "Implementation of Adaptive Navigation for NPCs in Computer Games", Journal of Korea Information Science Society 2016, pp.222-228, Feb 2016.
Sung-hyun Cho, "Reducing Search Space of A* Algorithm Using Obstacle Information", Journal of Korea Game Society 2015, pp.179-188, Aug 2015.
Abhilash Sreeramaneni, "A Real-Time Centralized Multi-Agent Pathfinding System using Systemized Iterative Deepening A*", The Graduate School of Seoul National University of Science and Technology, July 2015.
Jeong-won Ko, Sung-jun Park, "Path-Plan Algorithm using Collision Line Search Process", Proceedings of Korea Game Society Spring Conference 2012, pp.249-254, June 2012.
Myun-sub Lee, Byeong-heon Cho, Sung-hoon Jung, Yeong-rak Seong, Ha-ryoung Oh, "Performance Evaluation of Intelligent Characters for Fighting Action Games using Genetic Algorithms", Journal of Institute of Electronics Engineers of Korea 2004, pp.119-128, Dec 2004.
Hak-su Lee, Don-jung Choi, Hye-wuk Jung, Jee-hyong Lee, "Intelligent Tutoring System based on Genetic Algorithm", Proceedings of Korea Institute of Intelligent Systems Fall Conference 2010, pp67-69, Nov 2010.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.