Circle-Rectangle Collision Detection

[davisdude]

So, let me start out by saying that I already have a code that sort of works... or at least it looks like it... from far away.

This is the code I have so far (FYI: I have the bullet very slow and large for testing purposes)-
bullet.lua:

Code: Select all

require "enemy"

bullet = {}
bullet.speed = 500

function bullet:draw()
	for i, v in ipairs(bullet) do
		if v.id == true then
			love.graphics.setColor( 255, 255, 255 )
			love.graphics.circle( "fill", v.x, v.y, v.r )
		end
	end
end

function bullet:update(dt)
	for i, v in ipairs(bullet) do 
		if v.id == true then
			v.x = v.x + v.dx * dt
			v.y = v.y + v.dy * dt
		else
			v.x = nil
			v.y = nil
			v.r = nil
		end
	end
end

function bullet:shoot( x, y )
	mouseX = x
	mouseY = y
	
	startX = player.x
	startY = player.y
	
	dir = math.atan2(( mouseY - player.y ), ( mouseX - player.x ))
	
	bulletDx = bullet.speed * math.cos(dir)
	bulletDy = bullet.speed * math.sin(dir)
	
	table.insert( bullet, { x = startX, y = startY, dx = bulletDx, dy = bulletDy, r = 200, id = true } )
end

function bullet:collide() --note that bullet.x and bullet.y are located in the middle of the circle.
	for i, bullet in ipairs(bullet) do
		for ii, enemy in ipairs(enemy) do
			if bullet.id == true then
				if bullet.x + bullet.r > enemyA and
				bullet.x - bullet.r < enemyB and
				bullet.y + bullet.r > enemyA and
				bullet.y - bullet.r < enemyC then
					print("hit!")
					bullet.id = false
					enemy.id = false
				end
			end
		end
	end
end

enemy.lua:

Code: Select all

enemy = {}

function enemy:draw()
	for i, v in ipairs(enemy) do
		if v.id == true then
			love.graphics.setColor( 255, 0, 0 )
			love.graphics.rectangle( "fill", v.x, v.y, v.w, v.h )
		end
	end
end

function enemy:update(dt)	
	for i, v in ipairs(enemy) do
		if v.id == true then
			enemyA = v.x
			enemyB = v.x + v.w
			enemyC = v.y + v.h
		end
	end
end

function enemy:load( x, y, w, h )
	table.insert( enemy, { x = x, y = y, w = w, h = h, id = true } )
end

main.lua:

Code: Select all

function love.load() --Run only at start of game
	enemy:load( 400, 400, 32, 32 )
end

function love.draw() --Run every time game can
	player:draw()
	bullet:draw()
	enemy:draw()
end

function love.update(dt) --Run every time the game can
	bullet:update(dt)
	bullet:collide()
	player:update(dt)
	enemy:update(dt)
end

I guess what I'm really wondering is if there is a better way to do this without using HardAgon?
You can also use the arrow keys to move the player around just to speed up the process if you like.

[stampede247]

So I don't actually have an exact answer for you but I wanna say one thing. Precise circle vs rectangle collision is A LOT of work and frankly usually isn't useful for how computer intensive it is going to be, especially for something like a bullet that will probably have many of on the screen, and especially for something that's gonna be such a small circle. Now if you want to do this go and search through google something like "rectangle vs. circle". However my suggestion would be to use just a simple AABB rectangle vs rectangle test for the bullet and you will rarely get any false positives if the bullet is small. Or you could treat the player like another circle because circle vs circles tests are very easy, it's just a matter of calculating distance. Also if your bullets are going to be moving fast then you might want to consider the possibility of using a "sweep test" rather than just a simple intersection test so that the bullets don't ever pass through your player due to low framerate or such. These types of tests are going to be harder but in the end usually less intensive on the computer than the alternatives.

Anyways thought I'd share my ideas/experience with this.

p.s. I've tried to do precise rectangle vs circle test (following a website that explained how) but after about 4 hours of testing, retrying, debugging and frustration I decided it wasn't worth it. But you are welcome to try for yourself if you want haha. let me know if you succeed

[stampede247]

HOLD UP! I just had a wonderful idea! haha

I still suggest most of what I said in the last post, however I just thought of an idea of how you could do a simple hack for rectangle vs circle collision. I beleive this should work in most (if not all) cases and is really simple to check. All you need to know how to do is check point vs rectangle and point vs circle. Ask me if you need to know how to do that.

Anyways let me give you an illustration (see attachment). So essentially all you have to do is this.

1. Go through each corner point on the rectangle and check if they are inside the circle (red points). This should actually cover a lot of the scenarios if you wanna just do that.
2. If you want more precision go through four points around the circle that align with the center axis and check if they are inside the rectangle (blue points)

You can stop the calculations and return true if ANY of the steps come back true.

Let me know if you try this I think it would work great. If you want an example I may have time tomorrow or you might be able to get somebody else to make one. Hope this helps!

