Kommi
Junior Devvie  
All opinions will be lined up and shot!
|
 |
«
Posted
2003-05-20 00:51:02 » |
|
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.
|
Kommi
|
|
|
jbanes
|
 |
«
Reply #1 - Posted
2003-05-20 02:22:11 » |
|
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
Junior Devvie  
All opinions will be lined up and shot!
|
 |
«
Reply #2 - Posted
2003-05-20 02:40:29 » |
|
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?
|
Kommi
|
|
|
Games published by our own members! Check 'em out!
|
|
jbanes
|
 |
«
Reply #3 - Posted
2003-05-20 12:40:20 » |
|
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
|
 |
«
Reply #4 - Posted
2003-05-20 14:08:59 » |
|
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
|
 |
«
Reply #5 - Posted
2003-05-20 14:52:39 » |
|
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
Junior Newbie
Proud father of Bobbin.
|
 |
«
Reply #6 - Posted
2003-05-20 19:50:48 » |
|
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
|
 |
«
Reply #7 - Posted
2003-05-20 21:17:47 » |
|
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
Junior Devvie  
All opinions will be lined up and shot!
|
 |
«
Reply #8 - Posted
2003-05-21 14:04:51 » |
|
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?
|
Kommi
|
|
|
Jacko
|
 |
«
Reply #9 - Posted
2003-05-21 14:36:45 » |
|
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
|
 |
«
Reply #10 - Posted
2003-05-21 15:09:34 » |
|
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
Junior Devvie  
All opinions will be lined up and shot!
|
 |
«
Reply #11 - Posted
2003-05-21 17:20:21 » |
|
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, ...?
|
Kommi
|
|
|
Abuse
|
 |
«
Reply #12 - Posted
2003-05-21 21:15:42 » |
|
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
Junior Devvie  
All opinions will be lined up and shot!
|
 |
«
Reply #13 - Posted
2003-05-21 21:48:47 » |
|
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
|
Kommi
|
|
|
|