Path finding 문서 원본 보기

[[분류: 경로 탐색]]

== 개요 ==
어떤 점 A에서 B로 캐릭터나 unit을 이동시키는 알고리즘을 말한다. Path Finding은 Shortest path problem과 밀접한 연관이 있다. 그래프 이론과 관련하여 어떤 경로가 최선의 경로인지를 파악하는 알고리즘이 Path Finding이다. 

== 노드들을 만드는 방법 ==
# Waypoints: 미리 정해진 waypoint를 이용하는 방식
# Precomputation: 미리 계산한 거리 벡터를 이용하는 방식
# Quantization: 게임의 공간을 나누는 방식
# Localization: 나뉘어진 공간에서 캐릭터의 위치를 기반으로 노드를 찾는 방식

== 종류 ==
# [[A*]] 알고리즘
# [[BFS]]
# [[TBA*]]
# [[LRTA*]]
# [[IDA*]]
# [[RIBS]]
# [[HPA*]]

== 참고 ==
https://qiao.github.io/PathFinding.js/visual/

https://www.kevanahlquist.com/osm_pathfinding/