Hi I''m having a bit of trouble doing some collision detection for a Java based game... it''s a shoot''em up, but the question should also be applied to beat''em ups and other games that require an accurate collision detection. On my previous Java game I used a pixel precision collision detection. I placed the ship into an array, filling the spaces occupied by the ship with 1''s and the others with 0''s. Then I overlapped this array with the "scenario" and detected all the collisions. This worked really great but it has a dramatic downside... filling in the spaces is really boring and it involves a lot of time lost without being programming. Note: you can see a little bit of info about this title at http://student.dei.uc.pt/~pamaro/caverna.htm On my Pascal programming days, I used a similar method but, instead of filling the array "manually", I drawed the picture on screen and used a pixel grabber (get_pixel(int x, int y)) to fill in the array. Is there a similar routine that can be done in Java? Apart from this technique... which other can you recommend me? I thought about doing it with a rectangle, without caring about the details on the ship, but the loss in accuracy makes it almost useless in shoot''em ups and beat''em ups (except if we want to detect the collision between a small object and a big object). I also thought about mixing these two methods... filling the array from the first one with generic forms... but this would just add the problems from both... any other ideas? Thanks in advance Pedro Amaro

I had the same problem in my shoot em up, and I solved it like so:

When I loaded an image that will appear on the screen, I also stored a bit-map of each pixel in memory; ie, if it was transparent, I stored a 0, else I stored a 1 (1 bit per pixel). Then, to map the bit-map to the image, I used a hash table with the address of the image, and the address to the bit-map.

In my collision detection algorithm, I get the two images'' bit-maps I''m comparing, and I align them, and check if there is any place where they are both 1, and, thus a collision.

In Java, If you can read each pixel from the image, you should be able to do something like this.

Hope that helps.

Nutts

I did much the same thing, well probably exactly the same thing. I used all four of John Amato''s collision algos. I rewrote them for the bitmask.

You can learn them here:

http://www.gamedev.net/reference/articles/article735.asp

They are in C++, but by using the basic concepts, you should be able to make them work under JAVA.

Guy

Actually, that''s one of the methods I mentioned in the initial post . I used to do it in Pascal... loaded the bitmap (with a color set as transparent) and used an "int get_pixel(int x, int y)" to fill in the array. I''m looking for a suitable alternative to that... or at least info on how to do one in Java .

The only problem I see with that one is that it can get a bit CPU intensive if there are lots of objects on the screen... are there better techniques? I wouldn''t mind losing a bit of accuracy to gain in performance in programming simplicity... but loosing too much accuracy isn''t acceptable (which is why I don''t use the polygon-based method I also mentioned above). But I''m out of ideas... isn''t there something between these two methods? Something that adds the precision of one and the performance of the other and makes one damn good 2D collision detection routine? So far, I''ve only come up with ideas that add the lack of performance of one with the lack of precision of the other... any ideas?

Pedro Amaro

John Amato''s algos do have a quick reject using bounding squares. That avoids unnecessary pixel detection. I guess you could use relative vectors as well to limit collision detection.

I tested the detection using 10 balls for which I bounced around the screen. They also had to bounce off of each other. I believe that was 45 actual possible collisions. I did''nt test frame rate, but they did move rather smoothly. At the moment, I can''t think of a better method. How many objects are you concerned about ?

Guy

Hmmm... the amount of objects would be bigger than 10... and with different sizes.

Assuming I''d want to add "infinite" elements, I''ll use linked lists. Although there can''t be infinite elements on screen, for a standards 640*480 resolution we can have... 15 to 20 ships at the same time (variable sized).

The collision detection routine should also work with the shots... assuming a double-firing ship in the worst case scenario (located at the bottom of the screen firing), we can have around 40 to 60 ammo rounds. Of course, enemy ships would also be firing... I guess that we can easily have 200 objects on screen requiring collision detection (maybe more... but I''m assuming a rather simplistic shoot''em up). This is why I''m concerned about speed... in my latest game I did few collision tests per frame (to use a measure)... that game wasn''t a true shoot''em up, though... for a real 2D scrolling shooter (in the style of Tyrian, Raptor or Musha Aleste), the amount of objects to be detected is closer to the 200 I mentioned earlier.

Adding to that scenario collisions (to make scenario elements destructable), that number increases even more... but scenario elements are big enough when compared to the rounds to make a less-accurate approach... however... when it comes to the ships, perfect detection is a must... but we''re talking about a massive amount of objects on screen...

