충돌 감지와 2차원에서의 객체 표현 (2)

등록일: 2014. 10. 22

시작하세요! 안드로이드 게임 프로그래밍

  • 마리오 제흐너 지음
  • 유윤선 옮김
  • 832쪽
  • 36,000원
  • 2011년 09월 30일

광범위 충돌 감지와 미세 충돌 감지

아직까지 객체와 경계 도형 사이의 충돌 검사를 어떻게 하는지 배우지 않았다. 이런 충돌 감지 범위로는 두 가지가 있다.

  • 광범위 충돌 감지: 이때는 어떤 객체들이 잠재적으로 충돌할지 판단한다. 예를 들어 서로 충돌할 수 있는 100개의 객체가 있다고 가정하자. 이 경우 각 객체가 서로 충돌하는지 여부를 단순히 판단하려면 100×100/2번의 충돌 검사를 수행해야 한다. 이런 단순 충돌 검사 방식은 O(n2) 점근적인 복잡도 방식으로서 완료까지 n2번의 단계가 필요하다(실제로는 이 수의 절반에서 작업이 끝나지만 점근적인 복잡도에서는 모든 상수를 배제한다). 광범위 충돌 감지 로직을 사용하면 실제로 충돌 위험에 처한 객체 쌍이 어떤 것들인지를 파악한다. 나머지 쌍(예를 들어 두 객체가 서로 충돌하기에는 너무 동떨어진 경우)들에 대해서는 검사하지 않아도 된다. 미세 충돌 검사는 보통 많은 연산이 소요되므로 이런 식의 로직을 적용하면 연산 부담을 그만큼 줄일 수 있다.
  • 미세 충돌 검사: 충돌할 수 있는 객체 쌍이 어떤 것인지 알았다면 경계 도형이 겹치는지 여부를 확인해 실제로 충돌하는지 판단한다.

여기서는 미세 충돌 검사부터 먼저 살펴보고 이어서 광범위 충돌 검사를 나중에 살펴보겠다.

미세 충돌 검사

광범위 충돌 검사를 끝내고 나면 충돌할 위험이 있는 객체들의 경계 도형이 서로 중첩되는지 확인해야 한다. 앞에서 필자는 경계 도형으로 몇 가지 옵션을 사용할 수 있다고 얘기한 바 있다. 삼각형 메시는 가장 많은 연산 부담이 따르고 만들기도 까다롭다. 사실 대부분의 2D 게임에서는 경계 사각형과 경계 원만으로도 충분하므로 여기서도 이를 활용한 방법에 대해서만 설명하겠다.

원 충돌

경계 원은 두 객체의 충돌 여부를 가장 쉽게 알 수 있게 해준다. 먼저 간단한 Circle 클래스를 정의하자. 이 클래스는 예제 8-4에 나와 있다.

예제 8-4 ㅣ 간단한 원 클래스인 Circle.java

package com.badlogic.androidgames.framework.math;

public class Circle {
    public final Vector2 center = new Vector2();
    public float radius;

    public Circle(float x, float y, float radius) {
        this.center.set(x,y);
        this.radius = radius;
    }
}

여기서는 중심을 Vector2로 저장하고 반지름을 단순 float으로 저장했다. 그럼 두 원이 중첩되는지 여부를 어떻게 알 수 있을까? 그림 8-13을 보자.

그림 8-13 | 두 원이 중첩(왼쪽)되는 경우와 중첩되지 않는 경우(오른쪽)

사실 이 로직은 매우 간단하며 연산도 효율적이다. 이때는 두 원의 중심 사이의 거리만 판단하면 된다. 이 거리가 두 원의 반지름보다 크다면 두 원이 중첩되지 않은 것이다. 이런 충돌 검사 코드는 다음과 같이 작성할 수 있다.

public boolean overlapCircles(Circle c1, Circle c2) {
    float distance = c1.center.dist(c2.center);
    return distance <= c1.radius + c2.radius;
}

여기서는 먼저 두 원 사이의 거리를 측정하고 거리가 반지름의 합보다 작거나 같은지 확인한다.

