In building a program to simulate a zombie invasion, collision detection presented an interesting problem when working with large numbers of humans and zombies, represented by black and green dots respectively.
Detecting collisions between two dots is straightforward, but large numbers of dots become challenging. Using brute force to detect collisions of dots in a plane is \(O(n^2)\), so something more efficient is necessary.
If the dots were discrete, then a HashMap would be a natural choice, so the solution involves translating the plane into discrete components. By dividing the plane into squares sized similar to the dots, a collection can be associated with each square containing every dot contained by that square. Since dots in this situation cannot overlap there can be at most 4 dots partially covered by any one square. This constrains the number of collisions to consider down to a constant number, so all of the collisions can be identified in \(O(n)\) time.
The dots have two responsibilities: testing for overlap with another dot and producing which squares it covers.
public class Dot {
private Point center;
private int radius;
public Dot(Point center, int radius) {
this.center = center;
this.radius = radius;
}
public Point get_center() {
return center;
}
public int get_radius() {
return radius;
}Two dots overlap if the distance between centers does not exceed the sum of the two radii.
public boolean overlaps(Dot other_dot) {
return center.distance(other_dot.get_center()) < radius + other_dot.get_radius();
}Instead of building a separate object for squares, they are represented by a point describing the top left corner. Calculating these corners is a little more involved, marking a point every 10 units and truncating to the nearest tens place.
public HashSet square_corners_covering() {
HashSet corners = new HashSet();
Point top_left_corner = calculate_containing_square_corner(new Point(center.x - radius, center.y - radius));
for (int x = top_left_corner.x;x <= center.x + radius;x += 10) {
for (int y = top_left_corner.y;y <= center.y + radius;y += 10) {
corners.add(square_corner_containing(new Point(x, y)));
}
}
return corners;
}
private Point calculate_containing_square_corner(Point point) {
return new Point(point.x - Math.abs(point.x % 10), point.y - Math.abs(point.y % 10));
}
private Point square_corner_containing(Point p) {
Point square_corner = new Point(p.x, p.y);
if (p.x < 0 && p.x % 10 != 0) square_corner.x -= 10;
if (p.y < 0 && p.y % 10 != 0) square_corner.y -= 10;
square_corner.x += Math.abs(square_corner.x % 10);
square_corner.y += Math.abs(square_corner.y % 10);
return square_corner;
}
} With the dot class in place, the class that actually identifies collisions can be built.
public class DotCollider implements Iterable {
private HashSet dots;
private HashMap> grid;
public DotCollider() {
dots = new HashSet();
grid = new HashMap>();
}
@Override
public Iterator iterator() {
return dots.iterator();
} Looking the collections associated with each square up in the grid, adding empty ones if they don't exist.
public HashSet dots_within(Dot dot) {
HashSet all_dots = new HashSet();
for (HashSet dots_within_square : covered_squares(dot))
for (Dot overlap_candidate : dots_within_square)
if (dot.overlaps(overlap_candidate))
all_dots.add(overlap_candidate);
return all_dots;
}
private ArrayList> covered_squares(Dot dot) {
ArrayList> result = new ArrayList>();
for (Point corner : dot.square_corners_covering()) {
ensure_corner_exists(result, corner);
result.add(grid.get(corner));
}
return result;
}
private void ensure_corner_exists(ArrayList> result, Point corner) {
if (!grid.containsKey(corner)) grid.put(corner, new HashSet());
} Adding the provided dot to the master record of all dots and every covered square.
public void add(Dot dot) {
dots.add(dot);
for (HashSet covered_square : covered_squares(dot))
covered_square.add(dot);
} To determine which dots have collided, just those dots within covered squares need be considered.
public Collection get_collisions(Dot d) {
ArrayList collisions = new ArrayList();
for (Dot collided : dots_within(d)) {
if (d != collided)
collisions.add(collided);
}
return collisions;
}
}