[📜일지] 댕댕이 서바이벌 #17 - 길찾기 (끝)

[태보미코(taebomico)]

개발일지 목록

#1 - 플레이어 기본 조작

#2 - 무기 기틀 세우기

#3 - 무기 종류 추가 및 업그레이드 구현

#4 - 기본 몬스터

#5 - 몬스터 스폰

#6 - 즉사 공격, 가까운 적 탐색, 데미지 표기

#7 - 플레이어 스텟

#8 - 성능 최적화 (움짤 주의)

#9 - Experience Point

#10 - 넉백 / 미티어 스트라이크

#11 - 경험치 및 레벨업 UI

#12 - HP / SP

#13 - 상호작용 / 타일맵

#14 - 활 무기 개선 및 추가 / 플레이어 팔로우

#15 - 패기 / 길찾기 (1)

#16 - 길찾기 (2)

지난 이야기

나름 열심히 머리를 써가며 길찾기 알고리즘을 구현한 뒤,

중간 개발일지 피드백으로 flow field pathfinding이라는 정보를 얻었었다.

하지만 여태까지 만든게 아깝기도 하고 처음부터 쭉 재귀로 찾는 것보다 낫지 않을까 싶어서

내 알고리즘으로 탐색하지 못하는 부분만 재귀적으로 탐색하도록 했다.

그렇게하여 완성된 것이 위 짤.

동작 자체는 99%는 방향이 잘 나오는데 간혹가다 조건이 엇갈리면 요상하게 나오는 경우가 생기긴 한다.

지난 개발일지를 작성하고 다시 한번 확인하면서 알게되었는데 찝찝해졌다.

시간이 없으니 그냥 넘어갈까 싶었는데, 댓글 중 디테일이 완성도를 높인다는 이야기를 듣고 한번 더 점검하게 되었다 !

Flow Field Pathfinding

간혹 방향이 이상하게 나오는 것은 조건만 확인해주면 되므로

일단 현재 아쉽게 느껴졌던 타일을 중복체크하는 것을 방지해볼까 생각했다.

지난 개발일지의 바로 이 좌하단 부분의 탐색한 부분을 또 탐색하는 문제 !

어떻게 해결할까 생각해본 결과 flow field 알고리즘은 BFS로 탐색하다보니 낮은 거리부터 탐색한다는 아이디어를 차용해

청록색 탐색 시작점을 가까운 거리부터 탐색해주면 되지 않을까? 생각했다.

이것을 해결할 방법으로는 현재 탐색 큐에서 낮은 거리 순으로 빼내는 것.

탐색 지점 삽입 또한 크기순이 아니므로 낮은 것을 빼도록 보장해주는 우선순위 큐를 사용하는 것이다 !

우선순위 큐

Priority Queue 자료구조가 C#에 있으므로 사용하기 위해 작성했는데, 없다.

이게 왜...? 없지...?

찾아보니 유니티의 닷넷 프레임워크는 c#이랑 동일한게 아니라는 듯 하다.

직접 구현해주도록 하자.

구현이라곤 했지만 기본적인 자료구조다보니 많은 자료가 존재해 구현이 간단했다.

혹시 필요하신 분이 계시다면 사용하면 좋겠다 !

public class PriorityQueue<T> where T : IComparable<T> { private readonly List<T> _heap; public PriorityQueue(int capacity) { _heap = new List<T>(capacity); } public int Count => _heap.Count; public void Enqueue(T item) { _heap.Add(item); var i = _heap.Count - 1; while (i > 0) { var parent = (i - 1) / 2; if (_heap[parent].CompareTo(_heap[i]) > 0) { (_heap[parent], _heap[i]) = (_heap[i], _heap[parent]); i = parent; } else { break; } } } public T Dequeue() { if (_heap.Count == 0) { throw new InvalidOperationException(); } var root = _heap[0]; _heap[0] = _heap[^1]; _heap.RemoveAt(_heap.Count - 1); var i = 0; var last = _heap.Count - 1; while (i < last) { var child = i * 2 + 1; if (child < last && _heap[child].CompareTo(_heap[child + 1]) > 0) { child++; } if (child > last || _heap[i].CompareTo(_heap[child]) < 0) { break; } (_heap[i], _heap[child]) = (_heap[child], _heap[i]); i = child; } return root; } }

내 입맛대로 작성했다.

T로 들어가는 자료형은 IComparable를 받아 구현해서 서로 우선순위를 비교할 수 있도록 해주면 된다.

잘 동작하겠지? 기대하며 실행 !

이전과 다르게 중복 탐색을 하지 않는다 !