Vector2.dist() 메서드에서는 루트를 사용해야 한다. 하지만 루트를 사용할 경우 연산에 더 많은 시간이 소요된다. 이를 더 빠르게 할 수는 없을까? 할 수 있다. 이 경우 다음 조건을 수정하면 된다.

sqrt(dist.x * dist.x + dist.y * dist.y) <= radius1 + radius2

루트를 없애려면 다음과 같이 양 변을 수정하면 된다.

dist.x * dist.x + dist.y * dist.y <= (radius1 + radius2) * (radius1 + radius2)

여기서는 우변에 값을 한 번씩 더하고 곱함으로써 루트를 없앴다. 이 방식이 훨씬 효율적이다. 이번에는 두 벡터 사이의 거리 제곱을 반환하는 Vector2.distSquared() 함수를 작성해 보자.

public float distSquared(Vector2 other) {
    float distX = this.x - other.x;
    float distY = this.y - other.y;
    return distX*distX + distY*distY;
}

이제 overlapCircles()는 다음과 같이 작성할 수 있다.

public boolean overlapCircles(Circle c1, Circle c2) {
    float distance = c1.center.distSquared(c2.center);
    float radiusSum = c1.radius + c2.radius;
    return distance <= radiusSum * radiusSum;
}
사각형의 충돌

이번에는 사각형을 살펴보자. 먼저 사각형을 표현할 클래스가 필요하다. 앞에서 사각형은 좌측 하단 구석 위치에 너비와 높이를 더해 정의한다고 언급한 바 있다. 이를 코드로 옮긴 게 예제 8-5다.

예제 8-5 ㅣ 사각형을 나타내는 Rectangle.java

package com.badlogic.androidgames.framework.math;

public class Rectangle {
    public final Vector2 lowerLeft;
    public float width, height;

    public Rectangle(float x, float y, float width, float height) {
        this.lowerLeft = new Vector2(x,y);
        this.width = width;
        this.height = height;
    }
}

이 클래스에서는 좌측 하단 구석의 위치를 Vector2에 보관하고 너비와 높이를 두 개의 float에 보관한다. 그럼 두 사각형의 충돌은 어떻게 검사할 수 있을까? 그림 8-14에서는 이에 대한 힌트를 볼 수 있다.

그림 8-14 | 서로 중첩되거나 중첩되지 않은 많은 사각형

처음 두 경우처럼 부분 중첩 또는 중첩되지 않은 상태는 쉽게 판단할 수 있다. 하지만 마지막 경우는 생각하기가 쉽지 않다. 사각형은 당연히 다른 사각형 안에 완전히 포함될 수 있다. 이런 일은 사실 원에서도 일어난다. 하지만 원의 경우 원이 다른 원에 포함돼 있더라도 항상 중첩 검사가 올바른 결과를 반환해준다.

사각형의 중첩 검사는 처음에는 조금 복잡해 보인다. 하지만 약간의 로직을 활용하면 충돌 검사를 간단히 작성할 수 있다. 다음은 두 사각형 사이의 중첩 검사를 수행하는 가장 간단한 메서드다.

public boolean overlapRectangles(Rectangle r1, Rectangle r2) {
    if(r1.lowerLeft.x < r2.lowerLeft.x + r2.width &&
       r1.lowerLeft.x + r1.width > r2.lowerLeft.x &&
       r1.lowerLeft.y < r2.lowerLeft.y + r2.height &&
       r1.lowerLeft.y + r1.height > r2.lowerLeft.y)
        return true;
    else
        return false;
}

이 메서드는 처음에는 조금 어려워 보이므로 각 조건절을 하나씩 살펴보자. 첫 번째 조건절에서는 첫 번째 사각형의 왼쪽 모서리가 두 번째 사각형의 오른쪽 모서리보다 항상 왼쪽에 있어야 한다고 지정한다. 두 번째 조건문에서는 첫 번째 사각형의 오른쪽 모서리가 두 번째 사각형의 왼쪽 모서리보다 오른쪽에 있어야 한다고 지정한다. 나머지 두 조건문에서는 사각형의 상단과 하단 모서리에 대해 동일한 로직을 지정한다. 이런 조건을 모두 충족한다면 두 상각형은 중첩된 것이다. 그림 8-14를 다시 한 번 살펴보자. 이 그림에서 이와 동일한 조건을 다루고 있음을 알 수 있을 것이다.

