[📜일지] 알고리즘 - 범위공격이 가장 많은 적을 맞추려면

AI가 범위공격 스킬을 쓸 때, 가장 많은수의 적이 맞는 위치를 어떻게 특정해 내야 하는가?

라는 알고리즘을 구현했다.

아래와 같은 상황에서 가장 많은 적을 맞출 수 있는 원의 중심을 찾는것이 목표이다.

원이 아니라면...? 미스포츈의 원뿔모양 같은건 나중에 생각하기로 함.

구글 검색 결과 스택오버플로우에서 해답을 발견.

스택오버플로우에서 설명하고 잇는것은 논문에서의 Greedy Algorithm을 응용한것임.

나도 그리디 알고리즘을 대충 배껴서 만들기로 결정.

내가 만드는 알고리즘의 목표는

-> 반지름이 r 인 원이 AI 의 현재 타겟을 포함하면서, 가장 많은 점을 커버하는 위치를 찾아라 (원의 중심의 위치를 찾아라)

그것을 위한 알고리즘의 간략한 설명은 아래와 같다.

먼저 전제조건으로 두개의 점을 지나는 원은 두개 존재한다는 것을 숙지할 것.

1. 모든 점에 대해서, 두개의 점의 거리가 원의 지름보다 작은 페어를 찾는다.

2. 1에서 찾은 각각의 페어를 지나는 두개의 원의 중심을 찾는다.

3. 원의 중심과 현재의 타겟과의 거리가 r보다 작은 원만 선택한다.

4. 그 원이 커버하는 점의 숫자를 구한다.

5. 가장 많은 점을 커버하는 원을 선택한다.

이렇게 모든 점들의 페어 (짝)을 다 하나하나 계산하면 엄청나게 계산량이 많아지지 않을까 했지만

실제로 존재하는 페어의 수는 2 * nC2 으로, 내 게임의 적은 많아봐야 10마리 이므로 2 * 10C2 = 90로 최대 90개 원을 구하는데 그칠것이다.

두개의 점을 지나는 원의 중심은 어떻게 구하는가? 의 해답은 이것을 참고했다.

대충 해석해보자면,

두개의 점 페어와 원의 중심을 이으면 변의 길이가 r인 마름모가 된다.

마름모의 대각선의 길이를 피타고라스의 정리등을 이용해서 구하면 원의 중심을 구할 수 있다

자세한거는 링크 참조. 거기에 식 다나옴.

이런식으로 대충 알고리즘 만들어서 구현했따는 이야기.

갑자기 귀찮아져서 여기서 쓰는거 그만둠.

댓글 3