한 타일 3000*3000 정도의 맵에 100마리 정도가 길을 찾아가는 게임을 만들려고 합니다

 

a* 알고리즘 적용하여 만들었는데 문제는 한마리 찾을땐 괜찮은데 100 마리 한꺼번에 길을찾으려니까 맵이너무 커서 길한번 찾을때마다 엄청 멈추더라구요

 

그래서 3000*3000 을 약간 구역을 만들어서 만약에 0,0 에서 3000, 3000 까지 간다면 그냥 가상으로 대각선으로 선을 쭉 이어서 타일 100개 정도 들어갈 길이의 위치를 찾아서 거기까지 길을 찾고 , 도착하면 또 그 위치에서 다시 3000 * 3000 까지 대각선으로 선을 가상으로 이어서 타일 100개정도 갈만큼의 위치에서 끊고 길찾고..이런식으로 하니까 렉은 없긴 한데..

이게 시작점에서 끝점까지 유효한 경로중에 타일100개만큼의 길을 찾는게 아니라 가상으로 대각선을 그어서 100개만큼의 위치를 지정하는 거다 보니까 길을 약간 와리가리 하다가 가는경우가 있더라구요 (첫번째 100개만큼 갔다가 두번째 갈때는 경로가 틀어져서 뒤돌아서 간다든지)

 

맵에서 가는길 못가는길은 항상 실행할때마다 바뀌고 시작지점 끝지점도 유동적인데

 

 위와같은 경우에 계속 a star 를 쓰는게 맞는지..아니면 저렇게 큰 맵에서 수십 수백마리가 동시에길을 찾을 때 좀 더 좋은방법이 있는지 궁금합니다ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