[💬] 오늘 하루 효과적으로 시간 버린 썰 푼다

[로코복실한(dovecreative)]

어제 자기전에 잡생각을 하다가, 만약 패스파인더에서

이런 네트워크를 패스파인딩한다고 할 때 분기점이 없는 1, 2 노드들은 그냥 스킵하면 퍼포먼스가 좋아지지 않을까?

이 생각이 들어서 프로젝트에 있는 A* 기반 패스파인더를 개조하기로 했어.

기존에는 이렇게 정직하게 점들을 패스파인딩했어.

그렇다면 아이디어를 반영해서 수정한 패스파인더는 어떨까?

(빨간색이 패스된 점. 단순히 -0- 형식의 노드만 패스한 게 아니라, 막다른 길이거나 이미 탐색이 진행된 노드로 인해 탐색 지점이 하나가 되었을 경우도 패스함)

와 시@봉방거 속도 빨라진것 보소

이정도면 a*의 새로운 패러다임ㅇㅈ?

보기에는 속도가 빨라진 것처럼 보여도, 이건 한 과정을 0.1초에 나누어 표현한 실험이기 때문에 과정의 수가 줄어도 과정 자체에 걸리는 시간이 늘어났다면 실제로는 오히려 퍼포먼스가 악화된걸수도 있어. 한번 확인해볼까?

AStar 원본

40x40 사이즈, 소요시간 19, 29, 35, 18, 18 (ms)

평균 23.8ms 최소 18ms

개선된 AStar

동일 맵, 소요시간 23, 39, 22, 34, 44 (ms)

평균 32.4ms 최소 22ms

오히려 기존 알고리즘에 비해 1.3배 넘게 느려진 걸 확인할수 있어...

이 A*는 클래식 A*와 다르게 거리를 삼각법으로 계산해서 격자가 아닌 환경에서도 사용할 수 있도록 만들어졌는데, 이 때문에 휴리스틱 거리 계산을 줄이는게 최적화에 큰 도움이 될 거라고 생각했어.

하지만 -0- 식의 노드를 걸러내는 과정이 추가되다 보니 프로그램이 체크해야 하는 것도 많아지고, 원래는 하나였던 경로 저장 방법(이전 노드만 저장)이 열거형(분기 전까지의 노드를 전부 저장)으로 바뀌어서 실제로 생성된 객체 양과 처리해야 할 양이 오히려 더 많아지게 된 것 같아.

A*는 주변을 전부 검색하는 방식이라 한 객체에 대한 계산이 좀 늘어나더라도 계산해야 할 객체 수 자체가 줄어들면 전체적으로 성능 향상이 있지 않을까 했는데, 오히려 역효과였던 거지.

아무튼 이렇게 하루를 효과적으로 버릴 수 있었어. 너무 아깝지만 게임개발을 할 때는 잡생각을 하지 말고, 최적화할 시간에 구현부터 하자는 교훈을 다시한번 얻을 수 있었어 - 그리고 애초에 이거 할 시간에 JPS를 만들었으면 더 좋은 결과를 얻을 수도 있었겠지.

앞으로는 최적화는 출시를 먼저 하고 하려고 해. 지금은 아이디어 구현을 먼저 하고, 최적화는 출시 후에 나보다 똑똑한 사람들과 함께 하는게 아무래도 맞는거같아.

다음에는 다시 개발일지로 돌아올게!

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

[개발하는똥개(skten1234)]

너 게임 길찾기 알고리즘 때문에 많이 무거워?

[로코복실한(dovecreative)]

아니 사실 이 수정은 간단할줄 알았어 생각할때는 if문 조금만 쓰면 될줄알았거든 근데 해보니까 생각보다 너무 복잡한거야

[로코복실한(dovecreative)]

수정해야겠다는 필요성을 느낀 것도 게임이 느려져서라기보단 자기전에 잡생각이 떠올라서인데 그게 잘못된 결정이었다는걸 오늘 하루를 써서 배웠어

[개발하는똥개(skten1234)]

그래도 이런 고민 하는 시간이 있어야 성장하는듯

[로코복실한(dovecreative)]

[ㅆㅇㅆ(124.216)]

캬 똑똑하네

[로코복실한(dovecreative)]

뭐야 내 하루 돌려줘요

[채썰기고양이(miners11)]

[로코복실한(dovecreative)]

[로코복실한(dovecreative)]

지금 생각해보면 물리적으로 목적지에서 먼 지점에 추가 패널티를 주는 식으로 개조하면 특정 상황에서 좀더 효과적일 수 있겠다. 하지만 jps보다 효과적일것같진 않고, 또 실험에 들어가는 시간대비 효과도 크진 않을거같아서 해보진 않을려고.

[로코복실한(dovecreative)]

그말이 맞다

[쭈구리야(zzu9riya)]

[로코복실한(dovecreative)]

[에뚜(ssss4610)]

왜케 고수임

[로코복실한(dovecreative)]

망햇서요

[익명(hereticbyte)]

이런애들이 개똑똑한거, 누가 당연하다 말한거 끝까지 반박하고 파고들고 시도하면서 완전한 이해를 갖게됌

[ㅇㅇ 1(59.18)]

생각은 흥미로운데 결국 반복문에 if문 추가가 되는게 오히려 패널티가 되는거구나

[로코복실한(dovecreative)]

나 그래도 이게 좀 마음이 걸려서 딥프로파일링 돌려가지고 좀 개선함 보니까 개선된 패스파인더의 Update 부분에 Linq.ToArray() 부분이 부하가 많이 걸리더라고 그래서 이거 지우고 foreach문으로 바꿔주니까 보편적인 환경에서는 일반 버전보다 1.1배 느려짐. 대신 -0- 부분을 의도적으로 많이 넣은 맵에서는 두 배 이상 빨라지는 효과가 있더라. 그래서 완전 폐기하진 않고 특수한 경우에만 사용하려고.

[로코복실한(dovecreative)]

평소에 성능 생각은 많이 안하고 '가독성만 좋으면 되지' 주의였는데 이번 기회로 올바르게 함수들을 쓰는거에 대한 중요성을 더 알게됐다. 이제와서 생각해보면, 오늘이 버린 시간은 아니었어

[ㅇㅇ 1(59.18)]

결국은 연구한게 경험으로서 너의 개발 견문을 넓히는데 작든 크든 도움이 되는거니깐 좋은 방향이라고 생각해

[로코복실한(dovecreative)]

감사합니다 좋은 경험이었습니다...