인프런 커뮤니티 질문&답변
작성한 질문수
Astar를 이용한 마우스 이동
작성
·
603
0
안녕하세요.
Astar 알고리즘을 이용해서 키보드 대신 LOL처럼 우클릭시 마우스 좌표로 이동하는 알고리즘을 짜보았는데요.
LOL은 갈 수 없는 벽을 클릭하면 가장 가까운 걸 수 있는 지형으로 가는 걸 보고 따라 해봤는데요.
제가 짠 알고리즘은 이렇습니다.
1. 갈 수 없는 곳을 클릭한다. (Pos dest : ButtonDown했을때 마우스 좌표) (CanGo(dest) == false)
2. dest를 시작점으로 상하좌우 방향, 길이가 1로 BFS를 돈다. (Pos here : BFS탐색중 현재 좌표)
3. BFS탐색중 (CanGo(here) == true) 가 나오면 탐색을 멈추고
4. dest = here
5. dest 까지 Astar 를 실행한다.
여기서 시간복잡도가 대략 Astar : O(VlogV) BFS : O(v^2) 이고
이걸 클라마다, 클라가 마우스를 연타할 때마다 계산해야 하는 게 맘에 안 듭니다.
혹시 개선사항이나 다른 알고리즘 힌트가 있을까요?
제가 고민해본 개선사항은 Astar 경로를 구간별로 캐싱인데 몇일동안 생각이 정리가 되지 않아 질문드립니다!
답변 2
0
상세한 답변 감사합니다.
BFS 선처리를 선택한 이유가 답변의 2번에서 순회 종료 타이밍을 몰라 맵전체를 순회하다 보니 맵(현재 5000x3000)보다 비교적 작은 장애물(최대 4000x300)로 확실한 목적지를 선처리해서 더 적은연산을 하고 싶었습니다.
3번 답변은 한번 구현해 보고, 또다른 모르는 게 생기면 다시 질문하겠습니다!
감사합니다!!
0
1.
BFS랑 A*는 역할이 겹치기 때문에
굳이 BFS로 선체크를 하고 A*를 할 필요는 없습니다.
2.
현재 A* 코드에서는 목적지에 도달해야 멈추고 길을 찾습니다.
이 부분의 코드를 살짝 수정해서 목적지가 없더라도
그 동안 찾은 후보군 중에서 평가점수가 가장 좋은 (그림에서 거리가 3인) 애를
목적지로 가게 수정하면 됩니다.
3.
시작점/목적지 경우의 수가 너무 많기 때문에 캐싱은 힘듭니다.
보통 스타크래프트처럼 길찾기 횟수가 엄청 많은 게임은
다양한 최적화가 들어가는데 이는 고급 AI 기술에 해당합니다.
대표적으로 구간을 미리 나눠서 대략적으로 정해진 길을 따라 가게 합니다.
Lost Temple이라는 맵을 예로 들면은
1 구역에서 2구역으로 이동한다면,
이미 연산된 정보로 1->2 갈 수 있음은 알 수 있고
동그라미 영역을 반드시 지나야 하기 때문에
먼저 1->동그라미를 계산하는 식이죠.
롤 정도 수준이면 그 정도까진 필요 없어 보이지만
다양한 시도를 해보는 것은 도움이 됩니다.