당구 시뮬레이션 2 - 최적 알고리즘을 찾아서

Jeuk Oh·2021년 9월 12일
1

ㅋㅅㅋ

목록 보기
3/10
post-thumbnail

개요

내일 있을 시험에 대비해서 미리 생각해보는 시간

세팅

총 6개의 공과 6개의 Hole이 존재한다.

0번 공 (수구, Que_ball)과 목적구 (1번 공, 3번 공), 상대 목적구 (2번 공, 4번 공), 최종 목적구 (5번 공)이 존재한다.

Player는 공의 위치와 Hole의 위치, 테이블 정보만을 인풋으로 받는다. Que_Ball에 주어야하는 적절한 힘의 크기와 방향을 계산하여 서버에 전송해야한다.

목표

상대가 2번공, 4번공을 넣고 최종 목적구를 넣기 전에 먼저 목적구 1, 2를 넣고 최종 목적구를 마지막으로 넣는다. 20턴 동안 게임이 끝나지 않을 시 누적감점이 큰 사람이 패배.

감점 요소
수구를 Hole에 넣으면 감점
수구는 목적구를 먼저 때려야함, 상대 목적구를 먼저 맞추거나, 아무 공도 맞추지 못하면 감점
목적구 1,2를 넣기 전에 최종목적구를 넣으면 패배


접근 방식

함수가 참 많이 필요하다. 넘파이를 못쓰게 하는 것은 너무하다...

1. Path_find

path_find 함수를 구현

path_find 함수는 시작 위치와 목적 위치를 인풋으로 받아 시작 위치에서 해당 점에 도착할 수 있는 원 쿠션을 고려한 모든 path 백터를 반환,
이 때 path_check 함수를 구현하여, path상에 목적구와 수구를 제외한 다른 공, 테이블 경계, path 중간에 구멍이 존재할 시 해당 Path를 반환하지 않는다.

쿠션을 고려하자면

3번 구가 구멍에 들어가는 path_find 개요도 중 일부, path_find의 목적 위치 인풋 좌표가 테이블 경계를 넘어간다면 테이블 경계를 기준으로 path 백터를 자른 뒤 대칭하여서 path백터를 2개로 분리하고 각각 path_check를 2번하면 될 것 같다. (이 때 분리 된 Path 시작 지점과 끝 지점에서 테이블 경계와 만나는 것은 예외처리를 해야하는데 쩜 복잡해지는 구먼)

1-1 목적구가 Hole에 들어갈 수 있는 Path

이런 식으로 path_find 함수를 구현하면 path_find(목적구위치, hole 위치) 를 통해 모든 hole에 위치에 대해서 돌려서 원 쿠션을 고려한 모든 가능한 path를 찾을 수 있다. 앞으로 목적구 A의 Obj_Paths라고 명명하겠다.

다음은 목적구가 Hole에 들어갈 수 있는 경우에 대응하는 수구가 목적구를 맞추는 path를 계산해야한다.

1-2 수구가 목적구를 맞추는 Path

Obj_Paths의 한 path에 대해서 path 백터를 단위 백터화 한 뒤 목적구의 현재 위치에서 path백터* 공의 지름을 빼주면
목적구가 그 path를 가기 위해 수구가 도착해야 하는 목적지가 나온다.

path_find (수구 위치, 해당 목적지) 로 Que_Paths를 얻을 수 있다.

Que_Paths는 원쿠션을 고려한 목적구를 한 Obj_path로 보내기 위한 방법들이다.

파란 색 Obj_path에 대해서 Que_Paths들 이래서 경로 중에 Hole이 있는 것도 제거해 주어야한다. ( 사진은 제거가 안된 상태, 오른쪽 대칭 path도 제거 되어야 맞다. (경로 중에 공이 있으므로))

1-3 Que_Paths중 최적 Que_Path 찾기

Que_Path는 단순히 공을 목적 위치에 가져다 놓는 경우이지 힘을 전달하는 목적은 고려가 되어 있지 않다. 예를 들어 위 그림 중 위로 맞추는 경우는 (어차피 Hole때문에 안 되긴 하지만) 사실상 목적구가 전혀 힘을 받지 못한다. Que_path와 Obj_path의 각도를 내적을 사용해 확인하여 각도가 가장 작은 것을 리턴해주는 것이 최적 Que_Path일 듯 하다. (Que_path가 쿠션을 맞는 path일 시, obj_path도 알맞게 대칭을 해주어야 한다. 아이고 복잡해)

목적구가 여러개이면 불리한 Que_path여도 다음 목적구를 맞추기 쉽게 다른 path를 선택해야 하는 것은 아닌가?

일단은 고려하지 않으려고 하는데, 이에 대한 내 생각은 다음과 같다. 먼저 공들의 좌표가 주어지면 모든 목적구들에 대해서 Obj_paths를 구해 놓는다.

