Optimization > Heuristic Optimization

Heuristic Optimization

휴리스틱 최적화를 사용하여 상당한 속도 향상을 얻는 방법에 대한 튜토리얼입니다.

경로 찾기 검색이 이루어질 때 일반적으로  heuristic 이 사용됩니다. 휴리스틱은 목표까지 얼마나 멀리 있는지를 대략적으로 추정하는 방법입니다. 일반적으로 실제  euclidean distance 를 직접 사용합니다. 이는 빠르고 일반적으로 상대적으로 좋은 결과를 제공하기 때문입니다. 하지만 작은 장애물만 있는 열린 공간이 아닌 세계에서는 이 추정이 좋지 않습니다. 그 결과, 휴리스틱이 더 나았더라면 필요하지 않았을 많은 노드를 검색하게 됩니다.

A* Inspector -> Settings -> Heuristic Optimization
휴리스틱 최적화 설정을 보유합니다.

Heuristic Optimization 참조

A* Pro 기능 이 기능은 A* Pathfinding Project Pro 기능입니다. 이 함수/클래스/변수는 A* Pathfinding Project의 무료 버전에는 존재하지 않거나 기능이 제한될 수 있습니다. Pro 버전은 여기에서 구매할 수 있습니다.

이 설정은  AstarPath.euclideanEmbedding 멤버에 해당합니다.

Results

이 기술은 목표를 찾기 위해 검색해야 하는 노드 수를 크게 줄일 수 있습니다. 이는 성능을 크게 향상시킬 수 있습니다.

아래의 두 이미지를 비교해 보십시오. 첫 번째 이미지에서는 이 최적화가 비활성화되어 있고, 두 번째 이미지에서는 활성화되어 있습니다. 두 번째 이미지에서는 검색이 더 정보에 기반하여 불필요한 방향을 피할 수 있습니다.

휴리스틱 최적화 비활성화

휴리스틱 최적화 활성화

Background

세계가 정적이거나 업데이트가 매우 드문 경우, 노드 간의 거리를 미리 계산하고 훨씬 더 나은 휴리스틱을 얻을 수 있는 기술을 사용할 수 있습니다. 이는 많은 경우 경로 찾기 성능을 10배 향상시킬 수 있습니다.

최적의 휴리스틱은 물론 그래프의 모든 노드 간 거리를 알고 있을 때입니다. 하지만 이는 계산에 오랜 시간이 걸리고 많은 공간을 차지하기 때문에 실용적이지 않습니다.

따라서 몇몇 노드(이후 "피벗 포인트"라 부름)를 선택하고 그 노드에서 그래프의 모든 다른 노드까지의 거리를 계산합니다. 이를 통해 꽤 좋은 휴리스틱을 계산할 수 있습니다.

사용된 휴리스틱과 관계없이, A* 알고리즘은 항상 최단 경로에 있을 수 있는 모든 노드를 검색합니다. 따라서 이 기술은 예를 들어 큰 열린 그리드 그래프에서 성능 향상을 제공하지 않습니다. 왜냐하면 경로 검색은 어쨌든 최단 경로의 노드보다 훨씬 더 많이 검색하지 않기 때문입니다.

아래 이미지는 완전히 비어 있는 그리드 그래프와 3개의 다른 최적 경로를 보여줍니다. 알고리즘은 녹색 영역에 있는 모든 노드를 검색해야 합니다. 왜냐하면 그들은 모두 동일한 길이를 가지고 있기 때문입니다. 그리드에서는 많은 최적 경로가 있기 때문에 모든 노드가 최적 경로에 있습니다.

A*  Pathfinding Project는 수동으로 선택하는 것보다 더 좋은 피벗 포인트를 자동으로 선택하는 알고리즘을 가지고 있습니다. 피벗 포인트를 수동으로 배치하는 것보다 무작위로 선택하는 것이 더 나은 경우가 많습니다.

Placing Pivot Points Manually

이 피벗 포인트를 배치할 때 중요한 점은 이들이 세계의 막다른 곳에 있어야 한다는 것입니다. 많은 경로가 피벗 포인트로 확장될 수 있고 여전히 최단 경로가 될 때 가장 잘 작동합니다.

아래 이미지에서 보라색으로 표시된 피벗 포인트를 볼 수 있습니다. 왼쪽 하단의 에이전트가 녹색 원으로 경로를 요청했습니다.

게임에 특정한 지식을 적용할 수도 있습니다. 예를 들어 TD 게임에서는 거의 모든 유닛이 단일 목표로 이동합니다. 따라서 목표에 단일 피벗 포인트를 배치하면 모든 경로가 훨씬 빠르게 계산됩니다. 왜냐하면 그 지점까지의 최적 거리가 이미 알려져 있기 때문입니다.

Placing Pivot Points Automatically

두 가지 모드가 있습니다. 무작위로 모든 포인트를 선택하거나, 가능한 한 서로 멀리 떨어져 있는 노드를 선택하는 알고리즘을 적용하는 것입니다. 두 번째 방법은 훨씬 높은 품질의 휴리스틱을 제공하지만, 초기 거리 계산을 직렬로 수행해야 하므로 계산 속도가 느립니다.

아래 이미지에서 무작위로 선택한 5개의 포인트와 서로 멀리 떨어진 5개의 포인트를 비교할 수 있습니다. 서로 멀리 떨어진 포인트는 막다른 곳이나 맵의 구석에 배치되는 경향이 있어 매우 좋은 결과를 제공합니다.

사용할 피벗 포인트의 수는 다양합니다. 가장 좋은 방법은 다양한 값을 시도해보고 어떤 것이 게임에 가장 적합한지 확인하는 것입니다. 피벗 포인트가 100개를 넘으면 검색할 노드 수가 줄어드는 이득보다 오버헤드가 더 커집니다. 1에서 100 사이를 권장하며, 다양한 값을 시도해보고 어떤 것이 가장 적합한지 확인하십시오.

게임 시작 시 경로 찾기가 작동할 때까지 지연이 발생할 수 있습니다. 이는 휴리스틱 조회를 사전 처리하느라 바쁘기 때문입니다. 이 지연이 문제가 된다면 "Random" 모드를 사용하거나 피벗 포인트 수를 줄이십시오.