Hmmm... should I mix both types of collision? If yes, is the performance increase good enough to compensate for the loss of accuracy? I don''t want to make the ultimate shoot''em up, but I also don''t want to program something so slow that is unplayable or with a collision detection so unprecise that makes the player give up playing...

Right now, unless someone can point me to a new algorythm, I''m thinking about doing the division as follows:

* ship to ship collision: reduced bounding-box collision detector

* laser to ship collision: pixel-level collision detector

* laser to scenario collision: reduced bounding-box collision detector

Would this work well? Or is there another option? Notice that we have 200+ objects on screen...

Pedro Amaro

With 200 objects, that game sounds pretty cool.
That''s also alot of collision detection.

You have your ships on screen, and they can collide with each other. That''s fine. A bounding box check first, if that passes maybe add a pixel level check.

Do all you ships have all their volleys firing at once ? Maybe some are''nt active or on-screen. If so, only check the on-screen
active ones with the ships.

It also depends how fast your objects are moving on screen. Maybe you don''t have to do a collision detection every single frame. Maybe you can incorporate a collision timer that you could play with that would only check for collisions every so often instead of every frame. This might/might not work depending on your objects vectors. If they are moving a pixel at a time, maybe it''s worth trying.

I''m presently working on a space invader type thing which has 40 invaders at onset. I can fire up 10 volleys at them. That works out to 400 possible collisions. They also throw down 10 volleys which can collide with the ship. That''s ten more collisions. So far I''m up to 410 possible collisions. All these collsions are done sprite for sprite at the pixel level. So far I have not noticed any performance loss. Though such a scheme is easily optimized. If you are doing point within a sprite at pixel level, that''s pretty quick using bitmasks.

Maybe you should build on you collision detection. Start off with bounding box, if your happy, you can always add pixel level check to a bounding box check that rang true.

Guy

200 objects isn''t much... I mean, for an action-packed side-scrolling shoot''em up . My last game was also a sidescroller and it involved little collision detection, so I used the pixel-based routine (you can get the game at http://student.dei.uc.pt/~pamaro/caverna.zip if you''re bored enough to play with it... the graphics, sound and music aren''t original, though... only the programming is... I''m not an artist ).

Hmmm... to do the minimum possible collision detection tests, I''ll be placing the shots in one linked list and the ships on screen in another. Therefore, we only need to go through the linked list and see if the current element is clashing with anything (comparing the shots with the ships, etc). Still, this causes a huge amount of possible collisions... each shot can be colliding with a ship or a scenario element, each ship can be colliding with each other... I still need to decide if I''ll be placing crashes between the ship and scenario elements, but if I do it''ll be another one... plenty of collisions on screen, as you can notice...

Your idea sounds really good... my only fear is that, in the worst case scenario, it''ll make the collision detection even slower (first we do a bounding, then we have to do a pixel-level). Nevertheless, I might try that out and see how it works.

As for frame skipping, I''m not sure if that''ll work well... there''s always a small possibility that something hitted something during the frame(s) we were skipping... although this may not be noticed when it comes to ship-to-ship collision, it might occur in shot-to-ship collisions...

Pedro Amaro

pamaro,

I''ve created a side-scroller exactly like you''re talking about (writen in C/C++ tho), and I do bounding-box checking 1st, then checking with my pre-defined bit-masks, and there really is no noticeable slowdown at all. I even have a level where the ship flies though a tunnel that moves up and down, but it''s actually just a long bitmap, so, the ship is always within the bounding box, so, every frame, it must check if the ship is colliding with the tunnel (ie, non-transparent part of the bitmap), along with the enemies and bullets, there still is no slowdown.

Besides, that, keep lists of all the objects on the screen, backgrounds, and bullets on the screen, and check the collision for each. If you would like, i could send you the part of the source code for the collision (including pre-defining the bit-masks, checking each list of objects and the collision routine itself).

Nutts

I''m doing mine in Java... which is why I''m so concerned about speed and performance. Despite being a powerful language, it''s a bit slower than most other languages due to its nature... I know I could compile it in native code, but that would "defeat" the purpose of doing it in Java and assure multi-system compatibility.

I''m also planning on adding two or three paralax scrolling plans... my last game only used two (I tried it with three and it became too slow), but I''m trying to optimize its programming... but for that I need a really efficient routine.

The idea you and Guy mentioned seems to be good... doing first a bound checking and, only if it turns true, a pixel-level. Hmmm... but what about if we added an 80% bounding box in between? Would it become too much of a overhead or the situations in it might prevent a pixel level would compensate for this? Or if, instead of 80%, I did an average of the ship''s size...?

Pedro Amaro