목적구 A, B가 있고 A를 맞추는 것에 대한 계산을 진행하여 A를 Hole에 넣을 수 있는 Que_Paths 후보들을 찾았다. 각각 Que_Path마다 필요한 속도의 양을 계산하고, 충돌 뒤 예상 정지 지점을 추측한다. (마찰을 고려하지 않는다면 충돌 후 속도를 쉽게 대충 계산할 수 있다.) 정지 지점이 목적구 B의 Obj_paths를 연장한 직선들에 가장 가까이 도착할 수 있는 친구에게 가중치를 준다. 다행히도 잘 정제된 (중간에 충돌이 없이, 목표한 대로 잘 가는) Obj_Path에 대해선 딱히 가중치를 고려할 것이 없다. 그나마 거리 threshold정도? 너무 거리가 길면 풀차지 샷을 날려도 도달하지 못할 수가 있다.

Obj_Path에 대해 Que_Path가 계산되면 이 친구들은 가중치가 필요해보인다.

Que_Path의 가중치
1. 대응되는 Obj_Path와의 각도 -> 각도가 작을수록 다이나믹스가 줄어들어 변수가 적다.
2. 거리 -> 거리가 크면 Obj_Path에 도달하기 전에 속도가 많이 줄어 계산이 어려워진다. 마찰을 고려한 미분 방정식까지 구현하고 싶지는 않다.
3. 맞춘 뒤 예상 도착 지점 -> 앞서 말한 다른 목적구의 Obj_Path의 연장선에 가까운 친구들이 좋아보인다. (근데 이러면 Obj_Path의 연장선에 또 Path_check를 해야하므로 일단은 고려하지말자)

아무튼 ... 이제 Obj_Paths들과 Obj_Path에 대해 최대 가중치를 가진 Que_Path들만 남았다.

이중에 어떤 Obj_Path, Que_Path를 선택해야할지는 여기서 맞춘 뒤 예상 도착 지점을 계산하거나 앞서 계산한 Que_Path의 가중치를 활용하면 될 것 같다. 가중치가 큰 값부터 처리하면 될 듯 하다. 한 공을 처리한 뒤 새로운 정보를 받아서 똑같이 반복하면 될 듯 하다.


결론

이정도 구현으로도 이번 시험은 충분히 통과 할 것 같지만.. 과연 시간안에 구현이 가능할지 모르겠습니다. (아마 2시간 반) 일단 시간이 없을 때를 가정해서 구현의 우선순위를 정하자면, 구현에서 필수 부분은 Path_find와 Path_check이고 Path_find에서 쿠션을 생각하지 않으면 1개의 Path만 나와 훨씬 쉽게 구현할 수 있을 것 입니다. Numpy만 사용가능해도 훨씬 구현이 빠를텐데 흐음...

그리고 해당 전략은 일단 방향성에 대한 얘기밖에 없고, 힘의 크기에 대한 부분이 없습니다. 적절한 힘의 크기를 계산하는데, 미분 방정식을 풀기는 싫다면 어떻게 접근해야 할까요. 다행히도 Obj_Path에 대해선 어차피 홀에 들어가기 때문에 속도의 상한을 크게 생각할 필요가 없습니다. 하지만 하한은 생각해야 합니다. 반대로 Que_Path는 속도가 크면 다이나믹스를 일으키므로 (키-스) 가능하면 하한을 우선적으로 고려해야합니다. 일단 위 시뮬레이션에서는 쿠션을 고려하지 않고, Path check도 고려하지 않았습니다. 적절한 힘의 크기는 Obj_path와 Que_Path의 단위백터들 간의 내적을 계산한 뒤 ( 0보다 작으면 path_check에 문제가 있는 것),

만약 힘이 전부 전달되는 형태라면 내적 값이 1일 것이고, 힘이 전달되지 않는 형태면 0에 가까울 것입니다. F = F_dir/(내적값)*C1+C2 으로 힘을 뻥튀기 해줍시다. C1은 프로그램의 단위를 고려한 적절한 값이고 C2는 마찰을 고려한 여유힘입니다.

암튼 내일 과제를 받으면 가장 먼저 백터 클래스를 만들고, 백터의 덧셈, 뺄셈, 크기 메서드를 만든 뒤 공의 위치를 다 백터화 해놓는 게 좋겠습니다.
dotproduct도 만들고...

이-글 을 보면 도움이 될 듯 합니다.

아무리 시험이라고 해도 이런 재밌는 플젝을 던져주면서 구글링 및 외장 라이브러리를 못 쓰는건 좀 너무하지 않나 싶습니다. ㅜㅜ

화이팅

아 그리고 홀의 위치를 실제 위치보다 조금 앞으로 인식시켜주는 것이 좋습니다. 안그러면 테이블 다 긁습니다.

↑ 수정 전
↓ 수정 후

그 밖에 재밌어서 한 테스트들

아이 재밌다

profile
개발을 재밌게 하고싶습니다.

2개의 댓글

comment-user-thumbnail
2021년 9월 12일

아 생각해보니 1 목적구를 맞춘 뒤 2 목적구를 맞춰서 2 목적구를 넣는 형태도 고려하면 좋겠으나, 이경우는 테이블도 크고 공이 몇개 없으니 생각하지 맙시다..

답글 달기
comment-user-thumbnail
2021년 9월 13일

제가 구현하고 싶었던 거 완벽하게 구현하셨었군요,, ㅋㅋ
힘의 크기는 1차식으로 구현하셨는데, 불안정적 이라면, 2차나 3차로 정확도를 올려보시는 것도 좋아보여요.

답글 달기