글 수 56

A* 알고리즘 데모

조회 수 301 추천 수 0 2018.08.18 14:53:07


K-001.png

 

https://qiao.github.io/PathFinding.js/visual/

 

 

 

길찾기 인공지능의 가장 대표적인 A* 알고리즘 데모입니다. 오른쪽 하단에 있는 'Start Search' 버튼을 누르면 녹색에서 빨간색으로 가는 길을 보여줍니다. 마우스로 시작과 끝을 옮기거나 장애물도 추가할 수 있습니다. 현재 대부분의 게임에서 캐릭터를 이동하는데 이 방법을 응용하여 사용하고 있습니다.

 

보통 탐색을 하는 가장 쉬운 방법은 깊이우선/너비우선 탐색입니다. 깊이우선은 현재 위치에서 계속 한쪽 방향으로 연결을 찾다가 끝에 도달하면 바로 이전 위치로 돌아와 다른 연결로 이동합니다. 반대로 너비우선은 현재 위치에서 가로 방향으로 우선 찾고 그 다음 한단계 더 들어가 반복적으로 검색을 계속합니다.

 

만약 여기서 남산타워까지 가는 길을 알고 싶을때 깊이우선/너비우선 탐색으로는 시간이 너무 오래 걸립니다. 무식하게 모든 경로를 검사하기 때문입니다. 남산타워가 북쪽에 보인다면 굳이 남쪽 방향으로 먼저 찾을 필요가 없습니다. 중간에 길이 막혀 돌아가더라도 우선은 목표를 향해 가는 것이 더 효과적입니다. 이렇게 거리정보를 사용하는 방식이 A* 알고리즘의 특징입니다.

List of Articles
제목 글쓴이 날짜 조회 수
A* 알고리즘 데모 file 깊은바다 2018-08-18 301
FPS 전투가 가능한 인공지능 [4] 사지방컴 2018-05-13 370
블레이드 앤 소울과 게임 AI [1] 깊은바다 2018-03-14 360
인공지능과 게임 file 깊은바다 2018-03-02 342
FSM를 활용한 FPS게임 [2] 사지방컴 2017-10-02 527
넷마블 AI Lab 인터뷰 깊은바다 2017-09-29 387
강화학습 기반 NPC AI 깊은바다 2017-09-11 368
온라인 게임 속 로봇 경제와 내몰리는 인간 [1] 깊은바다 2017-05-16 197
딥러닝으로 게임 콘텐츠 제작하기 file 깊은바다 2017-05-11 548
유용한 게임 AI 기법 정리 깊은바다 2017-05-04 1981
다가오는 4차 산업혁명 시대의 게임개발 깊은바다 2017-04-27 177
초보자를 위한 A* 알고리즘 file 깊은바다 2017-04-16 621
딥러닝으로 스타크래프트 유닛 컨트롤 학습 깊은바다 2017-04-14 502
FSM을 사용한 인공지능 구현 예제 file [1] 깊은바다 2017-04-13 1332
실용적 예제로 본 게임 인공지능 소스코드 및 PDF 파일 깊은바다 2017-03-31 1179