How to do (or code) so that an array of Bullet objects can meet with an array of Zombie objects?

Question

I just started learning game development using Java.

I have created

1. ArrayList of class Zombie
2. ArrayList of class Bullet

Each of the object in the two ArrayList has a variable called rect of type Rectangle which surrounds their own graphics on screen.

My aim is to make an effect when any bullet meets any zombie.

My problem is I don't know how to do "any bullet meets any zombie."

My method: I used the rect variable to test whether both of the object have collided with each other by using the method rect.intersect(r). I'm testing every single bullet in the Bullet ArrayList to see if it has collided with any zombie in the Zombie ArrayList, which means I run through the two ArrayList completely per frame just to carry this feature out. There must be better ways..??

Answer 1

In general, what you do is the basic idea. You check every object from one array against the objects in the other array. If the number of objects is not insanely big this is fine.

But... You can optimise this in several ways to reduce the number of checks by predicting if two objects need a collision check.

Often collision detections are split in a 'broad' phase and a 'narrow' phase. The broad phase is used to eliminate objects that are unlikely to collide, the narrow phase does the actual collision check.

A broad phase method often used is Quadtrees. A quadtree is basically a way to order object by the location. Bullets and Zombies that are close to each other end up in the same 'quad space' and you only need to check bullets and Zombies that are in the same space.

There can be other ways of optimizing collision detections- you could only check bullets against zombies that are in the direction of the bullet. Or only check objects that have moved since the previous frame etc.

However you need to consider if the simple rectangle intersect is more costly than sorting your objects.

Answer 2

I don't have enough reputation to comment on Felsir's answer, but here's a good tutorial that explains what quadtrees are and how to implement one for collision checking in Java.