Collision detection

[Kommi]

If I have ten boxes moving around and I wish to do collision detection what is the best way to organize it? Should I take the first box and check it against the coords of the other nine, then take the second and check it agaginst the remaining 8, ...? I am asking becasue the boxes will be bounding boxes for characters in a game.

[jbanes]

Heh. I'll probably get accused of pimping my stuff, but GAGE has a collision algorithm that might interest you. The concept is to place boxes into different groups that can collide with one another. (i.e. Good Guys, Bad Guys, friendly fire, enemy missiles, etc.) For each of these groups, you can define a collision handler. The groups will be checked against one another and the collision handler called if any collisions occur.

The advantages to this approach are that the reciprocal checks that normally occur (object a checks object b, object b checks object a) are eliminated. Even better, only object that can interact with a specific group of characters are checked, thus eliminating things like "friendly missile collides with friendly missile" checks.

[Kommi]

I am intereste in your GAGE software but was wondering if you could answer my quesion about which collision detection approach to use. Do you have object a checks b checks c..., and then object b checks c, checks d...? Or is there some other better way?
Also is your collision detection bounding box or at the pixel level?

Games published by our own members! Check 'em out!

[jbanes]

My collision is at the bounding box level. Reread my previous post for how the algorithm works. Also, try looking at the JavaDocs for GAGE. It might help you understand it better.

[Jacko]

To get the best results you will want both bounding boxes and pixel methods.

Heres a quick round up of how I do this....

Sort your list of sprites by y position
take the first sprite
is the next sprite on the list closer then the current sprites height?
If it isnt then there is no collision, AND this sprite cant be colliding with any other sprites, so move onto the next one.

If it is you could have a collision so do a bounding box test
If the bounding box reports a collision you then move to the pixel level.
If it collides here then you have a perfectly detected collision, so you need to send a message to both sprites involved saying they have collided.

If the bounding box test doesnt report a collision, then test against the next sprite in the list, until the y position of the next sprite is greater than the sprite you are testing against.

Hope this helps.

[Abuse]

Sort your list of sprites by y position

Sort your list of sprites by whichever dimension makes more sense

in a side scrolling shooter, you'd want to sort by the x value, not y

[Ghardoan]

The techniques presented by the above posters are great and functional, but I thought I would toss out the option of partitioning the screen as well.

Essentially, the technique involves using linked lists to represent certain quadrants of the screen, such as halves, quarters, vertical slices, whatever. Each linked list contains the handles to the elements residing within that quadrant, making it possible to only check for collisions with elements in the same quadrant. This is much more efficient than the cycle-eating process of checking to see if every element collided with any of the other elements on screen.

Then again, for ten elements, processor cycles should be no problem. Just check each box against the other nine, and spare yourself the time and trouble of developing a quad tree or some other form of screen partitioning.

Sorry if this post seems a bit scattered; I just woke up, and I have a headache.


Cheers,

Ghardoan

[Abuse]

yeah, a quad tree is the proper way to do it - but it IS a lot of hassle, and only becomes beneficial (from a performance perspective) with reasonably big numbers of objects present in the universe.

[Kommi]

Will using linked lists to sort 20 or so sprites sixty times a second (60fps) cause conciderable slowdown? Should I tune the fps down or ecrease the number of sprites on the screen?  

[Jacko]

As usual, it all depends. Is it giving you poor performance now? If it is then look at the algorithms you are using. You should be able to get a lot more than 20 sprites running at 60 fps even with collision. First thought when I read your post is to change your sort method. A bubble sort is not what you want.

Games published by our own members! Check 'em out!

[jbanes]

Just to add here, when I did the collision detection for GAGE, it was my intention to use sorted lists to speed up the detection. The thing was, once I completed the basic detection, I found that it ran so fast that I had no need to use a sorted list. The lesson? Profile your app! You may be wasting your time optimizing things that don't matter!

[Kommi]

I havent implemented it yet, just general speculation. I dont think that I will have a performance issue since curently my engine can support thousands of sprites flying around and a scrolling background and evrything. I was wonering if bubble sort is not the bst way then what should I use? Mergesot, Quicksort, Selection Sort, ...?

[Abuse]

Actually.... bubble sort may be the best option  

because the positions of sprites (and hence their order) only changes a small amount each frame, the re-sorting needed between each frame will likely be very small - The ideal scenario for a bubble sort.

Alternatively, you may try to maintain the sorted status of the list at all times, and use insertion sorting - though, that maybe counter prodcutive, and complicate the code loads.

[Kommi]

Good point. I think insert sort would do the trick since what I am writting is an iso perspective rpg. The collision is between charcters and a character with a table or edge of a building. I guess buble sort or insertion sort should work fine, Ill se what happens when I implement it. Thanx