[💬] 전쟁게임 알고리즘 구현 질문좀..

[Pawn(112.162)]

길찾기 알고리즘을 A*로 구현할까 싶은데
스타크래프트의 경우 어택땅을 해놓으면

1) 목적지로 간다.
2) 가는 도중 적이 있다면 적에게 다가간다.

3) 적이 죽는다면 다시 1)로 돌아간다.

가장 가까운적을 서칭하는건 목적지로 가는 동안 매 프레임마다 하는건가요?


또한 적이 죽었을경우 유닛들이 잠시잠시 멈추는데 그동안 적이 있는지 여부를 서칭하는건가요?


스타크래프트 전투 알고리즘을 아시는분 도움부탁드립니다 ㅠㅠ

[익명(119.194)]

대학교 과제라면 과제를 쉬운걸로 바꾸셈...시간낭비임. A*같은건 인터넷 소스 널려있으니 조금만 공부하면됨. 진짜 게임개발할거면 Navigation Mesh기능쓰고 collider에 적이 발견되면 적 죽이러 가는 걸로 처리해야지....유니티 언리얼에 모두 있음. 이미 있는 기능 직접 구현하는건시간낭비야....

[Pawn(112.162)]

그걸로 하니까 메모리를 너무 많이 잡아먹더라구요..

[익명(119.194)]

본인이 스스로 날코딩으로 만드실 정도면 본문같은 질문이 나올 일이 없으리라 넘겨짚고, 뉴비이실거 같아서 저렇게 답글을 달았는데 잘못 짚었나보네요. 넘겨짚어서 죄송합니다. 뻘쭘 ㅠㅠ 인디규모라는 가정하에 저라면 어떻게든 있는것 사용하겠습니다. 메모리 잡아먹는건 유닛에 불필요한게 들어있는건 아닌지, 메모리 관리가 이상한것 아닌지 따져보고, 그 문제가 아니면 기획 규모를 줄여야죠. 프로그래밍 잘하시면 아래 02020202님처럼 탐지 알고리즘을 직접 구현하셔도 상관없을 것 같긴한데.... 솔직히 구현까지는 한다쳐도 나중에 튜닝+디버깅단계에서 뒷감당할 자신이 없네요 전 ㅎㅎ

[Pawn(112.162)]

아닙니다.. 저도 너무 어려워서 찾고있는거라 ㅠㅠ 너무 감사합니다 이미 말씀해주신것만으로도 도움이 많이 됐습니다 감사합니다!!

[익명(211.206)]

스갤가서 물어보셈

[Pawn(112.162)]

하앍..

[02020202(jyoug2)]

저도 물리엔진쓰면 너무 무거워서 자주 직접 구현하는데, 주변 적 채크구현할때는 쿼드트리를 사용했습니다. 4각형 맵을 계속 4등분시켜서 몹의 사거리에 맞춰 깊이를 정하고 해당 뎁스, 구역안에 배치된 적들을 탐색하는 식으로 하였는데 분할경계에 서있을때 예외가 생기기는 해도 성능이 잘 나오더라구요.

[Pawn(112.162)]

경계분할을 해야하는게 맞겠죠?.. 스타크래프트도 경계를 계속 분할하던데..

[02020202(jyoug2)]

스타 구현에 대한 정보가 없어 죄송합니다.. 만족스런 구현하시길 바라요 :>

[Pawn(112.162)]

네넵 감사합니다!!

[익명(211.46)]

저도 스타크래프트 길찾기에 대해 엄청 많은 고민을 했었는데 일단 경계분할을 스타크래프트처럼 상황에 맞춰하는 알고리즘은 도저히 머리로는 못짜겠더라구요 지형에 따라 알아서 "리전"이 나뉘어야하는데 그걸 하는법을 아무리 고민하거나 구글링해봐도 잘 모르겠었고.. 그래서 그냥 256*256의 맵이라면 32*32 크기의 큰 타일 8*8 정도로 나눈다거나 하는 방식으로 크게 지역을 분할해서, 오브젝트 리스트를 그 타일에 귀속시켜서 관리하면서 길찾기는 처음 로딩할 때 큰 타일의 가운데를 기준으로 주변 8타일로 가는 최단경로를 탐색해서 저장해두고,

[익명(211.46)]

