5line

  Constrainted Delaunay Triangulation + A* + Simple Stupid Funnel를 합한 NavMesh다. 오늘날에 흔히 쓰이는 길찾기 휴리스틱 알고리즘를 만들 수 있어 기쁘다. 참 오래 걸린 알고리즘이였다, 4~6개월쯤 날렸나? 여기에 local avoidance, douglass peucker line simplication, 3D화(예시로 계단이라던가) ... 등등 해야할 것들이 많지만 이걸 만드느라 게임을 못 만들었기에 넘어가고 빨리 배운 걸 응용할거다 그래, 좀비생존게임이나 만들어볼까...

CDT는 모든 점 중에서 특정한 점들이 모여 만든 다각형들만 제외/분별하여 DT하는 알고리즘이다. 힘들었다. https://www.jdxdev.com/blog/2021/07/06/rts-pathfinding-2-dynamic-navmesh-with-constrained-delaunay-triangles/   https://forum.unity.com/threads/programming-tools-constrained-delaunay-triangulation.1066148/ 링크로부터 개념을 배워 적용하기에 많은 어려움이 있었다 일반적인 예로 작은 장애물 여러가지가 있는데 큰 장애물을 새로 덮어 씌울 때 어떻게 해야 하는가? 그 반대는 어떻게 처리해야 하는가? 게다가 정밀성 오류가 터지니 대체 어떤 곳이 틀렸는지 고생했다 결국에는 해당 알고리즘의 자료 구조를 능숙하게 아는 것이 중요하다 또 유닛 테스트는 가장 느려보이지만 먼 거리를 가장 빠르게 가는 방법이다 이런 값비싼 교훈을 얻었다.  디버깅 실력을 더 키워야겠다

이 알고리즘에 대해 설명하자면 직역해 들로네 삼각분할 이라 하고 주어진 모든 점으로부터 삼각형을 만드는데  전체적인 형태가 정삼각형인 것으로 해주는 것이다. 정보가 많아 구현하기 쉬웠다. 해깔리는 점들을 나열하자면 -  - 위키에서 Boyer-Watson식과 기본 Incremental식과 차이점, Incremental은 점을 포함하는 삼각형의 점들과 이어 만든 삼각형들에게 Flip을 적용하는 것이고 Boyer-Watson은 점을 포함하는 삼각형을 기점으로 주변을 살펴  점이 외접원에 포함되는 것만 따로 모은 삼각형들, 즉 나쁜 삼각형들에게  3변 하나씩 나쁜 삼각형들과 포함하지 않는 변들만 점과 이어 새로운 삼각형을 만든다. 두 방식들 모두 삼각형의 탐색방법에 따라 O(n^2) ~ O(nlogn) 정도 걸린다. - Mesh 데이터구조 HalfEdge 구조인데 시간을 아끼기 위해 충분한 이해 없이 무작정 베끼다가 오류가 터졌을 때 뭐가 틀렸는지 도저히 이해가 안돼 문제점을 찾을 때 까지 고생 좀 했다.  꽤 좋은 경험이였다.

절대 Simple하고 Stupid하지 않았다. 알고리즘을 만들어낸 사이트  를 찾아냈는데 봐도 이해를 못해 다른 웹사이트 로부터 그림으로 쉽게 설명해서 기본적인 이해도로 구현해봤는데 제대로 작동이 안됐다. 작동이 안되는 이유를 찾기위해 더욱 더 검색해 일본인 웹사이트  까지 번역기 돌려서 봤는데 내가 찾던 문제점과는 맞지 않았다. 결국 검색을 포기하고 수많은 시도 끝에 겨우 만들어 냈다. 이것도 어떠한 이유로 작동 안될 수도 있지만 전보다는 훨씬 낫기에 쓴다 답을 찾아 여기까지 온 불행한 영혼을 위해 설명은 영어로 썼다. GITHUB