성능을 체크해보자 !

각각 위가 우선순위, 아래가 기존이다.

타일 1만개를 체크했을 때 9000번 체크하던 것을 2400번으로 훨씬 줄어들었다 !

하지만 큐에 enqueue, dequeue가 잦다보니 정렬을 너무 많이 시도해 전체 동작 시간 자체는 증가해버렸다...

그렇다... 답은 근본대로 하는것...

원점으로

지금까지 구현한 것이 아깝긴 하지만 현재 내가 구현한 알고리즘은 일관성이 없다.

상황에 따라 최악 수행 시간이 중복 체크를 하며 너무나도 증가해버리는 것.

그냥 처음부터 BFS방식으로 구현해보자.

먼저 시작점부터 상하좌우로 체크해보자.

몬가 이쁜것 같다.

잘 동작하므로 대각선 방향이 최적지점이라면 각도를 계산해주자.

재귀는 간단하고 신인것 같다.

장애물을 배치하고 잘 동작하는지 봐주자.

탐색이 이상한 부분이 생겼다 !

이유는 왼쪽과 오른쪽이 모두 최소 거리이기 때문이었다.

위나 옆, 아래나 옆의 경우 중간 각도를 구해주면 되지만 양 옆인 경우 중간 각도를 구해버리면 서로 반대방향일 경우 원하지 않는 값이 나올 수 있다.

따라서 이런 경우에는 따로 체크를 해주자.

나는 현재 타일에서 가장 근접한 타일 방향을 Flag를 이용해서 나타내준 뒤

최종적으로 그 flag를 이용해 방향을 결정해주었고,

위 경우에 Flag값을 없애주는 방식으로 진행했다.

잘 동작하는 것 같은데...? 싶지만 콜라이더 대각선 방향에서 상하좌우4방향의 값을 합치다가 콜라이더로 박아버리는 현상이 발생한다.

아래 사진에서 자세히 볼 수 있다.

화면 중앙의의 우측 콜라이더 방향으로 향하는 타일

동그라미 친 부분에서도 보인다.

따라서 근처에 콜라이더가 있는 경우를 체크해주자.

콜라이더 닿는 부분은 방향이 상하좌우로만 향해버려 아쉽긴 하지만

간단한 로직을 위해, 어짜피 그다지 중요하지 않으므로 여기서 타협했다.

빨빨빨빨 움직여보자 !

이상한 방향 없이 잘 동작하는 것 같다 !

개발일지에서는 보여주기가 중요하기 때문에

근거리부터 프레임마다 채워나가도록 짤로 보여준것이고,

실제론 한프레임에 끝나는 작업이다.

성능 테스트

그럼 이제 가장 중요한 내 알고리즘보다 좋은지 체크해보자.

당연히 좋겠지만...

타일 1만개부터 체크해보자.

1만개의 타일 기준 10ms 정도 소요된다.

지난 개발일지를 보자.

지난 개발일지에서 총 15ms정도 소요되던 것을 생각하면 굉장히 빨라졌다 !

그럼 이제 딥 프로파일을 꺼보자.

딥 프로파일 시에는 함수 호출을 전부 체크하다보니 속도가 더 느려진다.

재귀적으로 진행하다보니 매우 느려졌을 것이라 예상된다.

1만개의 타일을 체크하는데 1ms도 소요되지 않는다.

충격 그 자체인것...

지금은 디버그 모드로 아마 빌드 시에는 내부적으로 최적화되어 더 빨라질 듯 싶다.

내가 사용할 1000개의 타일 기준으로 체크해보자.

딥 프로파일이 꺼지면 0.1ms밖에 소요되지 않는다 !

다익스트라는 신이고 BFS는 갓이다.

코드 길이도 매우 짧아져서 디버깅 시에도 편할 것 같다.

이게... 코딩의 즐거움 아닐까...?

다음으로 길찾기를 사용할 지형이나 만들어봐야겠따 !

[유타몰(ssamtoo)]

쵸고수

[태보미(taebomi)]

[소닉쫄따구테일즈(dcz3xv7zgu14)]

훗 저정도쯤은 뭐...(잘 모름)

[태보미(taebomi)]

dots로 구현하면 더더더 빠를까 궁금한거에요 !

[쉔가오랜(ads7080)]

난 이전에 길찾기A*같은거나 다익스트라 쓰다가 그냥 NavMesh 사용하는데 어느게 더 부하가 적으려나... 근데 맵 구조가 계속 바뀌면 이게 더 난거같기도 ㅋㅋㅋㅋ 개꿀인거같음

