2023/12/21 2
-
A*알고리즘을 이해하기 위해서는 Dijkstra 알고리즘을 이해해야 한다. 일반적으로, Dijkstra알고리즘은 A*알고리즘의 하위호환이라고 이해하면 될 것이다. Dijkstra 알고리즘 간선간 연결되어있는 노드들을 예시로 들어보자. 이제 각 거리간 시간이 걸리는 정도를 계산하고 넣어보자. 이제 여기에서 전방위 순환을 하면서 가장 가까운 거리를 찾는 것 이다. 위와 같은 방식을 비슷하게 사용하나, 더 효율적인 방법으로 A*알고리즘 이 있다. 근처 Node를 순환하면서 필요한 인접Node만 탐색하는 방식으로. 전체순환을 할 필요가 없어 더 효율적이다. 각 계산수식을 살펴보자. float AStar::GetDiagonalManhattanDistance(int start, int end) { Vector3 s..
-
그래프로 이루어진 맵에서 Point to Point간의 최단경로를 찾는데 사용되는 알고리즘 중 하나이다. 각 노드간의 가중치가 존재하는 그래프에서 사용된다. 먼저, F, G, H 개념을 이해해야 한다. F는 결과값으로, G + H를 의미한다. G는 Start-> Now까지의 가중치 이다. H는 Now-> End까지의 가중치 이다. Node는Index, F, G, H, State, From 값을 가진다고 가정한다. Index는 Node의 번호를 의미한다. 1번node, 2번node 등을 이야기 한다. State는 Open, Close의 상태 두가지를 가진다. From은 전 Node의 Index값을 가진다. Node는 생성시 항상 Open으로 둔다. 순서 출발 노드 선택 출발노드를 선택하고, 선택노드까지의 ..
