Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (753)
Games in Android Showcase (228)
games submitted by our members
Games in WIP (842)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Collision detection  (Read 5065 times)
0 Members and 1 Guest are viewing this topic.
Offline 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
Offline jbanes

JGO Coder


Projects: 1


"Java Games? Incredible! Mr. Incredible, that is!"


« 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.

Java Game Console Project
Last Journal Entry: 12/17/04
Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline jbanes

JGO Coder


Projects: 1


"Java Games? Incredible! Mr. Incredible, that is!"


« 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.

Java Game Console Project
Last Journal Entry: 12/17/04
Offline Jacko

Junior Devvie





« 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.
Offline Abuse

JGO Ninja


Medals: 64


falling into the abyss of reality


« Reply #5 - Posted 2003-05-20 14:52:39 »

Quote

Sort your list of sprites by y position


Sort your list of sprites by whichever dimension makes more sense Cheesy

in a side scrolling shooter, you'd want to sort by the x value, not y Roll Eyes
Offline 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
Offline Abuse

JGO Ninja


Medals: 64


falling into the abyss of reality


« 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.
Offline 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
Offline Jacko

Junior Devvie





« 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!
Legends of Yore - The Casual Retro Roguelike
Offline jbanes

JGO Coder


Projects: 1


"Java Games? Incredible! Mr. Incredible, that is!"


« 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!

Java Game Console Project
Last Journal Entry: 12/17/04
Offline 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
Offline Abuse

JGO Ninja


Medals: 64


falling into the abyss of reality


« Reply #12 - Posted 2003-05-21 21:15:42 »

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

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.
Offline 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
Pages: [1]
  ignore  |  Print  
 
 

 
nelsongames (12 views)
2018-04-24 18:15:36

nelsongames (10 views)
2018-04-24 18:14:32

ivj94 (586 views)
2018-03-24 14:47:39

ivj94 (49 views)
2018-03-24 14:46:31

ivj94 (383 views)
2018-03-24 14:43:53

Solater (63 views)
2018-03-17 05:04:08

nelsongames (110 views)
2018-03-05 17:56:34

Gornova (159 views)
2018-03-02 22:15:33

buddyBro (705 views)
2018-02-28 16:59:18

buddyBro (93 views)
2018-02-28 16:45:17
Java Gaming Resources
by philfrei
2017-12-05 19:38:37

Java Gaming Resources
by philfrei
2017-12-05 19:37:39

Java Gaming Resources
by philfrei
2017-12-05 19:36:10

Java Gaming Resources
by philfrei
2017-12-05 19:33:10

List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!