[계산 기하] PINBALL 핀볼 시뮬레이션.

1. 벡터

 

이 문제는 장애물과의 충돌 유무와 충돌후 방향 벡터를 구하는 함수만 구현하면 쉽게 풀린다.

문제는 구현이다.

 

이 문제에서 사용한 벡터 클래스는 책에 구현되어 있는 것이다.

 

2. 핀볼과 장애물의 충돌 유무 판단

장애물의 중심 = c

장애물의 반지름 = r

핀볼의 방향 벡터 = dir

핀볼의 시작점 = a

 

장애물에서 a, a+dir 두점을 지나는 직선과의 거리 = h

 

라고 하자.

 

먼저 핀볼의 현재 상태에서 다음 충돌할 장애물을 찾아야한다.

 

핀볼이 충돌 할 수 있는 장애물은

 h < r + 1 임을 알 수 있다.

 

그리고 이 조건을 만족하는 장애물들 중에서

핀볼과 가장 가까운 장애물을 선택하면된다

 

이것은 내분점 공식을 이용하여 구하였다.

 

(예외 조건으로 a를 중심으로 dir과 c 가 예각을 이루어야 한다. 둔각인 경우 핀볼과 반대 방향에 있다는 뜻) 

3. 핀볼의 장애물 충돌후 방향 벡터

빨간선이 핀볼의 방향벡터라 하자

검은색 화살표는 핀볼이 충돌할때 생기는 핀볼의 중심에서 장애물 중심으로 가는 방향 벡터이다, 중심벡터라하자.

공의 충돌 후 방향 벡터는 입사각 반사각이 같으므로 

 

중심벡터를 θ 만큼 더한것에 방향을 바꾼것과 같다.

 

즉, 중심벡터에 핀볼의 방향 벡터를 뺀값을 더하고 음수를 곱하면 다음 방향벡터가 나온다.

(뺀값이 음수가 될 수 있으므로 fmod를 사용하여 0~2pi 값만 사용하게 하였다.)

 

4. 책에서의 풀이

 

장애물과의 충돌판정은 거리, 속도, 시간을 이용하여 문제를 해결하였고

핀볼의 충돌 후 방향벡터는 내적 정사영을 사용하여 간단하게 해결하였다.

 

 

 

class obstruction
{
public: 
    vector2 point;
    int r;
    obstruction(double x = 0., double y = 0., int r = 0.) {
        this->point = vector2(x, y);
        this->r = r;
    }    
    bool isCollision(vector2 a, vector2 dir, int r, vector2& p) {
        double dirPolar = dir.polar();
        double centerPolar = (this->point - a).polar();
        
        if(dirPolar > centerPolar) std::swap(dirPolar, centerPolar);
        if(PI/2 <= (centerPolar-dirPolar) && (centerPolar - dirPolar) <= 3. * PI / 2) return false;
       
        double h = pointToLine(this->point, a, a+dir);
        double d = r + this->r;
        if(h < d) 
        {
            vector2 b = perpendicularFoot(this->point, a, a+dir);
            double n =  sqrt(d*d - h*h);
            double m =  (b-a).norm() - n;
            p = vector2((m*b.x + n*a.x)/(m+n), (m*b.y + n*a.y)/(m+n));
 
            return true;
        }
        else return false;
    }
 
};
 
int testCase, N;
vector2 pinball, pinballDirection;
obstruction obs[50];
 
vector2 polarTovector(double p) {
    return vector2(cos(p), sin(p));
}
 
vector2 reflectionAngle(int obsIndex, vector2 dir, vector2 pinballPos) {
    vector2 normalVector = obs[obsIndex].point-pinballPos;
    double nP = normalVector.polar();
    double angle = fmod(2*PI + nP - dir.polar(), 2*PI);
    return (polarTovector(angle + nP))*-1.;
}
 
int findNext(int before, int count)
{
    if(count >= 100)
    {
        std::cout<<"\n";
        return count;
    }
 
    int min = INT32_MAX, select = -1;
    vector2 tmpPinball((double)INT32_MAX, (double)INT32_MAX);
    vector2 minPinball = tmpPinball;
 
    for(int i = 0; i < N; i++)
    {
        if(before != i && obs[i].isCollision(pinball, pinballDirection, 1, tmpPinball))
        {
            if(howMuchCloser(pinball, tmpPinball, minPinball) > 0)
            {
                minPinball = tmpPinball;
                select = i;
            }
        }
    }
    if(select == -1) { 
        cout<<"\n";
        return count;
    }
    pinball = minPinball;
    pinballDirection = reflectionAngle(select, pinballDirection, pinball);
    
    cout<<select<<" ";
    return findNext(select, count+1);
}
 

PINBALL