EDIT: (sorry I keep thinking about this and revising) I did realize a short coming of this method. If the rectangle is really long and extends all the way through the circle without overlapping any of the circle's points it will return false. However with bullets this shouldn't be much of a problem

[Santos]

Here's an example:

Code: Select all

function love.load()
	circle_radius = math.random(10, 150)
	circle_x = math.random(circle_radius, love.graphics.getWidth() - circle_radius)
	circle_y = math.random(circle_radius, love.graphics.getHeight() - circle_radius)


	rectangle_width = math.random(10, 300)
	rectangle_height = math.random(10, 300)
	rectangle_x = math.random(0, love.graphics.getWidth() - rectangle_width)
	rectangle_y = math.random(0, love.graphics.getHeight() - rectangle_height)
end

function love.draw()
	if circle_and_rectangle_overlap(circle_x, circle_y, circle_radius, rectangle_x, rectangle_y, rectangle_width, rectangle_height) then
		love.graphics.setColor(0, 255, 0)
	else
		love.graphics.setColor(255, 255, 255)
	end

	if point_in_circle(love.mouse.getX(), love.mouse.getY(), circle_x, circle_y, circle_radius) then
		circle_style = 'fill'
	else
		circle_style = 'line'
	end

	if point_in_rectangle(love.mouse.getX(), love.mouse.getY(), rectangle_x, rectangle_y, rectangle_width, rectangle_height) then
		rectangle_style = 'fill'
	else
		rectangle_style = 'line'
	end

	love.graphics.circle(circle_style, circle_x, circle_y, circle_radius)
	love.graphics.rectangle(rectangle_style, rectangle_x, rectangle_y, rectangle_width, rectangle_height)
end

function love.update(dt)
	if rectangle_selected then
		rectangle_x = love.mouse.getX() + rectangle_offset_x
		rectangle_y = love.mouse.getY() + rectangle_offset_y
	end

	if circle_selected then
		circle_x = love.mouse.getX() + circle_offset_x
		circle_y = love.mouse.getY() + circle_offset_y
	end
end

function love.mousepressed(mouse_x, mouse_y)
	if point_in_rectangle(mouse_x, mouse_y, rectangle_x, rectangle_y, rectangle_width, rectangle_height) then
		rectangle_selected = true
		rectangle_offset_x = rectangle_x - mouse_x
		rectangle_offset_y = rectangle_y - mouse_y
	end

	if point_in_circle(mouse_x, mouse_y, circle_x, circle_y, circle_radius) then
		circle_selected = true
		circle_offset_x = circle_x - mouse_x
		circle_offset_y = circle_y - mouse_y
	end
end

function love.mousereleased()
	rectangle_selected = false
	circle_selected = false
end

function love.keypressed()
	love.load()
end

function circle_and_rectangle_overlap(cx, cy, cr, rx, ry, rw, rh)
	local circle_distance_x = math.abs(cx - rx - rw/2)
	local circle_distance_y = math.abs(cy - ry - rh/2)

	if circle_distance_x > (rw/2 + cr) or circle_distance_y > (rh/2 + cr) then
		return false
	elseif circle_distance_x <= (rw/2) or circle_distance_y <= (rh/2) then
		return true
	end

	return (math.pow(circle_distance_x - rw/2, 2) + math.pow(circle_distance_y - rh/2, 2)) <= math.pow(cr, 2)
end

function point_in_rectangle(point_x, point_y, left, top, width, height)
	return point_x >= left
	and point_x <= left + width
	and point_y >= top
	and point_y <= top + height
end

function point_in_circle(point_x, point_y, circle_x, circle_y, circle_radius)
    return (math.pow(circle_x - point_x, 2) + math.pow(circle_y - point_y, 2)) <= math.pow(circle_radius, 2)
end

overlap_example.love

(863 Bytes) Downloaded 358 times

You can click and drag the circle and the rectangle, and you can randomise the circle and rectangle position and size by pressing any key. This example is maybe a bit more complicated than it needs to be, sorry about that.

Here's an explanation of the the circle and rectangle collision function: http://stackoverflow.com/a/402010

[davisdude]

First of all I want to thank you all for your help. I will implement Santos' code (or something of the sort) to use. Thanks also to Stampede 247. You both have really helped me quite a bit. While I have you, do you mind me asking if there is a better way to stop drawing/updating the bullet than what I already have (with the changing id to false if it hits)?
Once again, thanks to all of you!

[Santos]

You're welcome!

You could just remove the bullets and enemies from their tables maybe:

Code: Select all

function bullet:collide() --note that bullet.x and bullet.y are located in the middle of the circle.
	for b = #bullet, 1, -1 do
		for e = #enemy, 1, -1 do
			if bullet[b].x + bullet[b].r > enemy[e].x and
			bullet[b].x - bullet[b].r < enemy[e].x + enemy[e].w and
			bullet[b].y + bullet[b].r > enemy[e].x and
			bullet[b].y - bullet[b].r < enemy[e].y + enemy[e].h then
				print("hit!")
				table.remove(bullet, b)
				table.remove(enemy, e)
			end
		end
	end
