Arkanoid and PyGame Collision Detection

Published August 23, 2020
Advertisement

Background

I chose to write an Arkanoid-like clone (see the original below), assuming this would be a relatively simple place to start with PyGame.

Arkanoid. Fresh outta the 80s.

So I coded away and felt joy and satisfaction as I quickly implemented a sprite sheet loader, platform movement, block and level loading. It was all going so well… until I came to writing the projectile (silver ball) interaction with the blocks, ie: reflection.

The Problem - Collision and Edge Detection

The collision detection part was relatively easy. PyGame has a simple API for collision detection for rectangle-rectangle and circle-circle collisions. Where I got stuck was determining which side of a block the projectile had struck. Without that, the game would not know which direction the projectile should rebound.

I tried to implement edge-detection using PyGame's rectangle-rectangle collision detection, coupled with various methods I researched on the internet. For all my effort, the code was complex and the results were sketchy. The projectile rebounded unpredictably near the corners of the block and tunnelled through the block in some implementations.

Below is a simplified sketch of the problem. In Arkanoid, the projectile can hit the block at any position and angle.

Problem: The incoming projectile can hit the block from any angle.
How can we determine which side in order to reflect it logically?

My Solution

Recognising that the circular projectile was not modelled adequately by a rectangle in this game, I researched circle-rectangle collision detection and found two methods which helped me solve the problem. I used clamps to determine whether the projectile had collided with the block. Then I used a vector dot-product comparison to determine which side of the block intersected with the projectile's collision path.

Circle-Rectangle Collision Detection Using Clamps

Using a helpful You-tuber's advice, I wrote the following code to detect when the projectile (modelled as a circle) had “moved into” the block (modelled as a rectangle).

	def clamp(self, minimum, maximum, value):
		return max(minimum, min(maximum, value))

	def collided_with_circle(self, sprite_circle, sprite_rect):
		point_on_block = Vector2(self.clamp(sprite_rect.rect.x,
												sprite_rect.rect.x + sprite_rect.rect.w,
												sprite_circle.rect.center[0]),
									self.clamp(sprite_rect.rect.y,
												sprite_rect.rect.y + sprite_rect.rect.h,
												sprite_circle.rect.center[1]))
		circle_centre_to_block = sprite_circle.rect.center - point_on_block
		
		return circle_centre_to_block.magnitude() < sprite_circle.radius

Note that my Projectile and Block classes are both derived from PyGame's Sprite, hence they must both own a rect member of type Rect. The integer-indexed variables (center[0] and center[1]) represent x and y values respectively while variables w and h represent width and height.

Additionally, my Projectile class owns a radius member which is simply the width of it's rectangle divided by two.

Edge-Detection Using Vector Dot Products

Thanks to GameDev's page on Vector Maths, I found the right tool for this problem: using a dot-product comparison to check for a line's intersection with a plane.

The maths resolves the intersection of the collision path with a test plane, based on the surface normal (a unit vector pointing out of the surface) of the edge under test.

In the diagram below, the points indicated by the collision path form the line segment. The test plane is represented by the surface normal, in this case the vector: SN = [-1, 0].

The projectile's path as it collides with the block forms a line
segment. We can use that to determine which side of the
block was hit by the projectile.

By comparing dot products as described in the GameDev Vector Maths page, we can determine whether the collision path intersects with the block side wall, or whether it runs parallel to it (does not intersect). The code in projectile_intersects() below demonstrates how to use this dot-product comparison to determine which edge of the block was hit by the projectile.

    def on_collision(self, collision_detector: CollisionDetector) -> None:
        sprite_group = collision_detector.collided_sprite_group
        if (sprite_group.group_type == SpriteGroupType.BLOCKS or
                sprite_group.group_type == SpriteGroupType.BOUNDARIES or
                sprite_group.group_type == SpriteGroupType.PLATFORM):
            for collided_sprite in collision_detector.collided_sprites:
                test_surfaces = [
                    TestSurface("top", (0, -1), collided_sprite.rect.midtop),
                    TestSurface("right", (1, 0), collided_sprite.rect.midright),
                    TestSurface("bottom", (0, 1), collided_sprite.rect.midbottom),
                    TestSurface("left", (-1, 0), collided_sprite.rect.midleft)
                ]

                for test_surface in test_surfaces:
                    if self.projectile_intersects(test_surface.surface_test_point, test_surface.surface_normal):
                        self.reflect(test_surface.surface_normal)
                        if sprite_group.group_type == SpriteGroupType.BLOCKS:
                            event = BlockHitEvent(collided_sprite, collided_sprite.rect.midbottom)
                            self.event_bus.publish(event)
                        return

    def projectile_intersects(self, surface_test_point, surface_normal):
        # Line-plane intersection algorithm based on dot-product comparison.
        # https://pygamerist.blogspot.com/2020/06/arkanoid-and-collision-detection.html
        projectile_edge_point = Vector2(self.rect.center) - self.radius * surface_normal
        previous_projectile_edge_point = Vector2(self.previous_rect.center) - self.radius * surface_normal
        projectile_collision_path = projectile_edge_point - previous_projectile_edge_point
        dot1 = surface_normal.dot(surface_test_point - previous_projectile_edge_point)
        dot2 = surface_normal.dot(projectile_collision_path)

        if dot2 == 0.0:
            return False

        return 0 < dot1 / dot2 <= 1

    def reflect(self, surface_normal):
        self.velocity = self.velocity.reflect(surface_normal)
        self.rect.center += self.radius * surface_normal

 

Conclusions

Using a combination of clamp collision detection and dot-product edge detection the game reflects the projectile as expected.

There was one occasional glitch when the projectile would appear to hit two adjacent blocks at the same time: sometimes the block closest to the projectile was left while the adjacent block was destroyed. This occurred because the collision detection code was only used to find the first collided object, whereas multiple collisions can occur simultaneously when there are adjacent blocks. It is a simple thing to fix: the clamp collision detection code must find all collided objects, then return only the block closest to the projectile.

The full code for the game can be found here.

0 likes 0 comments

Comments

Nobody has left a comment. You can be the first!
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Advertisement
Advertisement