원/사각형의 충돌

그럼 원과 사각형의 중첩도 검사할 수 있을까? 물론 할 수 있다. 하지만 이 작업은 좀 더 복잡하다. 그림 8-15를 살펴보자.

그림 8-15 | 원에 가장 가까운 사각형 내의 점을 찾음으로써 원과 사각형의 중첩을 검사

원과 사각형의 전반적인 중첩 검사는 다음과 같이 진행된다.

  • 원의 중심에 가장 가까운 사각형 위/안의 x좌표를 찾는다. 이 좌표는 사각형의 좌측 또는 우측 모서리상의 점일 수 있다. 원의 중심이 사각형 안에 포함된 경우에는 가장 가까운 x 좌표가 원 중심점의 x좌표가 된다.
  • 원의 중심에 가장 가까운 사각형 위/안의 y좌표를 찾는다. 이 좌표는 원의 중심이 사각형 안에 포함되지 않은 경우 사각형의 상단 또는 하단 모서리상의 점일 수 있다. 원의 중심이 사각형 안에 포함된 경우에는 원의 중심점 y좌표가 이 좌표가 된다.
  • 가장 가까운 x, y 좌표로 구성된 점이 원 안에 있는 경우 원과 사각형은 중첩된 것이다.

그림 8-15에는 나오지 않았지만 이 메서드는 사각형을 완전히 포함하는 원에 대해서도 사용할 수 있다. 이를 코드로 작성해 보자.

public boolean overlapCircleRectangle(Circle c, Rectangle r) {
    float closestX = c.center.x;
    float closestY = c.center.y;

    if(c.center.x < r.lowerLeft.x) {
        closestX = r.lowerLeft.x;
    }
    else if(c.center.x > r.lowerLeft.x + r.width) {
        closestX = r.lowerLeft.x + r.width;
    }
    if(c.center.y < r.lowerLeft.y) {
        closestY = r.lowerLeft.y;
    }
    else if(c.center.y > r.lowerLeft.y + r.height) {
        closestY = r.lowerLeft.y + r.height;
    }
    return c.center.distSquared(closestX, closestY) < c.radius * c.radius;
}

앞에서 설명한 내용보다 실제 구현이 훨씬 쉬워 보일 것이다. 여기서는 원에 가장 가까운 사각형의 점을 판단한 후 이 점이 원 내부에 있는지 여부만 검사한다. 이 점이 원 내부에 있다면 원과 사각형은 중첩된 것이다.

여기서 필자가 Vector2 인스턴스 대신 두 개의 float 인자를 받는 오버로드된 distSquared() 메서드를 Vector2에 추가했다는 점에 주의하자. 마찬가지로 dist() 함수도 오버로드했다.

내용 정리

점이 원 또는 사각형 내에 있는지 여부에 대한 검사는 유용하게 활용할 수 있다. 이번에는 두 개의 메서드를 더 작성하고 앞서 정의한 나머지 세 메서드와 함께 이를 OverlapTester에 집어넣자. 예제 8-6은 이 코드를 보여준다.

예제 8-6 ㅣ 원, 사각형, 점 사이의 중첩을 검사하는 OverlapTester.java

package com.badlogic.androidgames.framework.math;

public class OverlapTester {
    public static boolean overlapCircles(Circle c1, Circle c2) {
        float distance = c1.center.distSquared(c2.center);
        float radiusSum = c1.radius + c2.radius;
        return distance <= radiusSum * radiusSum;
    }

    public static boolean overlapRectangles(Rectangle r1, Rectangle r2) {
        if(r1.lowerLeft.x < r2.lowerLeft.x + r2.width &&
           r1.lowerLeft.x + r1.width > r2.lowerLeft.x &&
           r1.lowerLeft.y < r2.lowerLeft.y + r2.height &&
           r1.lowerLeft.y + r1.height > r2.lowerLeft.y)
            return true;
        else
            return false;
    }