end

Here is the reason for not using ipairs for looping through the tables when items are being removed from them: http://love2d.org/forums/viewtopic.php? ... 254#p73380

[davisdude]

Here is hopefully the final code. One question though: Is it okay if I keep using ipairs for draw and update? It works fine, but I don't know if there is a better way to do it. Thanks in advance!
main.lua-

Code: Select all

require "player"
require "enemy"
require "bullet"

function love.load()
	love.graphics.setBackgroundColor( 255, 255, 255 )
	enemy:load( 128, 128, 32, 32 )
end

function love.draw()
	player:draw()
	enemy:draw()
	bullet:draw()
end

function love.update(dt)
	player:update(dt)
	bullet:update(dt)
end

function love.mousepressed( bullet_x, bullet_y )
	bullet:load( bullet_x, bullet_y, 2 )
end

player.lua (slightly irrelevant, but whatever)-

Code: Select all

player = {}
player.x = 32
player.y = 32
player.w = 32
player.h = 32

function player:draw()
	love.graphics.setColor( 0, 255, 0 )
	love.graphics.rectangle( "fill", player.x, player.y, player.w, player.h )
end

function player:update(dt)
	if love.keyboard.isDown('w') or love.keyboard.isDown('up') then
		player.y = player.y - 192 * dt
	end
	if love.keyboard.isDown('a') or love.keyboard.isDown('left') then
		player.x = player.x - 192 * dt
	end
	if love.keyboard.isDown('s') or love.keyboard.isDown('down') then
		player.y = player.y + 192 * dt
	end
	if love.keyboard.isDown('d') or love.keyboard.isDown('right') then
		player.x = player.x + 192 * dt
	end
end

enemy.lua-

Code: Select all

enemy = {}

function enemy:draw()
	for i, v in ipairs(enemy) do
		love.graphics.setColor( 255, 0, 0 )
		love.graphics.rectangle( "fill", v.x, v.y, v.w, v.h )
	end
end

function enemy:load( x, y, w, h )
	table.insert( enemy, { x = x, y = y, w = w, h = h } )
end

function enemy:getPoints( point_x, point_y, left, top, width, height )
	return point_x >= left
	and point_x <= left + width
	and point_y >= top
	and point_y <= top + height
end

bullet.lua-

Code: Select all

bullet = {}
bullet.speed = 500

function bullet:load( bullet_x, bullet_y, bullet_r )
	bullet.speed = 500
	
	startX = player.x + player.w + bullet_r/2
	startY = player.y + player.h/2 + bullet_r/2
	
	dir = math.atan2(( bullet_y - startY ), ( bullet_x - startX ))
	
	bulletDx = bullet.speed * math.cos(dir)
	bulletDy = bullet.speed * math.sin(dir)
	
	table.insert( bullet, { x = startX, y = startY, dx = bulletDx, dy = bulletDy, id = true, r = 2 } )
end

function bullet:draw()
	for i, v in ipairs(bullet) do
		if v.id == true then
			love.graphics.setColor( 0, 0, 0 )
			love.graphics.circle( "fill", v.x, v.y, v.r )
		end
	end
end

function bullet:update(dt)
	for i, v in ipairs(bullet) do
		if v.id == true then
			v.x = v.x + v.dx * dt
			v.y = v.y + v.dy * dt
		end
	end
	
	bullet:collide(  )
end

function bullet:collide()
   for b = #bullet, 1, -1 do
      for e = #enemy, 1, -1 do
         if bullet_and_enemy_overlap( bullet[b].x, bullet[b].y, bullet[b].r, enemy[e].x, enemy[e].y, enemy[e].w, enemy[e].h ) then
            print("hit!")
            table.remove(bullet, b)
            table.remove(enemy, e)
         end
      end
   end
end

function bullet_and_enemy_overlap( cx, cy, cr, rx, ry, rw, rh ) --circle is circle, r is rectangle
	local circle_distance_x = math.abs(cx - rx - rw/2)
	local circle_distance_y = math.abs(cy - ry - rh/2)

	if circle_distance_x > (rw/2 + cr) or circle_distance_y > (rh/2 + cr) then
		return false
	elseif circle_distance_x <= (rw/2) or circle_distance_y <= (rh/2) then
		return true
	end

	return (math.pow(circle_distance_x - rw/2, 2) + math.pow(circle_distance_y - rh/2, 2)) <= math.pow(cr, 2)
end

function bullet:getPoints( point_x, point_y, circle_x, circle_y, circle_radius )
	return (math.pow(circle_x - point_x, 2) + math.pow(circle_y - point_y, 2)) <= math.pow(circle_radius, 2)
end