만약 이동 명령이 큰 타일 1개의 거리보다 길게 찍히면 그 타일과 타일의 경로를 무조건 따라가게 하는 방식으로 했어요 실제 스타크래프트도 리전 나누기 방식이지만 비슷한 방식을 사용하구요 그리고 적 탐색 같은 거 할 때도 쿼드트리 사용하거나 주변 큰 타일에 들어있는 오브젝트 리스트만 갖고 탐색하면 아무래도 빠르구요 스타가 다수 vs 다수의 길찾기와 적탐색을 계속 실행하다보니까 메모리관리나 실행시간 최적화가 진짜진짜 힘들더라구요 많이 고민해보셔요

[Pawn(112.162)]

말씀만 들어도 고민을 엄청 하신 티가 나네요.. 2d 네비게이션으로 구현을 하고 있다가 적 탐색 알고리즘 최적화를 어떻게 해야할지 모르겠어서 멈춘 상태긴한데 역시 쉬운부분이 아니었군요... 다들 어렵다해주시니까 오히려 나만그런게 아니구나 하면서 힘이 납니다. 감사합니당.

[익명(211.46)]

좀 정리하면 1. 클릭하는 순간만 길찾기를 실행, 매 프레임 이걸 하면 겜 바로 터짐 2. 이동거리가 일정 이상이면 미리 로딩해둔 큰 타일과 타일 사이의 경로를 따라감 3. 거리가 일정 이하일 때만 세밀한 탐색을 실행 4. 이동 중일때 쿼드트리 등 좀 최적화된 자료구조를 통해서 적 탐색, 적 탐색 성공하면 최소한 일정 거리 이하라는 뜻이므로 자세한 길찾기 실행 5. 여기서 건물과 유닛 길막이 들어가는데.. 이거도 머리 엄청아픔..

[익명(211.46)]

제가 검색해보고 고민한 바로는 지형 기반 길찾기(리전 탐색) -> 건물을 포함한 길찾기(크게크게 길을 막음 + 자원채취하는 일꾼은 유닛은 통과하는데 건물은 통과못함) -> 유닛을 포함한 길찾기(내 앞 경로의 유닛이 이동 중인지? 이동중인 유닛이면 그 유닛이 경로를 비워줄때까지 대기, 그래서 질럿이나 저글링이 버벅대면서 일자로 감, 내 앞 경로의 유닛이 멈춤 상태면 실행 시간 어마어마하게 잡아먹을 경로 탐색을 다시하는게 아니라 시계방향으로 도는 방법 등으로 최대한 부하 안주고 돌아갈 수 있게 처리해줘야 함) 등의 절차를 거쳤던 것 같아요.. 그냥 이론만으로 만들어둔 타일 100*100개 에서 탐색하는 A*로는 진짜 택도 없더라구요

[익명(211.46)]

제가 말한 절차가 어떤 느낌인지 저글링 블러드 같은거 보시면 알거에요 저글링 블러드 유즈맵에선 비콘 찍으면 저글링들이 한번에 일정 위치로 어택땅을 찍는데 지형에 따라 움직이고, 건물은 또 돌아가고, 앞에 저글링 갈때까지 기다리다보니 일렬로 쭈욱 늘어서서 뛰고.. 암튼 머리 엄청아파요

[익명(211.46)]

그러면서 느낀건 1995년도 컴퓨터 사양으로 1600마리까지 무리없이 돌아가게 최적화한 미친 개발자들이 새삼 대단하게 느껴질 뿐...

[Pawn(112.162)]

아 정말정말 감사합니다. 이렇게나 해주시고 ㅠㅠ 에셋 2d 네비게이션으로 간략하게 나마 만들고 있었는데 유닛을 죽이고 유닛을 재탐색하는 경우 유닛이 멈춰있는 시간이 길어서 a*로 해보려 했는데 이것도 힘들어보이네요 ㅠㅠ 아무튼 머리깨질각오하고 한번 노력해보겠습니다.. 다시한번 너무 감사합니다.

[누아(rbfwmqwntm)]

이 영상에서는 A* 대비 JPS(B)가 많이 우월한 성능을 보인다는데. 이걸로는 해볼 생각 없니?
https://youtu.be/rfOgaPXCADQ

[Pawn(112.162)]

이거 저 때문에 찾으신거에요? 감동.. 저도 이거 봤었는데 내부적으로 어떻게 도는지 확인이 안되고 논문을 참고해서 코드를 짤 수 있는 실력은 아니라고 판단해서 아직은 그림에 떡인듯 싶습니다 ㅠㅠ 그럼에도 너무너무 감사드려요!!!!