당구 시뮬레이션 3 - 정리, 느낀 점

개요

당구 시뮬레이션 시험은 끝, 치열한 경기 끝에 반에서 우승했습니다. 예~

제가 한 구현보다는 테스트 툴이 생각보다 틱 단위가 큰 것으로 느껴졌습니다. 속도가 조금만 커도 공이 겹치고 계산하지 않은 방향으로 가는 문제가 컸습니다.

좀 극단적인 경우지만 그림처럼 수구의 속도가 너무 빠르면 충돌 판정이 이미 공이 닿고 이동한 후에 나와서 목적구가 엉뚱한 방향으로 갑니다. 심한 경우는 충돌을 안하고 통과하기까지..

그렇다고 해서 속도를 약하게 하면 목적구가 힘을 못받아서 오히려 상대에게 기회만 주는 꼴이 되었습니다.

가장 좋은 방법은 최대한 공이 충돌하는 각도를 두껍게하여 이러한 현상이 나타나도 목적구의 방향의 오차가 적게 하는 것이었습니다. 그리고 힘의 전달도 잘 됩니다.

어쩐지 똑같은 코드로도 시행을 반복할때마다 결과가 달라서 의아했는데 이런 이유가.. 이걸 몰라서 로직이 뭔가 잘못된 줄 알고 로직을 고치느라 시험 중 시간을 많이 소모했었습니다. 근데 실제로 틀린 거 발견 ㅎㅎ;;

---

구현

파-워

원래 쿠션을 고려한 경로찾기까지 완성시키는 것이 목적이었으나, 공이 계산한대로 가지 않아 쿠션을 고려해봐야 의미가 없겠구나 싶어 힘 조절에만 집중하였습니다.

어설픈 방정식을 풀어서 거리에 따른 힘의 량을 추측했습니다. 이게 맞는지 잘 모르겠네요. 껄껄

그림과 같이 힘을 받아 굴러가는 공은 충돌하기 전까지 운동마찰력만 받는다고 생각하고

$V_T = V_0 - {\mu}t_0$
$S=\int_0^{t_0}(V_0-{\mu}t)dt$

정리하면

$V_0 = \sqrt{{V_T}^2+2{\mu}S}$

목적구가 Hole에 들어갈 때는 속도의 상한이 없으니 적당히 $V_T$에 6~70을 주고
마찰계수는 그냥 적당히 주었습니다. S는 처음에는 목적구와 Hole의 거리를 쓰고
이렇게 구해진 $V_0$를 다시 같은 식의 $V_T$ 로 사용하여 이번엔 S로 수구와 목적구의 거리를 쓰면 적당히 목적구가 홀에 6~70의 속도로 도착하게 하는 시작 속도 값을 얻을 수 있습니다. ( 사실 여기서 각도에 대한 값을 보정해야합니다. 그건 나중에 했습니다.) 보통 이런 구현은 처음에 준 힘값을 바로 속도로 쓸테니 그 값에 적절한 하이퍼 파라미터를 곱하고 더해 힘 값으로 썼습니다.

확실히 바꾸기 전보다 거리에 따른 속도가 안정적으로 바뀌었다고 생각합니다.

---

논-쿠-션

시험은 쿠션을 고려하지 않고 단순한 구현으로 끝났지만 이왕 한게 아쉬워서 쿠션도 고려해보았습니다.

그 전에 먼저 쿠션을 고려하지 않은 코드는 다음과 같았습니다.

논쿠션 path_find

    def path_find(x:Vector,y:Vector):
        def path_check(path:Vector,start,end):
            # todo
            # 경로중에 공이 있으면 제외
            checkvec = end-start
            checkvec = checkvec/checkvec.norm
            cnt = 0
            for ball in objball+enemyball+[myball]+Myholes:
                checkball = ball - start
                if checkvec.dot(checkball) < 0:
                    continue
                if abs(checkvec.cross(checkball)) < 1.5 * Ball_r:
                    cnt += 1
                #print(cnt)
            print(start, end, cnt)
            if cnt > 2:
                return False
            return True
        path = y-x
        #todo
        #쿠션고려
        
        if path_check(path,x,y):
            return path
        return None

먼저 시작위치와 목적위치 x, y를 받으면 경로를 확인 후 반환하는 path_find 함수입니다. 아직 쿠션을 고려하지 않아서 y-x를 바로 리턴하네요.
path_check에서 예상 경로에 방해물이 있나 확인합니다.

목적구, 상대목적구, 수구, 홀들에 대해서 백터의 원점을 시작 방향으로 한 뒤
외적을 사용하여 수직 거리를 구할 수 있습니다.

그림으로 보면 이해가 편합니다.

$|\vec A\times \vec B| = |\vec A||\vec B|sin({\theta})$

이므로 checkvec을 단위백터로 사용하여 공의 경로와 다른 공의 거리를 쉽게 구할 수 있습니다. 하지만 두 백터의 외적이 음수라면 상관없으므로 제외해줍니다.