    public static boolean overlapCircleRectangle(Circle c, Rectangle r) {
        float closestX = c.center.x;
        float closestY = c.center.y;

        if(c.center.x < r.lowerLeft.x) {
            closestX = r.lowerLeft.x;
        }
        else if(c.center.x > r.lowerLeft.x + r.width) {
            closestX = r.lowerLeft.x + r.width;
        }

        if(c.center.y < r.lowerLeft.y) {
            closestY = r.lowerLeft.y;
        }
        else if(c.center.y > r.lowerLeft.y + r.height) {
            closestY = r.lowerLeft.y + r.height;
        }

        return c.center.distSquared(closestX, closestY) < c.radius * c.radius;
    }

    public static boolean pointInCircle(Circle c, Vector2 p) {
        return c.center.distSquared(p) < c.radius * c.radius;
    }

    public static boolean pointInCircle(Circle c, float x, float y) {
        return c.center.distSquared(x, y) < c.radius * c.radius;
    }

    public static boolean pointInRectangle(Rectangle r, Vector2 p) {
        return r.lowerLeft.x <= p.x && r.lowerLeft.x + r.width >= p.x &&
            r.lowerLeft.y <= p.y && r.lowerLeft.y + r.height >= p.y;
    }

    public static boolean pointInRectangle(Rectangle r, float x, float y) {
        return r.lowerLeft.x <= x && r.lowerLeft.x + r.width >= x &&
            r.lowerLeft.y <= y && r.lowerLeft.y + r.height >= y;
    }
}

이로써 물리 모델과 충돌 검사에 사용할 수 있는 2D 수학 라이브러리를 모두 갖추게 됐다. 이번에는 광범위 충돌 검사에 대해 좀 더 자세히 들여다 보자.

광범위 충돌 검사

그럼 광범위 충돌 검사는 어떻게 적용할 수 있을까? 수퍼마리오 브라더스의 전형적인 화면을 보여주는 그림 8-16을 한번 보자.

그림 8-16 | 수퍼마리오와 악당들. 객체 주변의 상자가 경계 사각형이다. 큰 상자는 세계에 부여한 그리드를 구성한다.

독자들 중에는 벌써 어떤 부분을 검사하지 않아도 되는지 눈치 챈 사람도 있을 것이다. 그림 8-16에서 파란색 그리드는 세계를 쪼갠 파티션 셀을 나타낸다. 각 셀은 정확히 동일한 크기를 갖고 있으며 전체 세계는 셀로 덮여 있다. 마리오는 현재 이런 셀 중 두 곳에 걸쳐 있으며 마리오가 충돌할 수 있는 다른 객체들은 다른 셀 안에 있다. 따라서 마리오는 화면에 있는 다른 객체와 같은 셀 안에 있지 않으므로 이때는 충돌 검사를 하지 않아도 된다. 이때 해야 할 일은 다음 작업이 전부다.

  • 물리 이론과 컨트롤러의 현재 단계에 기반해 세계의 모든 객체를 업데이트한다.
  • 객체의 위치에 따라 각 객체의 경계 도형 위치를 업데이트한다. 물론 이때 방향과 스케일도 함께 업데이트해야 한다.
  • 경계 도형에 기반을 둔 어떤 객체가 어떤 셀이 들어 있는지 판단하고 이 객체를 이들 셀에 들어 있는 객체의 목록에 추가한다.
  • 충돌을 검사한다. 이때 충돌할 수 있는 객체 쌍(예를 들어 굼바는 다른 굼바와 충돌하지 않는다)과 동일 셀 내의 객체들 사이에서만 충돌 검사를 수행한다.

이 방식은 공간 해시 그리드 광범위 충돌 검사라고 부르며 구현하기도 매우 쉽다. 첫 번째로 할 일은 각 셀의 크기를 정의하는 것이다. 이 크기는 게임 세계의 스케일과 단위에 따라 크게 달라질 수 있다.