[태보미(taebomi)]

네브메시를 한번도 안써봐서 모르겠지만 네브메시보단 에이스타가 더 가벼울것 같아요. 몹 적으면 에이스타 사용하면 정교하게 길찾기가능하니 좋을것같고 몹 수가 굉장히 많으면 요방식이 좋은것 같더라고요. 보통 rts나 대규모 유닛 시뮬레이션 류가 이런 방식인듯?

[쉔가오랜(ads7080)]

가벼운거 써야겟당 안그래도 새로 기획한 게임은 몬스터수가 엄청 많다보니 ㅋㅋㅋ 지금 만드는 생존게임은 navmesh2d 사용중인데 갈아엎긴 그렇기도하고 몹이 엄청 대규모로 쏟아지는건 아니니 그대로 가야지 소스 퍼가염!

[태보미(taebomi)]

[불타는키보드(1bnmaker)]

[태보미(taebomi)]

[익명(59.25)]

상점 시간 멈출때 어케했서요? 말 안해주면 화낼거에요

[태보미(taebomi)]

저 아직 상점이 없는 것이에요... 하면 timescale로 하면 되는것이에요 !

[익명(59.25)]

업글할때 게임이 멈추는 거에요 그래서 물어본거에요

[태보미(taebomi)]

그것도 timescale로 처리 가능한거에요. 혹시 timescale이 0인데 움직인다면 움직이는 물체의 update문에서 움직임에 deltatime을 곱해주지 않아 발생한 문제에요.

[에뚜(ssss4610)]

[태보미(taebomi)]

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[태보미(taebomi)]

[익명(112.166)]

고오수!

[태보미(taebomi)]

[익명(59.25)]

이건 1:n 에서만 사용 가능한건가요? 모든 캐릭터한테 저걸 적용하면 컴퓨터 터지질거 같은거에요

[태보미(taebomi)]

제가 구현한 방식으로는 1:n만 가능한것이에요.
RTS같은데서는 타일 단위보다 더 큰 단위로 한번 최적화 해주며 하더라고요.
https://youtu.be/SIS03T_-W1E?t=30
https://youtu.be/ALL7AQ1MRas?t=353
그리고
방향은 간단하게 8방향만 사용하고 유닛이 맞춰서 스티어링 해주며 움직이고요.

[익명(59.25)]

너무 친절해서 납치하고 싶은거에요

[태보미(taebomi)]

[익명(220.70)]

자 이제 네이티브 코드로 포팅을 하면 존나 빠를거임

[태보미(taebomi)]

[익명(5q9jebg64g2q)]

와 언젠가부터 구현 내용은 이해 못하고 그냥 화면이 반짝거리는 것만 예쁘다~ 하며 바라보고 있네 ㅋㅋㅋ

[태보미(taebomi)]

저도 구현하면서 쳐다보다보면 좀 재밌는거에요.

[익명(219.250)]

충격 그 자체!!

[태보미(taebomi)]

[kimgilsu(j8230091)]

이런걸 으떡게 만드능교 ㄷㄷ - dc App

[태보미(taebomi)]

보기보다 넘나 간단한 알고리즘이었던것!!

[익명(115.95)]

진짜 천재임?

[태보미(taebomi)]

[익명(218.144)]

끝...? 출시추!

[태보미(taebomi)]

"길찾기" 끝!!!!!!!!! 출시하고...싶다...

[익명(175.123)]

개인적으로 맵에서 플레이어가 지나갈 수 없는 지형(돌)이 많지 않게 구성되면 더 좋을 것 같아요 비슷한 겜(예: 브롤슈터즈라는 모바일겜) 플레이할 때 도망가는 과정에서 길이 너무 쉽게 막히면 게임 흐름이 끊겨서 아쉽더라구요

[태보미(taebomi)]

감사합니다 ! 저도 공감하는 바인지라 테스트를 위해 배치한거고 실제 플레이에선 저런식으로 있진 않을거에요 ! 폐허, 농장, 호수 이런식으로 좀 거대하게 지형을 배치해줄 거고요 !

[익명(175.123)]

감사합니다 전체적인 그래픽이 아기자기하고 너무 이쁩니다 출시가 기다려지네요 ㅎㅎ

[태보미(taebomi)]

열심히 할게요 감사합니다 !

[익명(175.213)]

항잘 잘 보고 있어요..!

[태보미(taebomi)]

감사합니다...!

[익명(114.207)]

알고리즘을..직접구현..!!쩔어요..!!

[태보미(taebomi)]

[익명(220.126)]

미쳐따

[태보미(taebomi)]