운석 피하기 게임 개발(11)- 충돌처리(3)(Sweep And Prune알고리즘)

 

지난 포스트에서 개발된 충돌검사는

실제로 충돌하는 부분이 아닌

이미지의 공백 부분까지 확인해서 처리하기 때문에

실제 화면에서 충돌하지 않았는데도 불구하고 충돌 처리가 되는 증상이 있었다.

이번 포스트에서 올린 부분 내용은

그 문제를 보완하고 중요한 충돌검사의 효율을 높이는 방법을 설명하겠다.

 

Sweep And Prune 알고리즘

SAP로 불리는 sweep and prune 알고리즘은 다수의 충돌 검사를 조금 더 효율적으로 처리해 준다.

지난 포스트에서 사용할 rect collider의 경우에는 x축과 y을 모두 검사하는 방식이라면

SAP의 경우는 x축만을 이용하여 검사를 한다.

아래 그림 처럼 운석과 기체의 위치가 있다고 가정해 보자.

지난 번 로직은 지금 화면에 있는 모든 사물의 충돌 검사를 위치와 관계없이 처리하는데 비해

SAP의 경우 아래와 같이 위치가 비슷하게 있는 아래 붉은색 박스 영역만을 처리한다.

SAP 알고리즘은 위의 박스 영역을 효율적으로 찾아주는 알고리즘이다.

코드를 한번 살펴보자.

def check_collision(self):
        self.collision_check_list.append(self.player_sprites.sprites()[0])
        
        for sprite in self.meteor_sprites.sprites():
            self.collision_check_list.append(sprite)
        
        # Sweep and Prone 알고리즘
        # x축만 정렬
        self.collision_check_list.sort(key=lambda sprite: sprite.rect.x)

        for i in range(len(self.collision_check_list)):
            sprite_a = self.collision_check_list[i]
            for j in range(i + 1, len(self.collision_check_list)):
                sprite_b = self.collision_check_list[j]
                # sprite_a가 화면 밖에 있는 경우, 충돌 검사할 필요가 없기 때문에 skip
                if sprite_a.rect.x + sprite_a.rect.width < 0 or sprite_a.rect.x > env.WIDTH:
                    break

# sprite_a와 sprite_b의 x 위치를 비교, 만약 겹치는 부분이 없다면 
# 그 뒤의 sprite_b는 검사할 필요가 없다.
# x축에 따라 정렬된 list 이기 때문에 무조건 충돌하지 않음, 따라서 skip
                if sprite_a.rect.x + sprite_a.rect.width < sprite_b.rect.x:
                    break

                # sprite_a와 sprite_b가 겹치는 경우, 
                # collide_mask를 통해 조금 더 충돌 검사의 정밀도를 높임
                if sprite_a.rect.x <= sprite_b.rect.x and \
                   sprite_a.rect.x + sprite_a.rect.width >= sprite_b.rect.x:
                    if pygame.sprite.collide_mask(sprite_a, sprite_b):
                        sprite_a.handle_collision(sprite_b.velocity, sprite_b.mass)
                        sprite_b.handle_collision(sprite_a.velocity, sprite_a.mass)

        self.collision_check_list.clear()

 

1. 우선 sprite 간의 충돌 검사를 진행할 list를 x축 값을 기준으로 정렬을 한다. y축은 신경 쓰지 않는다.

정렬이 완료되면 y축은 무시된 채로 아래와 같이 x 축 기준으로 sprites가 위치할 것이다.

 

2. 화면 밖에 위치한 녀석은 제외한다. (화면 밖에 위치한 녀석은 굳이 충돌 검사를 할 필요가 없음으로 skip)

 

 

3. 1번부터 충돌검사를 시작한다.

4. 1번 다음인 2번과 검사를 시작한다. 만약 1번과 2번이 x축이 겹치지 않는다면 2번 이후의 모든 번호는 무조건 충돌하지 않게 된다. 생각해보라. 지금 우리는 x축 기준으로 이미 정렬을 해 둔 상태이다. 절대 충돌할 수가 없다. 따라서 다른 것과 충돌 체크 없이 그냥 skip하고 2번으로 넘어간다.

5. 2번과 3번도 위의 과정을 계속 반복한다. 충돌하지 않는다면 3번 다음 녀석도 절대 충돌할 수 없으니 skip

 

위의 알고리즘대로 1번부터 8번까지 돌리게 되면 4번과 5번만 충돌 가능성이 있기 때문에

실제로 한번만 충돌 검사를 하고 나머지는 판단 여부를 체크하는 부분 1회만 돌리고 skip하게 된다.

 

기존의 알고리즘은 말 그대로 이런 체크없이 무조건 돌리기 때문에

화면에 8개의 sprite가 있다면

8 x 7 = 56로 총 56회를 검사를 해야했다.

하지만 SAP 알고리즘을 활용하면 총 8회의 검사와 1번의 실제 충돌체크를 수행하게 되어

훨씬 더 빠르게 처리가 가능한다.

if sprite_a.rect.x <= sprite_b.rect.x and \
   sprite_a.rect.x + sprite_a.rect.width >= sprite_b.rect.x:
    if pygame.sprite.collide_mask(sprite_a, sprite_b):
        sprite_a.handle_collision(sprite_b.velocity, sprite_b.mass)
        sprite_b.handle_collision(sprite_a.velocity, sprite_a.mass)

 

그리고 기존의 collide_rect 대신 collide_mask를 사용해서 충돌 검사를 수행한다.

mask를 사용하면 sprite의 투명화된 부분은 제외한 색상이 있는 부분끼리 겹치는 것을 검사하게 된다.

따라서 이는 기존의 collide_rect보다 훨씬 더 현실적인 충돌 판정을 하게 된다.

대신에 이미지 처리가 들어가서 계산하는 속도가 collide_rect보다 훨씬 오래 걸린다.

 

그래서 SAP를 사용하지 않으면

mask 검사하는 시간이 훨씬 오래 걸리기 때문에 화면에 운석이 많아질수록

속도가 느려지게 된다.

SAP을 사용하게 되면 운석 갯수가 많아져도

충돌 검사 자체 횟수가

충돌 가능성이 있는 sprite 갯수에서 크게 벗어나지 않기에 

훨신 더 빠른 처리가 가능하다.

 

소스 코드를 첨부한다.

현재 코드 상 collider 부분은 main.py 에 있는데

이를 분리해서 따로 만들어 보는 것도 도움이 될 것이다.

09. sap.zip

0.03MB