본문 바로가기

Flash,AS3.0

선분과 선분의 충돌체크 - 1


 

 ※ 아래 코드는 실행해보지 않은것입니다. 동작하지 않을 수도 있습니다.




점 2개의 좌표 정보로 표현된 선분이 2개 있을 때

충돌체크를 하는방법입니다.

퍼즐게임이나 슈팅게임, 아니면 총기를 발사하는 것을 구현할 때 유용하게 쓰일 수 있습니다.
첫번째 방법은 직선의 방정식을 이용하는 것입니다.



요약



아래와 같이 선분이 주어졌을때,



선분의 양 끝 두 점의 좌표를 알기때문에
직선의 방정식도 쉽게 나옵니다.


ax + by = c
a`x + b`y = c`
이 방정식에서 a, b, c, a`, b`, c` 만 변수에 저장해두는 형식으로
가상의(화면에 나타나지 않는) 직선이 있다고 생각하는 것입니다.



액션스크립트 geom 패키지의 Matrix 클래스를 사용하여
이원 일차방정식을 간단히 풀어낼 수 있겠죠.
즉, 위 방정식의 해가 교점의 좌표가 되는 것입니다.  



여기서 중요한 것이
구하려는 게 직선교점이 아닌 선분교점이라는 것입니다.



위와 같이 직선의 교점이 선분 밖에 있으면 안되겠죠.
교점의 좌표가 두 선분의 중간값이 되는지 체크하면 됩니다.

위의 행렬연산에서
역행렬이 존재하지 않는 경우는
해가 없거나(두 직선이 평행)
해가 무수히 많거나(두 직선이 일치)
이 두가지인데요,

두 직선의 x y 계수의 비로 이를 분기할 수 있는데,
두 직선의 해가 없는경우는 물론 두 선분도 겹치치 않으니 생각할 필요 없는데,
해가 무수히 많은경우는 다릅니다.


이러한(위 그림과 같은) 경우에는 직선의 해는 (무수히)있으나
구하려는 선분의 교차여부를 본다면 교차하지 않는 경우이지요.

선분의 한 점이 다른 선분의 중간값이 되느냐 안되느냐 하는 체크를 4개의 점에 걸쳐 모두 시행하면
해결할 수 있습니다.

이 경우와 같이
두 선분이 서로 겹쳐지는 경우는 제작하는 프로그램의 상황에 따라
만나는 것으로 처리할지 아니면 만나지 않을 것으로 처리할지 달라지겠네요.
예를 들어 총쏘는 게임을 만든다면 저렇게 스쳐가는것을 무시하게 할 수도 있지만,
꼬여있는 선분을 푸는 퍼즐게임 같은경우는 교차ok로 인식을 해야겠죠.




구현

선분이 두 개 있다면 
읽어들여야 할 변수는 
 
line1_p1.x , line1_p1.y    // 선분1 의 한쪽 끝 점의 x,y 좌표
line1_p2.x , line1_p2.y    // 선분1 의 다른 한 쪽 끝 점의 x,y 좌표
line2_p1.x , line1_p1.y    // 선분2 의 한쪽 끝 점의 x,y 좌표
line2_p2.x , line1_p2.y    // 선분2 의 다른 한 쪽 끝 점의 x,y 좌표

이렇게 8개가 됩니다. line1_p1 , line1_p2  등은 선분의 양 끝 점(DisplayObject 形) 입니다.


직선의 방정식의 기본형을 살짝 변형하여
ax - by = -c
a`x - b`y = -c`
를 기본으로 삼기로 하고,
a, b, c, a` ,b` ,c` 에 해당하는 변수를 각각
line1_a, line1_b, line1_c, line2_a, line2_b, line2_c
이라고 정했습니다.

직선1의 방정식에서 x의 계수인 line1_a 의 값은
1/(line1_p2.x - line1_p1.x)
가 되는데요, 왜 그러냐면
그래프에서 x의 계수를 2배로 하면 x축 방향으로 2배 축소 되고,
1/2 배로 하면 x축 방향으로 1/2배 축소(2배 늘어남) 가 되므로
직선의 기울기를, 주어진 선분의 기울기와 맞추기 위해
선분이 x축 방향으로 늘어난 정도(line1_p2.x - line1_p1.x)의 역수를 x의 계수로 취해 준 것입니다.

line1_b 의 값은 같은이치로
1/(line1_p2.y - line1_p1.y) 가 되고,

line1_c 의 값은
지금까지 구한 계수(방정식에서 a, b에 해당)와 선분의 아무 한 점을 최초의 방정식
ax - by = -c
에 대입하면 나옵니다.
따라서 아래와 같이 프로그램할 수 있겠습니다.
line1_c = (line1_a*line1_p1.x  +  -1*line1_b*line1_p1.y)*-1


