[📚정보] QuadTree 만듦 + 패스파인딩 최적화 자료

[익명(125.248)]

큰맵에서 패스파인딩을 하고싶은데 프레임이 수직낙하 하는걸 보고 어떻게든 최적화 똥꼬쇼 한 결과를 쓰는 글임

https://www.redblobgames.com/pathfinding/grids/algorithms.html

윗 링크에 최적화 할려면

그리드의 표현방식을 그래프, 메쉬 형태로 바꾸거나

그리드 구조의 이점을 응용해 효율적으로 개조한다던가 

자료구조 Queue 마개조 등등으로 노드를 빠르게 통과하게 한다던가

마지막으로 휴리스틱을 향상시키라는데 아마 HPA*을 뜻하는 것 같다

HPA*는 노드 보단, 지역으로 길을 찾는데, 지역은 최소한 지정된 최소노드보다 큰 노드로

해당 지역과 지역을 잇는 '문'을 중점으로 그래프화한다.

더 자세히 알고싶으면 아래링크참조

https://harablog.wordpress.com/2009/02/05/hierarchical-clearance-based-pathfinding/

어쨋거나, 이중에 가장 효율적인게 노드의 갯수를 줄이는게 효율적이다

그래서 쿼드트리를 응용하기로 함 이유는 이름이 멋있어서

일단 장애물 측정하는 단계정도 만들었다

별건 없다만 충돌 노드의 반지름과 QuadTree의 노드의 반지름을 조절하는데 애를 먹었는데 결국 무식하게 충돌노드의 반지름에 반을 곱했다

일단 시간이 너무 늦어져서 여기까지, 내 미래가 이것들로 패스파인딩과 연결해줄꺼야

[익명(usnned)]

굳