[🐣질문] a* 패스파인딩에서 길 없을 때 어떻게 처리해야 할지 질문 올립니다.

[ㅁㅁ(211.178)]

인갤러 개쩌는 분들 입장에서 이런 질문 자체가 너무 하찮아서 비웃으실지 모르지만 감히 여쭤봅니다. 

현재 만들고 있는 게임에서 a* 알고리즘을 활용해 적들이 길을 찾아 플레이어를 쫒아오게 했습니다.

그런데 플레이어가 적들이 쫒아 올 수 없는 곳으로 갈 경우

1. 밀폐된 공간에 들어가 문을 닫는다

2. 너무 많은 적이 주인공을 애워싸는 바람에 길을 못찾는 적들이 생긴다.

길을 못찾는 애들이 cpu 과부하를 일으킵니다. 

무슨 돈주고 사서 쓰는 에셋으로 패스파인딩을 하는 것도 아니고

완전 기초적인 형태의 것을 긁어와 사용하다보니

이런 경우에는 어떻게 이 문제를 해결해야 할지 모르겠습니다.

당장 떠오르는 건 최단 경로가 없을 때 몇 초간 길찾기를 멈추라는 식으로 하는 건데,

더 좋은 방법이 있을까요? 

[익명(218.234)]

나같은경운 내가 짠 알고리즘에선, 길찾기 리턴값이 false가 나와도, 받아오는 패스 배열에 최대한 가보려했던 길? 이 남아있음, 그거대로 이동시킴

[ㅁㅁ(211.178)]

감사합니다. (- -)(_ _) 말씀하신 내용들 잘 고려해볼게요!

[거붓(ggp02217)]

멀티쓰레딩으로 틱 계산해서 과도한 시간이 지나는 길찾기를 포기하고 다음 길찾기를 실행

[거붓(ggp02217)]

군집을 다룰 때는 다대다 패스파인딩 알고리즘을 응용하거나 유닛이 가는 방향에 ray 쏴서 해당 유닛을 기준으로 회피기동(Flock avoidance, 아니면 그냥 왼쪽 오른쪽으로 피하는 방식)를 하는 방법이 있음

[거붓(ggp02217)]

A* 특유의 막힌 곳 찾는 걸 최소화 하는 건 탐색공간을 축소(Nav-mesh) 혹은 분활(HPA*,JPS) 하는 방법이 있으나, 이럴 빠에 에셋으로 퉁치는게 나음

[ㅁㅁ(211.178)]

감사합니다. (- -)(_ _) 말씀하신 내용들 잘 고려해볼게요!

[정공개발자(firetruck4545)]

닫힌 리스트중 휴리스틱 추정값이 제일 낮은 곳으로 가서 대기하는 방법은 어떰?

[ㅁㅁ(211.178)]

감사합니다. (- -)(_ _) 말씀하신 내용들 잘 고려해볼게요!