Archived

This topic is now archived and is closed to further replies.

[java] effecient collision detection algo

This topic is 5126 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hmm... for my game(Space invaders clone), pretty much all I need of it so far is a collision detection algorithm.. I read articles on here and they''re mostly C ones using enemies as linked lists.. Now I''m just wondering if this method would be plausable in java.. first off I''d make a 3 dimentional array, with the X and Y size of the array being the size of the level divided by the largest object in my game, where the Z would be the number of objects allowed. X and Y of the array will (obviously) be an area to test for collisions, and the Z will contain the number of the enemy array the enemy will be, or a shot(and it''s ID). The tests would then be testing the area the player is in for enemies or enemy shots, then test the area the players shots are in for enemies. Is this plausable for java or should changes be made to it? In the end I want to make this a large scale trippy clone with hundreds of enemies at once..

Share this post


Link to post
Share on other sites
Somone can correct me if I am wrong(and I usually am), but this seems like too much work for an efficient collision detection system.

They way I do it isn''t the best I am sure but a bit easier than that, just make sure all of your enemies carry a flag that tells their state, either IsAlive or IsAwake or something like that.

Then as the enemies appear on-screen switch the flags to TRUE. Now you can just loop through your list, array or vector and only test the enemies or shots that are alive.

The major draw back is that your collision detection will have through run the the entire collection you have, BUT you will only have to make one Boolean test to see if you need to perform a collision detection test.

I hope this answers your question. Also if you are looking for ColDet algorithms lets us know there are some good ones floating out here on game dev.

Good Luck


"And then 2 men appeared... Men in dark suits.. with dark soulless eyes. Men like this could have come from only one place..
The bank."

Share this post


Link to post
Share on other sites
You shoot and it goes somewhere. So your problem could be.

Should I do: 1. count real point of interaction?
2. Should I count if frame by frame?

Answer depends on structure of your code.

Share this post


Link to post
Share on other sites
quote:
Original post by Wrathnut
Somone can correct me if I am wrong(and I usually am), but this seems like too much work for an efficient collision detection system.

They way I do it isn''t the best I am sure but a bit easier than that, just make sure all of your enemies carry a flag that tells their state, either IsAlive or IsAwake or something like that.

Then as the enemies appear on-screen switch the flags to TRUE. Now you can just loop through your list, array or vector and only test the enemies or shots that are alive.

The major draw back is that your collision detection will have through run the the entire collection you have, BUT you will only have to make one Boolean test to see if you need to perform a collision detection test.

I hope this answers your question. Also if you are looking for ColDet algorithms lets us know there are some good ones floating out here on game dev.

Good Luck


"And then 2 men appeared... Men in dark suits.. with dark soulless eyes. Men like this could have come from only one place..
The bank."



For more speed, you could have a linked list with only the alive objects in it. This way you are only checking anything that is alive. If you want a finite list of objects, then you could have 2 lists, one for alive and one for dead.



First make it work,
then make it fast.

--Brian Kernighan

The problems of this world cannot possibly be solved by skeptics or cynics whose horizons are limited by the obvious realities. We need men and women who can dream of things that never were. - John Fitzgerald Kennedy(35th US President)

Do not interrupt your enemy when he is making a mistake. - Napolean Bonaparte

Share this post


Link to post
Share on other sites
hmm I just have it so when the objects are there they exist, and when they die they get deleted.. And the thing about them being offscreen shouldn't be necessary seeing how there is no way the enemies to get offscreen..

[edited by - eedok on November 28, 2003 1:13:14 PM]

Share this post


Link to post
Share on other sites

0 1 2 3 4 5 6 7 8 9
|---|---|---|---|---|---|---|---|---|---|
| E | E | E | E | E | E | | | | | 0
|---|---|---|---|---|---|---|---|---|---|
| E | E | E | E | ^ | E | | | | | 1
|---|---|---|---|---|---|---|---|---|---|
| | | E | E | ^ | | | | | | 2
|---|---|---|---|---|---|---|---|---|---|
| | | | | ^ | | | | | | 3
|---|---|---|---|---|---|---|---|---|---|
| | | | | ^ | | | | | | 4
|---|---|---|---|---|---|---|---|---|---|
| | | | | ^ | | | | | | 5
|---|---|---|---|---|---|---|---|---|---|
| | | | | ^ | | | | | | 6
|---|---|---|---|---|---|---|---|---|---|
| | | | | P | | | | | | 7
|---|---|---|---|---|---|---|---|---|---|
E: enemy
^: bullet
P: player

Pseudocode:

loop {
if (LevelArray[bullet.pos]=''E'')
{
LevelArray[bullet.pos] = '' '' // killed
stopbullet();
}
else
advanceBullet();

MoveEnemies();
}

Share this post


Link to post
Share on other sites
Since you don''t have to worry about offscreen enemies, my next question is how many enemies will you have on screen at once?

Depending on how many enemies are on screen you might be doing more work with the algo you mentioned first then just looping though all of them and doing a simple col det.

Another question I have is what is you collision detection routine, the code for it I mean. I don''t want to seem liek I am prying but if we could find out those things we might be able to give you an answer that would be more helpful.



"And then 2 men appeared... Men in dark suits.. with dark soulless eyes. Men like this could have come from only one place..
The bank."

Share this post


Link to post
Share on other sites
quote:
Since you don''t have to worry about offscreen enemies, my next question is how many enemies will you have on screen at once?
I think at least like 25, all running their AI scripts and able to shoot 5 shots.

quote:
Depending on how many enemies are on screen you might be doing more work with the algo you mentioned first then just looping though all of them and doing a simple col det.
The simple detection starts bogging down once there''s 14 enemies onscreen(on this Celeron machine).

quote:
Another question I have is what is you collision detection routine, the code for it I mean. I don''t want to seem liek I am prying but if we could find out those things we might be able to give you an answer that would be more helpful.

I''ll just give you pseudocode of what I have now, but I want to change it to something like I have at the top if it''s feasable..

for(each shot fired){
for(everyenemy){
if(shot is in enemies bounding rectangle)
destroy enemy and shot
}
}

Share this post


Link to post
Share on other sites
Ok, before you change it to something like that which you have at the top try this first please.

This is your current code
quote:

for(each shot fired){
for(everyenemy){
if(shot is in enemies bounding rectangle)
destroy enemy and shot
}
}



It might be that your loop is just too big. I am assuming that there are going to be fewer player shots on the screen than there will be enemies, if not that should be the case. Say 5 shots is the max player shots allowed onscreen at once, or some arbitrary number.

So if we re-order the looping we should be able to dramatically reduce the length of the loop. Try this:

for(everyenemy){
for(each shot fired){
if(shot is in enemies bounding rectangle)
destroy enemy and shot
}
}

This way you won't have to loop through the enemy list repeatedly, but just one time, and just loop through the list of shots fired which at first at least will be smaller than the total enemies on screen.

Unfortuantely, unless your col det algorithm is way too complex I don't think you will gain too much speed. But you just might. Give this a shot, and let me konw if there is any difference. I just woke up so I am going to have to think about the other problem for a bit before I jump into that.

Cheers


"And then 2 men appeared... Men in dark suits.. with dark soulless eyes. Men like this could have come from only one place..
The bank."


edit due to lack of caffiene in brain pan

[edited by - wrathnut on December 2, 2003 10:24:04 AM]

Share this post


Link to post
Share on other sites
So you are basically saying that 20*5 is better than 5*20? For me, both is 100. I don''t see the difference or even the improvement that re-aranging the loops should give you.

Share this post


Link to post
Share on other sites