Collision Detection

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
Kuromeku
Party member
Posts: 166
Joined: Sun Jul 20, 2008 5:45 pm

Collision Detection

Post by Kuromeku » Sun Jul 20, 2008 5:58 pm

I made an almost perfect collision detection system:

Image
Image
Image

However... the problem is of course the FPS. There were only 32 entities in there, and what I'm doing is looping through each entity every update() and then looping through every entity again to check if two entity's bounding boxes are colliding. This is obviously a really bad thing to do in Lua because it's an interpreted language.

Help?

Please don't say wait for the new Love collision stuff because that isn't helping, that's a delay.

I only started using Love yesterday and already have a base game system working. It's just the collision...
Last edited by Kuromeku on Sun Jul 20, 2008 6:55 pm, edited 1 time in total.

User avatar
Kaze
Party member
Posts: 189
Joined: Sat Jul 19, 2008 4:39 pm
Location: Dublin, Ireland

Re: Collision Detection

Post by Kaze » Sun Jul 20, 2008 6:14 pm

You could try just looping through objects which are close to the object.

User avatar
Dr. Magnusson
Prole
Posts: 22
Joined: Sun Jul 20, 2008 6:10 pm

Re: Collision Detection

Post by Dr. Magnusson » Sun Jul 20, 2008 6:15 pm

Why did you post the same picture 3 times?

And how do you expect us to help you when you haven't posted any of the actual code for detecting collisions?

Also, does the energy of the boxes transfer to others on collision?

User avatar
Kuromeku
Party member
Posts: 166
Joined: Sun Jul 20, 2008 5:45 pm

Re: Collision Detection

Post by Kuromeku » Sun Jul 20, 2008 6:57 pm

It doesn't transfer yet. I planned to do that later.

This is the code that checks if two bounding boxes collide.

Code: Select all

		local ba = self:getBoundingBox();
		local bb = entity:getBoundingBox();
		
		-- Sort out the bounding boxes into groups.
		ba = { {ba[1], ba[2]}, {ba[2], ba[3]}, {ba[3], ba[4]}, {ba[4], ba[1]} };
		bb = { {bb[1], bb[2]}, {bb[2], bb[3]}, {bb[3], bb[4]}, {bb[4], bb[1]} };
		
		-- Loop through each bounding box structure.
		for k, v in pairs(ba) do
			for k2, v2 in pairs(bb) do
				local collision, x, y = hate.util.linesCollide(v[1], v[2], v2[1], v2[2]);
				
				-- Check if there is a collision.
				if (collision) then return true, x, y; end;
			end;
		end;
		
		-- Return false because there was no collision.
		return false;
That's the code that actually causes the bad FPS.

And as for checking only entities that are close, I still have to loop through every entity for that.

User avatar
rude
Administrator
Posts: 1051
Joined: Mon Feb 04, 2008 3:58 pm
Location: Oslo, Norway

Re: Collision Detection

Post by rude » Sun Jul 20, 2008 7:10 pm

Wow, that's a really crappy FPS. Do you check every object against every other?

User avatar
Kaze
Party member
Posts: 189
Joined: Sat Jul 19, 2008 4:39 pm
Location: Dublin, Ireland

Re: Collision Detection

Post by Kaze » Sun Jul 20, 2008 7:11 pm

rude wrote:Wow, that's a really crappy FPS. Do you check every object against every other?
That's what I was wondering..

User avatar
Kuromeku
Party member
Posts: 166
Joined: Sun Jul 20, 2008 5:45 pm

Re: Collision Detection

Post by Kuromeku » Sun Jul 20, 2008 7:21 pm

Yeah rude, I do:

Code: Select all

for k, v in pairs(hate.entities.spawned) do
        for k2, v2 in pairs(hate.entities.spawned) do
                  -- I check if the entities are close to each other here.
        end;
end;
Also rude, did you make Love? If so then good job, it's awesome.

I was thinking I could do the collision checking in a thread:

Code: Select all

	coroutine.resume(coroutine.create(function()
		for k, v in pairs( hate.entities.getAll() ) do
			v:onUpdate(delta);
			v:onHandlePhysics();
		end;
		hate.error = love.timer.getFPS().." FPS!";
	end));
But it still does it (I really don't think that's running a seperate thread like it should do).

User avatar
rude
Administrator
Posts: 1051
Joined: Mon Feb 04, 2008 3:58 pm
Location: Oslo, Norway

Re: Collision Detection

Post by rude » Sun Jul 20, 2008 10:41 pm

And with only 32 objects? I suppose there's no chance you'll post the full super-secret source? (So I can benchmark it myself).

You could implement some kind of spatial partitioning (grid, quadtree). That would keep you from having to check every object with every other, and it should speed up things considerably.

But still, an FPS like that with only 32 objects suggests that the collision detection algorithm itself is to blame. And it does look kind of slow. For instance, you create two tables for each iteration ... that can't be good.
Kudomiku wrote:Also rude, did you make Love? If so then good job, it's awesome.
  • What kind of shapes do you need?
  • What kind of collision response do you need?
  • Is there a lot of static geometry in your game? (I.e. terrain.)
  • Tell us more! :3
Kudomiku wrote:Also rude, did you make Love? If so then good job, it's awesome.
<obvious-pun>Yes, I make LÖVE with mike.</obvious-pun>

User avatar
Kuromeku
Party member
Posts: 166
Joined: Sun Jul 20, 2008 5:45 pm

Re: Collision Detection

Post by Kuromeku » Sun Jul 20, 2008 11:02 pm

Hello this is the source.

http://kudomiku.com/storage/hate.rar

I don't know how to make it a .love yet, like I said, I haven't been using Love for long.

And as for the other collision methods you talked about, I don't really know because I've never done collision before. This is my first time.

When the game loads, you'll see some falling prop_physics, you can grab them by clicking on them.

P.S: I managed to speed it up by checking if the entity is POSSIBLE to collide with it (checking if it's within possible distance). That manages 32 entities fine, but my goal now is 128 entities (which it currently can't handle), could you help? Anyway, take a look at my source and see how things are.

I plan to make it like a 'gamemode' sandbox. So I can make little fun Lua gamemodes like top-down shooters, side-scrollers, or whatever with ease.

Thanks for your help.

User avatar
rude
Administrator
Posts: 1051
Joined: Mon Feb 04, 2008 3:58 pm
Location: Oslo, Norway

Re: Collision Detection

Post by rude » Mon Jul 21, 2008 11:31 am

Kudomiku wrote:I don't know how to make it a .love yet, like I said, I haven't been using Love for long.
It's just a renamed .zip file.

If you can make do with circles, that should be fast enough for you. Check out the attatched demo. With 128 objects, it's stable around 110 FPS on my laptop.

I would help you out more, but this is what I have time for right now. ^^
Attachments
collision.love
(1.31 KiB) Downloaded 222 times
colldet.png
colldet.png (45.92 KiB) Viewed 3809 times

Post Reply

Who is online

Users browsing this forum: No registered users and 27 guests