직선2의 계수들도 같은방법으로 구해주면 드디어
두 직선의 방정식이 나왔네요.

이제 행렬을 이용해서 해를 구해야합니다.






Matrix 클래스는 플래시8 부터 있기때문에 그 이전 버전에서는 직접 비슷하게 구현해야 합니다.(역행렬, 행렬곱 메서드 정도만)
액션스크립트 3.0 에서는 flash.geom 패키지에 Matrix 클래스가 들어있습니다.

위쪽의 수식에서
(a  b )
(a` b`)
이 행렬을  matrix1 이라고 하고
(c )
(c`)
이 행렬은 matrix2라고 하면,  


(ActionScript3.0)
import flash.geom.Matrix;
var matrix1:Matrix = new Matrix(line1_a , -1*line1_b , line2_a , -1*line2_b );
var matrix2:Matrix = new Matrix(-1*line1_c , -1*line2_c );
var matrix3:Matrix = new Matrix();

이렇게 나타낼 수 있습니다

위쪽의 수식에서와 같이
매트릭스1을 역행렬로 변환하고, 매트릭스2를 곱해주면 되는데요,
matrix1.invert();
matrix3 = matrix1.concat(matrix2);
위와 같이 내장된 메서드를 이용하면 간단히 연산할 수 있습니다.

아! 역행렬이 존재하지 않는경우(ad-bc=0 의 꼴일 때)도 있으니까 위에 추가를 해줘야 합니다.
그래서 코드를 보면,

import flash.geom.Matrix;

var line1_a:Number = 1/(line1_p2.x - line1_p1.x);
var line1_b:Number = 1/(line1_p2.y - line1_p1.y);
var line1_c:Number = (line1_a*line1_p1.x  +  -1*line1_b*line1_p1.y)*-1;
var line2_a:Number = 1/(line2_p2.x - line2_p1.x);
var line2_b:Number = 1/(line2_p2.y - line2_p1.y);
var line2_c:Number = (line2_a*line1_p1.x  +  -1*line2_b*line2_p1.y)*-1;

var matrix1:Matrix = new Matrix(line1_a , line1_b*-1 , line2_a , line2_b*-1 );
var matrix2:Matrix = new Matrix(line1_c*-1 , line2_c*-1 );
var matrix3:Matrix = new Matrix();
if(matrix1.a*matrix1.d == matrix1.b*matrix1.c) {   //만약 역행렬이 존재하지 않으면
   if(matrix2.a/matrix2.c != matrix1.a/matrix2.c) {  //만약 두 직선이(일치하지 않고)평행하면
       //두  직선(선분)이 평행하므로 교차하지 않음
   }
   else {
     // 두 직선이 일치함. 상황에 따라 추가 코딩.
   }
}
else {  //(위의 if의 부정을 받아)만약 역행렬이 존재하면,
   matrix1.invert();                                 //행렬1을 역행렬화 함
   matrix3 = matrix1.concat(matrix2);        //행렬1과 행렬2의 행렬곱을 구해서 행렬3에 대입
}



일단 이렇게해서 두 직선의 교점의 좌표가 행렬3에 들어가게 됩니다.
위쪽의 행렬수식을 참고하면
matrix3.a 에는 교점의 x좌표가 들어가고
matrix3.c 에는 교점의 y좌표가 들어간다는 것을 알 수 있습니다.

그런데 구하려는 것은 직선의 교점이 아닌 선분의 교점입니다.
구한 (교)점이 선분에 포함되는지를 체크해야 합니다.

if( Math.min(line1_p1.x,line1_p2.x) <= matrix3.a  &&  Math.max(line1_p1.x,line1_p2.x) >= matrix3.a 
    Math.min(line1_p1.y,line1_p2.y) <= matrix3.b  &&  Math.max(line1_p1.y,line1_p2.y) >= matrix3.b  
    &&
    Math.min(line2_p1.x,line2_p2.x) <= matrix3.a  &&  Math.max(line2_p1.x,line2_p2.x) >= matrix3.a 
    Math.min(line2_p1.y,line2_p2.y) <= matrix3.b  &&  Math.max(line2_p1.y,line2_p2.y) >= matrix3.b ) 
   { 
      //교차.
   }
else {
   //교차하지 않음.
}


이렇게 교차여부와 교점의 좌표를 구할 수 있습니다.
(교차여부 확인하는 코드는 더 짧게 줄일 수 있지만 여기서는 쉽게 하기위해서, 교점좌표가 두 선분의 사이에 있는지 
 부등호를 사용하여 조건을 작성했습니다.)