게임 프로그래밍
Received: July. 10. 2019 Revised: Nov. 12. 2019 Accepted: Nov. 13. 2019
Corresponding Author: Dong-Yeop Lee(Kongju National University) E-mail: [email protected]
※ 이 논문은 2018년 공주대학교 학술연구지원사업의 연구지원에 의하여 연구되었음
ISSN: 1598-4540 / eISSN: 2287-8211
Ⓒ The Korea Game Society. All rights reserved. This is an open-access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.otg/licenses/by-nc/3.0), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
휴리스틱 유전 알고리즘 경로 탐색에 광선 추적 알고리즘을 활용한 경로 최적화 연구※
고정운*, 이동엽**
공주대학교 게임디자인학과
[email protected]*, [email protected]**
Path Optimize Research used Ray-Tracing Algorithm in Heuristic-based Genetic Algorithm Pathfinding
Jung-Woon Ko*, Dong-Yeop Lee**
Dept. of Game Design, Kongju National University
요 약
휴리스틱 기반의 유전 알고리즘 경로 탐색(H-GAP)은 노드, 에지 정보를 필요로 하지 않기 때문에 기존 경로 탐색 알고리즘의 단점을 보완하고 빠른 속도로 경로 탐색을 수행할 수 있다.
하지만 H-GAP를 이용해 탐색한 경로는 비 노드 기반이기 때문에 불필요한 경로 정보가 포함 되어 탐색된 경로가 최적의 경로가 아닐 때도 있다. 본 논문에서는 H-GAP를 이용해 탐색한 경로를 최적화하는 알고리즘을 제안한다. 제안하는 알고리즘은 H-GAP의 경로 탐색이 완료된 후 광선 추적 알고리즘을 이용해 불필요한 경로 정보를 제거하여 경로를 최적화한다.
ABSTRACT
Heuristic based Genetic Algorithm Pathfinding(H-GAP), a method without the need for node and edge information, can compensate the disadvantages of existing pathfinding algorithm, and perform the path search at high speed. However, because the pathfinding by H-GAP is non-node-based, it may not be an optimal path when it includes unnecessary path information. In this paper, we propose an algorithm to optimize the search path using H-GAP. The proposed algorithm optimizes the path by removing unnecessary path information through ray-tracing algorithm after the H-GAP path search is completed.
Keywords : Heuristic(휴리스틱), Genetic Algorithm(유전 알고리즘), Pathfinding(경로 탐색),
Path Optimize(경로 최적화), Ray-Tracing(광선 추적)
1. 서 론
게임 산업에서 인공지능은 게임의 재미, 편의성 과 같은 여러 분야를 위해 활발하게 연구되고 있 다. 플레이어와 대적하는 인공지능 기반의 적이 플 레이어의 숙련도에 비해 숙련도가 너무 낮거나 높 다면 플레이어는 금방 흥미를 잃게 된다. 게임 개 발사는 플레이어의 게임 지속을 위한 성능 좋은 인공지능 개발에 많은 노력을 하고 있다[1,2].
특히 경로 탐색 알고리즘은 적 에이전트뿐만 아 니라 플레이어에게도 활용될 수 있기 때문에 많은 연구가 진행되고 있는 분야이다[3,4].
경로 탐색 알고리즘은 BFS, DFS, Dijkstra, A*
와 같은 것들이 있다. 그 중 게임에서 주로 활용되 는 경로 탐색 알고리즘은 경로에 대한 비용을 기 반으로 최단거리를 탐색하는 A* 알고리즘이다. A*
알고리즘은 출발노드로부터 현재노드까지의 거리 g(goal)값과 현재노드로부터 목표노드까지의 추정 된 거리 h(heuristic)값의 합이 가장 적게 나온 경 로를 선택하는 알고리즘으로 최단거리의 탐색 경로 를 제공한다. 하지만 이와 같은 경로 탐색 알고리 즘들은 맵에 존재하는 노드, 에지 정보를 데이터 공간으로 구성해야한다. 또한 맵의 크기가 크면 리 스트에 많은 양의 노드들을 저장하고 사용해야 되 기 때문에 월드의 크기가 방대하거나 가변적일 때 사용하기 용이하지 않다[5,6,7].
경로 탐색 알고리즘 중 하나인 휴리스틱 기반의 유전 알고리즘 경로 탐색(Heuristic-based Genetic Algorithm Pathfinding, H-GAP)은 노드, 에지의 정보를 필요로 하지 않으며, 휴리스틱 정보와 교배, 교차, 돌연변이, 진화 연산을 통해 해를 찾기 때문 에 월드의 크기가 방대하거나 가변적일 때 사용하 기 용이하다[8].
휴리스틱 유전 알고리즘 경로 탐색은 노드 정보 를 사용하지 않기 때문에 메모리를 최소화 할 수 있고, A* 알고리즘을 포함한 여러 경로 탐색 알고 리즘보다 빠른 시간 안에 경로를 탐색할 수 있다.
하지만 노드 정보를 사용하지 않기 때문에 탐색된
경로에 불필요한 경로 정보가 포함되어 목표지점까 지 더 멀게 돌아가는 단점이 있다[8].
본 논문에서는 휴리스틱 유전 알고리즘 경로 탐 색을 이용해 탐색한 경로를 최적화하는 알고리즘을 제안한다. 제안하는 알고리즘은 H-GAP의 경로 탐 색이 완료된 후 광선 추적 알고리즘을 이용해 이 동 경로 사이에 장애물이 존재하는지 검사하여 장 애물이 존재하지 않으면 불필요한 이동 경로 정보 를 제거하여 경로를 최적화한다.
제안하는 알고리즘의 효율성을 검증하기 위해 가로, 세로 20, 50, 100 크기의 장애물이 배치된 월 드에서 휴리스틱 유전 알고리즘 경로 탐색으로만 탐색하였을 때와 본 논문에서 제안하는 최적화 된 휴리스틱 유전 알고리즘 경로 탐색으로 탐색하였을 때를 실험하였다. 실험에는 경로를 탐색하는데 소 요된 시간과 최종 경로로 설정된 노드 수(경로의 이동 길이)를 비교하였다.
2. 선행연구
2.1 경로 탐색 알고리즘
경로 탐색 알고리즘은 시작지점에서 목표지점까 지 이동하는 경로를 여러 조건에 따라 탐색하는 알고리즘이다. 경로 탐색 알고리즘은 무정보 탐색 과 비용 기반 탐색으로 분류된다. 일반적으로 게임 에서 가장 흔하게 활용되는 경로 탐색 알고리즘은 비용을 기반으로 최단거리를 탐색하는 A* 알고리 즘이다.
2.2 휴리스틱 기반의 유전 알고리즘 경로 탐색
휴리스틱 기반의 유전 알고리즘 경로 탐색은 휴 리스틱 연산을 바탕으로 경로 탐색에 대한 초기 세대 염색체들을 생성한다[8].
생성된 세대는 경로 탐색을 수행하고, 탐색 결과
에 대해 평가를 받게 된다. 원하는 결과에 도달하
지 못했다면 유전자의 교배, 교차, 돌연변이 연산
을 거쳐 새로운 세대를 생성한다. 각 세대는 위 과 정을 반복하며 원하는 결과(목표지점으로 향하는 경로)에 도달하게 된다[9,10].
[Fig. 1] Heuristic based Genetic Algorithm Path-Finding
2.3 충돌 라인 검색
충돌 라인 검색(Collision Line Search)은 게임에서 은면 제거, 장애물 판별과 같은 곳에 사용되는 광선 추적(Ray Tracing) 알고리즘을 활용해 비 노드 기반의 경로 탐색을 수행하는 알고리즘이다[11,12].
본 논문에서는 휴리스틱 유전 알고리즘 경로 탐 색을 이용해 탐색한 경로를 최적화하기 위해 이동 경로 사이의 장애물 판별에 활용된다.
[Fig. 2] Ray-Tracing Algorithm
3. 본 론
기존의 H-GAP 알고리즘은 경로 탐색 속도가 빠르고 메모리를 최소화 할 수 있지만 노드 정보 를 사용하지 않기 때문에 탐색된 경로에 불필요한 경로 정보가 포함되어 목표지점까지 더 멀게 돌아 가는 단점이 있다.
본 논문에서 제안하는 알고리즘은 노드 정보가 없는 상황에서 기존의 H-GAP 알고리즘으로 탐색 된 경로 정보에 광선 추적 알고리즘으로 경로 후 처리 과정을 거쳐 이동 경로를 조금 더 최적화 하 는 알고리즘을 제안한다.
[Fig. 3] Flow Diagram for Path Optimize Algorithm
[그림 3]은 제안하는 알고리즘의 진행 과정으로 기존 H-GAP 알고리즘으로 경로 탐색이 완료된 이후에 진행된다.
P0 .. Pn의 경로 리스트는 탐색된 이동 경로 정
보이다. P0부터 순차적으로 광선 추적을 하여 충돌
하는 오브젝트가 존재하는지 판단하고, 충돌하는
오브젝트가 존재하지 않으면 다음 경로로 광선 추
적을 실시하고, 충돌하는 오브젝트가 존재하면 최
종 이동 경로 리스트에 포함시키는 방법으로 이동
시 거치는 경로의 개수를 줄여 이동 경로를 최적 화 한다.
3.1 광선을 이용한 경로 추적
current는 P 0 , Pindex는 P 1 부터 시작하며, current 노드에서 P Index 노드로 뻗어나가는 광선을 생성한다. 광선에 부딪히는 오브젝트가 있는지 검 사한다. 부딪히는 오브젝트가 없으면 previous 변 수에 P Index 노드 정보를 저장하고, index의 값을 증 가시켜 다음 이동 경로로 광선을 생성하여 경로를 최적화 하는 작업을 수행한다.
3.2 오브젝트 검출 및 최적화 된 경로 저장
광선에 부딪히는 오브젝트가 존재하고, 오브젝트 의 속성이 장애물이면 current 변수에 previous 정 보를 저장하고, OptimizedPathList에 preivous 정 보를 저장한다. 오브젝트의 속성이 목표 오브젝트 이면 최적화된 경로 리스트에 P Index 를 저장하고 알 고리즘을 종료한다.
[Fig. 4] Path Optimize Process
4. 실험 및 결과
본 논문에서 제안하는 알고리즘의 효율성을 검 증하기 위해 [그림 5]와 같이 가로, 세로 20, 50,
100 크기의 장애물이 배치된 월드에서 휴리스틱 유전 알고리즘 경로 탐색과 제안하는 최적화 된 휴리스틱 유전 알고리즘 경로 탐색을 실험하였다.
[Fig. 5] Game World (20, 50, 100)
실험은 동일한 월드, 위치에서 1000번씩 탐색을 진행하였고, 위치를 변경하며 총 100,000번의 경로 탐색을 진행하였다.
실험 결과는 경로 탐색에 소요된 시간과 최종 경로로 설정된 노드 수(경로의 이동 길이)를 비교 하였다.
[그림 6]은 가로, 세로 100 크기의 월드에서 경 로 탐색을 수행하였을 때의 결과 중 하나이다. 빨 간색은 휴리스틱 유전 알고리즘 경로 탐색으로 탐 색된 경로이다. 초록색은 충돌 라인을 이용해 경로 를 최적화하는 과정이며, 파란색은 제안하는 알고 리즘의 경로이다.
[Fig. 6] Path-Finding in game world (100x100)
4.1 경로 탐색에 소요된 시간
가로, 세로 20, 50, 100 크기의 장애물이 배치된 월드에서 휴리스틱 유전 알고리즘 경로 탐색으로 탐색하였을 때와 최적화 된 휴리스틱 유전 알고리 즘 경로 탐색으로 탐색하였을 때에 대해 각각 1000회씩 경로 탐색을 수행하였을 때 경로 탐색에 소요된 시간이다.
[Fig. 7] Required time in game world (20x20)
[Fig. 8] Required time in game world (50x50)
[Fig. 9] Required time in game world (100x100)
휴리스틱 유전 알고리즘 경로 탐색을 이용해 탐 색된 경로에 추가적인 알고리즘이 적용되는 것이기 때문에 제안하는 최적화 된 알고리즘의 탐색 소요 시간이 더 길다. 20x20 크기의 게임 월드에서 경 로 탐색을 수행했을 때 평균 소요 시간은 휴리스 틱 유전 알고리즘 경로 탐색 0.0203초, 제안하는 최적화된 경로 탐색 알고리즘 0.0205초로 소요 시 간의 차이가 0.0002초로 거의 차이 나지 않는다.
또한 50x50 크기의 게임 월드에서 경로 탐색을 수 행했을 때 평균 소요 시간은 휴리스틱 유전 알고 리즘 경로 탐색 0.170초, 제안하는 최적화된 경로 탐색 알고리즘 0.171초로 소요 시간의 차이가 0.001초 차이난다. 100x100 크기의 게임 월드에서 경로 탐색을 수행했을 때 평균 소요 시간은 휴리 스틱 유전 알고리즘 경로 탐색 0.167초, 제안하는 최적화된 경로 탐색 알고리즘 0.168초로 소요 시간 의 차이가 0.001초 차이난다.
4.2 최종 경로 노드 수 (경로의 이동 길이)
가로, 세로 20, 50, 100 크기의 장애물이 배치된 월드에서 휴리스틱 유전 알고리즘 경로 탐색으로 탐색하였을 때와 최적화 된 휴리스틱 유전 알고리 즘 경로 탐색으로 탐색하였을 때에 대해 각각 1000회씩 경로 탐색을 수행하였을 때 최종 경로로 설정된 노드 수(경로의 이동 길이)이다.
[Fig. 10] Path node count in game world (20x20)
[Fig. 11] Path node count in game world (50x50)
[Fig. 12] Path node count in game world (100x100)
20x20 크기의 게임 월드에서 경로 탐색을 수행 했을 때 최종 경로로 설정된 노드 수(경로의 이동 길이)는 휴리스틱 유전 알고리즘 경로 탐색 40개 (35m), 제안하는 최적화된 경로 탐색 알고리즘 15 개(27m)로 2.6배(1.29배) 이상 적게 설정되는 것을 확인할 수 있다. 또한 50x50 크기의 게임 월드에 서 경로 탐색을 수행했을 때 최종 경로로 설정된 노드 수(경로의 이동 길이)는 휴리스틱 유전 알고 리즘 경로 탐색 143개(140m), 제안하는 최적화된 경로 탐색 알고리즘 42개(73.6m)로 3.4배(1.9배) 이상 적게 설정되는 것을 확인할 수 있다.
100x100 크기의 게임 월드에서 경로 탐색을 수행 했을 때 최종 경로로 설정된 노드 수(경로의 이동 길이)는 휴리스틱 유전 알고리즘 경로 탐색 347개 (350m), 제안하는 최적화된 경로 탐색 알고리즘 25개(200m)로 13.8배(1.75배) 이상 적게 설정되는 것을 확인할 수 있다.
[그림 13]은 A*, H-GAP, H-GAP+Ray Tracing 알고리즘을 이용해 경로를 탐색 실험을 하였을 때 소요된 시간과 경로 길이의 평균을 정 리한 내용이다.
[Fig. 13] Different Path-Finding Algorithm Required Time & Path Length(Node Count)
5. 결 론
본 논문에서는 월드의 크기가 방대하거나 가변적인 환경일 때 빠른 속도로 경로를 탐색할 수 있는 휴리스 틱 유전 알고리즘 경로 탐색(Heuristic-based Genetic Algorithm Pathfinder, H-GAP)의 경로를 최적화할 수 있는 알고리즘을 제안하였다.
제안하는 알고리즘은 H-GAP의 경로 탐색이 완료된 후 광선 추적 알고리즘을 이용해 이동 경로 사이에 장 애물이 존재하는지 검사하여 장애물이 존재하지 않으면 불필요한 이동 경로 정보를 제거하여 경로를 최적화한 다.
제안하는 알고리즘의 효율성을 검증하기 위해 가로, 세로 20, 50, 100 크기의 장애물이 배치된 게임 월드에 서 기존의 휴리스틱 유전 알고리즘 경로 탐색과 최적화 된 휴리스틱 유전 알고리즘 경로 탐색의 실험을 진행하 였다. 실험 결과 두 알고리즘의 경로 탐색에 소요된 시 간은 미미한 차이를 보였으며, 최종 경로로 설정된 노드 수(경로의 이동 길이)는 본 논문에서 제안하는 알고리즘 을 활용할 때 월등히 감소하는 것을 확인할 수 있다.
향후에는 실제 게임 내의 플레이어, 적 에이전트의
이동에 알고리즘을 적용하여 실제 게임 속의 다양한 환
경에서 활용 가능하도록 연구를 진행할 것이다.
ACKNOWLEDGMENT
This research was financially supported by Kongju National University.
REFERENCES
![[그림 3]은 제안하는 알고리즘의 진행 과정으로 기존 H-GAP 알고리즘으로 경로 탐색이 완료된 이후에 진행된다. P0 .. Pn의 경로 리스트는 탐색된 이동 경로 정 보이다](https://thumb-ap.123doks.com/thumbv2/123dokinfo/4730723.511722/3.808.85.393.237.462/제안하는-알고리즘의-과정으로-알고리즘으로-탐색이-완료된-진행된다-리스트는.webp)
![[그림 13]은 A*, H-GAP, H-GAP+Ray Tracing 알고리즘을 이용해 경로를 탐색 실험을 하였을 때 소요된 시간과 경로 길이의 평균을 정 리한 내용이다.](https://thumb-ap.123doks.com/thumbv2/123dokinfo/4730723.511722/6.808.85.392.160.413/알고리즘을-이용해-경로를-실험을-하였을-소요된-시간과-내용이다.webp)