자기 자신과 홀 또는 목적구를 제외하면 경로상에 공의 반지름 1.5배 이하의 거리엔 다른 공이 있으면 안됩니다. 카운트를 세서 3개가 넘어가면 해당 path가 불가능하다고 판단합니다. (2개는 자기 자신과 목적구, 또는 목적구와 홀입니다.)

이렇게 그림을 그려보닌까 수구가 노란 공을 때리는 path가 뒤에 검은 공과 보라공 때문에 불가능하다는 결과가 나오는 문제가 있었겠네요.

원래는 백터의 구간을 나누어서 점을 찍으며 근처에 공이있나 확인했었는데 이 방법이 좀 더 세련되고 깔끔해서 바꿨었는데 그게 나았을 수도 있겠습니다.

논쿠션 find_best_path

    # 내 목적구에 대해서만
    for obj in objball:
    	#후보가 될 path들
        cand_path = []
        # 모든 홀에 대해서 (6개)
        for hole in Myholes:
            #obj이 hole에 가는 방법
            objtohole = path_find(obj,hole)
            # path_find 함수는 obj-hole 백터를 반환하며 공의 진행방향에 장애물이 있나 확인
            if not objtohole:
                print('not objtohole pass')
                continue
            # objtohole을 위해 수구의 도착 위치 계산
            objtohole_nv = objtohole/(objtohole.norm)
            # 목적구가 홀로 가려는 방향의 반대방향으로 
            #공크기만큼 이동한 점이 수구가 가야할 곳
            que = obj + Ball_R*-objtohole_nv
            # 수구 to que점을 가는 길 계산
            quetoobj = path_find(myball,que)
            if not quetoobj:
                print('no quetoobj pass')
                continue
            quetoobj_nv = quetoobj/(quetoobj.norm)
            # 두 백터의 각도 계산 (단위백터끼리의 내적 cos(theta) 값임)
            # 영보다 작거나 음수면 안하고 진행
            if objtohole_nv.dot(quetoobj_nv) <= 0:
                continue
            #weights *= objtohole_nv.dot(quetoobj_nv)

            # 예측 힘의 값, objtohole 거리, quetoobj 거리에 비례하게 함

            mue = 5.5
            v1h = (55+2*mue*objtohole.norm)
            v01 = (v1h+2*mue*quetoobj.norm)**(1/2)
            inferF = quetoobj_nv * v01
            # 앞선 각도를 계산한 내적 값을 나눠주어 각도가 얇다면 더 쎄게 치도록 함
            inferF = inferF/(objtohole_nv.dot(quetoobj_nv)**(1/2))
            # 완성된 패스를 등록
            # 등록할 때 각도가 두꺼운 것을 우선하도록
            # 하지만 적당히 두꺼운 각도면 수용하도록 각도를 integer화함
            cand_path.append([int(objtohole_nv.dot(quetoobj_nv)*10),inferF.norm,inferF])
		# 모든 Hole에 대한 연산이 끝나면
        # cand_path를 정렬하여 가장 각도가 두껍고 힘이 약한 것을
        cand_path.sort(key=lambda x : (-x[0],x[1]))
        if cand_path:
        #Pathlist에 넣는다. cand_path는 한 목적구에 대한 계산임
            Pathlist.append(cand_path[0])

	#Pathlist는 모든 목적구에 대한 
    #가장 일직선으로 만나는 것 + 다음으로 힘의 필요가 가장 작은 것을 쓰자
    Pathlist.sort(key=lambda x : (-x[0],x[1]))

이 뒤 Pathlist의 가장 충돌 두께가 두꺼운 F를 사용하게 하였습니다.

확실히 다른 분들 시연과 차이가 났던 부분은 가까운 곳으로 치려는 것이 아니라 가능하면 최대한 직선으로 치려고한다는 점?

하지만 모든 경로가 직접 타격이라 경우의 수가 한 목적구에 대해 홀의 개수 6개밖에 없기에, 운이 없다면 Pathlist가 비는 경우가 있습니다. 꽤 자주 있습니다.

~_~

쿠션을 고려한 뒤로 Pathlist가 빈 적은 없지만 또 다른 문제가..

너무 많은 경우의 수때문에 적절한 가중치를 찾지 못하였고, 벽에 반사될 때도 또한 마찬가지로 꽤 큰 오차가 있었습니다.

글이 생긱보다 길어지네요.. 쿠션을 고려한 구현 부분은 다음 기회에...

---

느낀 점

사실 알고리즘 아이디어는 이-영상에서 얻었습니다. 그래도 베이스 코드 하나 없이 생각한대로 잘 구현되었다는 것에 만족. 코드는 여전히 보기 더럽지만 그래도 실력이 늘고있는 건 아닐까요? 껄껄
확실히 생각한 것을 그대로 구현하는 속도가 조금씩이나마 빨라지는 것 같습니다.

잘 한 경기 하나 자랑용 투척 ㅎㅎ;