java collision detection between two rotated rectangles
Collision detection is simple in only two cases:
- between circles
- between aligned rectangles
SmashCode explained how to detect collisions between circles.
Aligned rectangles are even easier, you only need to compare does maximal and minimal coordinates of rectangles overlap.
Sadly yours case is none of above. These rectangles have different coordinate systems and due their rotations edges of one of ractangles may be nether perpendicular nor parallel to axis of second one and they cannot be treated like that.
One of ways is to use bounding boxes like you did here:
if(a.getBounds2D().intersects(car)){
System.out.println("Collision!");
}
Calling a.getBounds2D() creates rectangle that is aligned to coordinate system and covers whole shape. But bounding box will also cover some space not occupied by shape. So checking for collision between aligned rectangle and bounding box of rotated one is fast and easy but may produce false positives like shown in
drawing of rectangles and bounding box of rotated one.
To fully and accurately check for collision you need to use some more sophisticated methods like SAT that use casting(projecting) of polygons onto different axis. Fact that you are working with only rectangles means that you will only need two axes and you already know their directions.
PS. Using bounding box isn't wrong, it is easy way to check if two figures are not colliding(if bounding boxes don't collide figures can't collide), you can still use it as faster pre-check to eliminate obvious cases.
How can I detect collision between two moving sprites?
You have to check if the player collides with an enemy in the main loop:
e.g.
run = True
hit_count = 0
while run:
# [...]
player.rect.clamp_ip(screen_rect)
collidelist = pygame.sprite.spritecollide(player, enemies_list, False)
if collidelist:
hit_count += 1
print("hit", hit_count)
draw_window()
If you want to fins initial enemy positions, which are not "on" the player, you've to check for collision of a new enemy and the player before you add it to enemies_list respectively all_sprites:
e.g.
def collision():
score = 0
while len(enemies_list) < 5:#
enemy = Enemy((randint(0, 600), randint(0, 600)))
if not pygame.sprite.collide_rect(enemy, player):
enemies_list.add(enemy)
all_sprites.add(enemy)
How to check intersection between 2 rotated rectangles?
- For each edge in both polygons, check if it can be used as a separating line. If so, you are done: No intersection.
- If no separation line was found, you have an intersection.
/// Checks if the two polygons are intersecting.
bool IsPolygonsIntersecting(Polygon a, Polygon b)
{
foreach (var polygon in new[] { a, b })
{
for (int i1 = 0; i1 < polygon.Points.Count; i1++)
{
int i2 = (i1 + 1) % polygon.Points.Count;
var p1 = polygon.Points[i1];
var p2 = polygon.Points[i2];
var normal = new Point(p2.Y - p1.Y, p1.X - p2.X);
double? minA = null, maxA = null;
foreach (var p in a.Points)
{
var projected = normal.X * p.X + normal.Y * p.Y;
if (minA == null || projected < minA)
minA = projected;
if (maxA == null || projected > maxA)
maxA = projected;
}
double? minB = null, maxB = null;
foreach (var p in b.Points)
{
var projected = normal.X * p.X + normal.Y * p.Y;
if (minB == null || projected < minB)
minB = projected;
if (maxB == null || projected > maxB)
maxB = projected;
}
if (maxA < minB || maxB < minA)
return false;
}
}
return true;
}
For more information, see this article: 2D Polygon Collision Detection - Code Project
NB: The algorithm only works for convex polygons, specified in either clockwise, or counterclockwise order.
Rotating character and sprite wall
It all depends on how your sprite looks and how you want the result to be. There are 3 different types of collision detection I believe could work in your scenario.
Keeping your rect from resizing
Since the image is getting larger when you rotate it, you could compensate by just removing the extra padding and keep the image in it's original size.
Say that the size of the original image is 32 pixels wide and 32 pixels high. After rotating, the image is 36 pixels wide and 36 pixels high. We want to take out the center of the image (since the padding is added around it).
To take out the center of the new image we simply take out a subsurface of the image the size of our previous rectangle centered inside the image.
def rotate(self, degrees):
self.rotation = (self.rotation + degrees) % 360 # Keep track of the current rotation.
self.image = pygame.transform.rotate(self.original_image, self.rotation))
center_x = self.image.get_width() // 2
center_y = self.image.get_height() // 2
rect_surface = self.rect.copy() # Create a new rectangle.
rect_surface.center = (center_x, center_y) # Move the new rectangle to the center of the new image.
self.image = self.image.subsurface(rect_surface) # Take out the center of the new image.
Since the size of the rectangle doesn't change we don't need to do anything to recalculate it (in other words: self.rect = self.image.get_rect() will not be necessary).
Rectangular detection
From here you just use pygame.sprite.spritecollide (or if you have an own function) as usual.
def collision_rect(self, walls):
last = self.rect.copy() # Keep track on where you are.
self.rect.move_ip(*self.velocity) # Move based on the objects velocity.
current = self.rect # Just for readability we 'rename' the objects rect attribute to 'current'.
for wall in pygame.sprite.spritecollide(self, walls, dokill=False):
wall = wall.rect # Just for readability we 'rename' the wall's rect attribute to just 'wall'.
if last.left >= wall.right > current.left: # Collided left side.
current.left = wall.right
elif last.right <= wall.left < current.right: # Collided right side.
current.right = wall.left
elif last.top >= wall.bottom > current.top: # Collided from above.
current.top = wall.bottom
elif last.bottom <= wall.top < current.bottom: # Collided from below.
current.bottom = wall.top
Circular collision
This probably will not work the best if you're tiling your walls, because you'll be able to go between tiles depending on the size of the walls and your character. It is good for many other things so I'll keep this in.
If you add the attribute radius to your player and wall you can use pygame.sprite.spritecollide and pass the callback function pygame.sprite.collide_circle. You don't need a radius attribute, it's optional. But if you don't pygame will calculate the radius based on the sprites rect attribute, which is unnecessary unless the radius is constantly changing.
def collision_circular(self, walls):
self.rect.move_ip(*self.velocity)
current = self.rect
for wall in pygame.sprite.spritecollide(self, walls, dokill=False, collided=pygame.sprite.collide_circle):
distance = self.radius + wall.radius
dx = current.centerx - wall.rect.centerx
dy = current.centery - wall.rect.centery
multiplier = ((distance ** 2) / (dx ** 2 + dy ** 2)) ** (1/2)
current.centerx = wall.rect.centerx + (dx * multiplier)
current.centery = wall.rect.centery + (dy * multiplier)
Pixel perfect collision
This is the hardest to implement and is performance heavy, but can give you the best result. We'll still use pygame.sprite.spritecollide, but this time we're going to pass pygame.sprite.collide_mask as the callback function. This method require that your sprites have a rect attribute and a per pixel alpha Surface or a Surface with a colorkey.
A mask attribute is optional, if there is none the function will create one temporarily. If you use a mask attribute you'll need to change update it every time your sprite image is changed.
The hard part of this kind of collision is not to detect it but to respond correctly and make it move/stop appropriately. I made a buggy example demonstrating one way to handle it somewhat decently.
def collision_mask(self, walls):
last = self.rect.copy()
self.rect.move_ip(*self.velocity)
current = self.rect
for wall in pygame.sprite.spritecollide(self, walls, dokill=False, collided=pygame.sprite.collide_mask):
if not self.rect.center == last.center:
self.rect.center = last.center
break
wall = wall.rect
x_distance = current.centerx - wall.centerx
y_distance = current.centery - wall.centery
if abs(x_distance) > abs(y_distance):
current.centerx += (x_distance/abs(x_distance)) * (self.velocity[0] + 1)
else:
current.centery += (y_distance/abs(y_distance)) * (self.velocity[1] + 1)
Full code
You can try out the different examples by pressing 1 for rectangular collision, 2 for circular collision and 3 for pixel-perfect collision. It's a little buggy in some places, the movement isn't top notch and isn't ideal performance wise, but it's just a simple demonstration.
import pygame
pygame.init()
SIZE = WIDTH, HEIGHT = (256, 256)
clock = pygame.time.Clock()
screen = pygame.display.set_mode(SIZE)
mode = 1
modes = ["Rectangular collision", "Circular collision", "Pixel perfect collision"]
class Player(pygame.sprite.Sprite):
def __init__(self, pos):
super(Player, self).__init__()
self.original_image = pygame.Surface((32, 32))
self.original_image.set_colorkey((0, 0, 0))
self.image = self.original_image.copy()
pygame.draw.ellipse(self.original_image, (255, 0, 0), pygame.Rect((0, 8), (32, 16)))
self.rect = self.image.get_rect(center=pos)
self.rotation = 0
self.velocity = [0, 0]
self.radius = self.rect.width // 2
self.mask = pygame.mask.from_surface(self.image)
def rotate_clipped(self, degrees):
self.rotation = (self.rotation + degrees) % 360 # Keep track of the current rotation
self.image = pygame.transform.rotate(self.original_image, self.rotation)
center_x = self.image.get_width() // 2
center_y = self.image.get_height() // 2
rect_surface = self.rect.copy() # Create a new rectangle.
rect_surface.center = (center_x, center_y) # Move the new rectangle to the center of the new image.
self.image = self.image.subsurface(rect_surface) # Take out the center of the new image.
self.mask = pygame.mask.from_surface(self.image)
def collision_rect(self, walls):
last = self.rect.copy() # Keep track on where you are.
self.rect.move_ip(*self.velocity) # Move based on the objects velocity.
current = self.rect # Just for readability we 'rename' the objects rect attribute to 'current'.
for wall in pygame.sprite.spritecollide(self, walls, dokill=False):
wall = wall.rect # Just for readability we 'rename' the wall's rect attribute to just 'wall'.
if last.left >= wall.right > current.left: # Collided left side.
current.left = wall.right
elif last.right <= wall.left < current.right: # Collided right side.
current.right = wall.left
elif last.top >= wall.bottom > current.top: # Collided from above.
current.top = wall.bottom
elif last.bottom <= wall.top < current.bottom: # Collided from below.
current.bottom = wall.top
def collision_circular(self, walls):
self.rect.move_ip(*self.velocity)
current = self.rect
for wall in pygame.sprite.spritecollide(self, walls, dokill=False, collided=pygame.sprite.collide_circle):
distance = self.radius + wall.radius
dx = current.centerx - wall.rect.centerx
dy = current.centery - wall.rect.centery
multiplier = ((distance ** 2) / (dx ** 2 + dy ** 2)) ** (1/2)
current.centerx = wall.rect.centerx + (dx * multiplier)
current.centery = wall.rect.centery + (dy * multiplier)
def collision_mask(self, walls):
last = self.rect.copy()
self.rect.move_ip(*self.velocity)
current = self.rect
for wall in pygame.sprite.spritecollide(self, walls, dokill=False, collided=pygame.sprite.collide_mask):
if not self.rect.center == last.center:
self.rect.center = last.center
break
wall = wall.rect
x_distance = current.centerx - wall.centerx
y_distance = current.centery - wall.centery
if abs(x_distance) > abs(y_distance):
current.centerx += (x_distance/abs(x_distance)) * (self.velocity[0] + 1)
else:
current.centery += (y_distance/abs(y_distance)) * (self.velocity[1] + 1)
def update(self, walls):
self.rotate_clipped(1)
if mode == 1:
self.collision_rect(walls)
elif mode == 2:
self.collision_circular(walls)
else:
self.collision_mask(walls)
class Wall(pygame.sprite.Sprite):
def __init__(self, pos):
super(Wall, self).__init__()
size = (32, 32)
self.image = pygame.Surface(size)
self.image.fill((0, 0, 255)) # Make the Surface blue.
self.image.set_colorkey((0, 0, 0)) # Will not affect the image but is needed for collision with mask.
self.rect = pygame.Rect(pos, size)
self.radius = self.rect.width // 2
self.mask = pygame.mask.from_surface(self.image)
def show_rects(player, walls):
for wall in walls:
pygame.draw.rect(screen, (1, 1, 1), wall.rect, 1)
pygame.draw.rect(screen, (1, 1, 1), player.rect, 1)
def show_circles(player, walls):
for wall in walls:
pygame.draw.circle(screen, (1, 1, 1), wall.rect.center, wall.radius, 1)
pygame.draw.circle(screen, (1, 1, 1), player.rect.center, player.radius, 1)
def show_mask(player, walls):
for wall in walls:
pygame.draw.rect(screen, (1, 1, 1), wall.rect, 1)
for pixel in player.mask.outline():
pixel_x = player.rect.x + pixel[0]
pixel_y = player.rect.y + pixel[1]
screen.set_at((pixel_x, pixel_y), (1, 1, 1))
# Create walls around the border.
walls = pygame.sprite.Group()
walls.add(Wall(pos=(col, 0)) for col in range(0, WIDTH, 32))
walls.add(Wall(pos=(0, row)) for row in range(0, HEIGHT, 32))
walls.add(Wall(pos=(col, HEIGHT - 32)) for col in range(0, WIDTH, 32))
walls.add(Wall(pos=(WIDTH - 32, row)) for row in range(0, HEIGHT, 32))
walls.add(Wall(pos=(WIDTH//2, HEIGHT//2))) # Obstacle in the middle of the screen
player = Player(pos=(64, 64))
speed = 2 # Speed of the player.
while True:
screen.fill((255, 255, 255))
clock.tick(60)
for event in pygame.event.get():
if event.type == pygame.QUIT:
quit()
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_a:
player.velocity[0] = -speed
elif event.key == pygame.K_d:
player.velocity[0] = speed
elif event.key == pygame.K_w:
player.velocity[1] = -speed
elif event.key == pygame.K_s:
player.velocity[1] = speed
elif pygame.K_1 <= event.key <= pygame.K_3:
mode = event.key - 48
print(modes[mode - 1])
elif event.type == pygame.KEYUP:
if event.key == pygame.K_a or event.key == pygame.K_d:
player.velocity[0] = 0
elif event.key == pygame.K_w or event.key == pygame.K_s:
player.velocity[1] = 0
player.update(walls)
walls.draw(screen)
screen.blit(player.image, player.rect)
if mode == 1:
show_rects(player, walls) # Show rectangles for circular collision detection.
elif mode == 2:
show_circles(player, walls) # Show circles for circular collision detection.
else:
show_mask(player, walls) # Show mask for pixel perfect collision detection.
pygame.display.update()
Last note
Before programming any further you really need to refactor your code. I tried to read some of your code but it's really hard to understand. Try follow Python's naming conventions, it'll make it much easier for other programmers to read and understand your code, which makes it easier for them to help you with your questions.
Just following these simple guidelines will make your code much readable:
- Variable names should contain only lowercase letters. Names with more than 1 word should be separated with an underscore. Example:
variable,variable_with_words. - Functions and attributes should follow the same naming convention as variables.
- Class names should start with an uppercase for every word and the rest should be lowercase. Example:
Class,MyClass. Known as CamelCase. - Separate methods in classes with one line, and functions and classes with two lines.
I don't know what kind of IDE you use, but Pycharm Community Edition is a great IDE for Python. It'll show you when you're breaking Python conventions (and much more of course).
It's important to note that these are conventions and not rules. They are meant to make code more readable and not to be followed strictly. Break them if you think it improves readability.
Handling sprite collisions against an angled rectangular obstacle that is static
The answer is coordinate translation. Imagine that the rotated object had its own coordinate system, where x runs along the bottom of the rectangle, and y up the side on the left. Then, if you could find the position of your sprite in that coordinate system, you could check for collisions the way you normally would with an unrotated rectangle, i.e., if x >=0 and x <= width and y >=0 and y <= height then there's a collision.
But how do you get the translated coordinates? The answer is matrices. You can use 2d transformation matrices to rotate, scale and translate vectors and coordinates. Unfortunately my experience with these types of transformations is in C#, not python, but this page for instance provides examples and explanations in python using numpy.
Note that this is quite simply the way 2d (and 3d) games work - matrix transformations are everywhere, and are the way to do collision detection of rotated, scaled and translated objects. They are also how sprites are moved, rotated etc: the pygame transform module is a matrix transformation module. So if the code and explanations looks scary at first glance, it is worth investing the time to understand it, since it's hard to write games without it beyond a certain point.
I'm aware this is not a full answer to your question, since I haven't given you the code, but it's too long for a comment, and hopefully points you in the right direction. There's also this answer on SO, which provides some simple code.
EDIT: just to add some further information, a full collision detection routine would check each collidable pixel's position against the object. This may be the required approach in your game, depending on how accurate you need the collision detection to be. That's what I do in my game Magnetar (https://www.youtube.com/watch?v=mbgr2XiIR7w), which collides multiple irregularly shaped sprites at arbitrary positions, scales and rotations.
I note however that in your game there's a way you could possibly "cheat" if all you need is collision detection with some angled slopes. That is you could have a data structure which records the 'corners' of the ground (points it change angle), and then use simple geometry to determine if an x,y point is below or above ground. That is, you would take the x value of a point and check which segment of the ground it is over. If it is over the sloped ground, work out how far along the x axis of the sloped ground it is, then use the sin of the angle times this value to work out the y value of the slope at that position, and if that is greater than the y value of the point you are checking, you have a collision.
Related Topics
Java Wait for Thread to Finish
How to Most Elegantly Iterate Through Parallel Collections
How to Enumerate All Classes in a Package and Add Them to a List
Maven Compilation Error: (Use -Source 7 or Higher to Enable Diamond Operator)
Replace the Last Part of a String
Error: Servlet Jar Not Loaded... Offending Class: Javax/Servlet/Servlet.Class
Java 8 Instant.Now() with Nanosecond Resolution
Java Applet Game 2D Window Scrolling
Java Recursive Fibonacci Sequence
Why Java.Util.Optional Is Not Serializable, How to Serialize the Object with Such Fields
How to Validate an Xml File Using Java with an Xsd Having an Include
How to Convert String to Date Without Knowing the Format
Get the Changed HTML Content After It's Updated by JavaScript? (Htmlunit)