알고리즘

A* 알고리즘을 이용한 길찾기2 : Heap을 이용한 최적화

저번 포스팅에서 사용한 A* 알고리즘은 Cost_F가 가장 낮은 노드를 찾기 위해 매번 모든 열린 목록을 탐색해야 한다는 단점이 있었다. 이번 포스팅에서는 Heap(각 노드가 자식 노드를 최대 두 개씩 가지는 일종의 이진 트리 자료구조. 최대값과 최소값을 빠르게 찾아낼 수 있다)을 이용해 A* 알고리즘을 효율적으로 수정해 보았다. 코드는 다음과 같다. using System.Collections; using System.Collections.Generic; using UnityEngine; using System; public class Heap where T : IHeapItem { //노드 배열을 지정하는 대신 T유형의 배열을 지정 T[] Items; int CurrentItemCount; //힙은 ..

A* 알고리즘을 이용한 길찾기

A*(A star)알고리즘이란 출발점에서 목적지까지의 최단 거리를 찾는 알고리즘이다. 알고리즘을 테스트하기 위해 먼저 바닥과 벽을 씬에 배치했다. 대충 이런 느낌이다. Hierachy의 A*는 빈 게임 오브젝트로, 여기에 필요한 스크립트를 넣을 예정이다. 라는 이름으로 스크립트를 만들어준다. 스크립트는 오브젝트에 넣을 게 아니기 때문에 MonoBehaviour를 삭제해 준다. using System.Collections; using System.Collections.Generic; using UnityEngine; public class Node { public bool bWalkable; public Vector3 WorldPositon; public Node Parent; //현재 노드의 바로 직전 ..