# Hit Detection Experiments

I decided I wanted to write an environment hit detection system the other day. My intention was to make a collidable image, by which I mean particles/circles could collide with arbitrary shapes based on the pixels of the image. Decided I could check if a line formed by the last position of the particle and the new position intersects any pixels in my image. To do this I started of trying to do something similar to a binary search since I was assuming that when it collided, the image would most often intersect near the center of my motion line. Here's what I came up with:

Algorithm A1:1 2 3 4 5 6 7 8 9 10 11 12 //maxTries is set to p1.distanceTo(p2)/2 at first public boolean hitTest(Point2D p1, Point2D p2, int maxTries) { Point2D mid = getMidpoint(p1, p2);   if (map.getRGB((int) mid.getX(), (int) mid.getY()) == 0xFF000000) { return true; } else if (maxTries < 0) { return false; } else { return hitTest(p1, mid, maxTries - 1) || hitTest(mid, p2, maxTries - 1); } }

It works but after some analysis I realized it was very slow. In an attempt to determine exactly how slow, I determined that if there's no collision it runs $\sum\limits_{n=0}^{N} 2^{n+1}$ times where $N$ is the length of the line. Simplifying, I get $2(2^{n+1} - 1)$ so it's complexity is $O(2^N)$. Exponential time, not great. I also graphed the performance to see if it mattered for the line lengths I would be using (remember, it runs in exponential time and this graph is on a logarithmic scale).

While I was doing these checks I thought of a better way to do it. I would use the Bresenham Line algorithm to find the points I should check on the image. There were almost no modifications to the algorithm necessary just that instead of setting a pixel, I check the color of my collision image and return true if it's black.

Algorithm A2 (basically just the Bresenham Line algorithm):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 public boolean hitTest(Point2D p1, Point2D p2) { double dx = Math.abs(p2.getX() - p1.getX()); double dy = Math.abs(p2.getY() - p1.getY()); double x = p1.getX(); double y = p1.getY();   int sx1,sx2,sy1,sy2; if (p1.getX() < p2.getX()) { sx1 = sx2 = 1; } else { sx1 = sx2 = -1; } if (p1.getY() < p2.getY()) { sy1 = sy2 = 1; } else { sy1 = sy2 = -1; }   double den, num, numadd, numpixels; if(dy < dx){ sx1 = 0; sy2 = 0;   den = dx; num = dx/2.0; numadd = dy; numpixels = dx; }else{ sx2 = 0; sy1 = 0;   den = dy; num = dy/2.0; numadd = dx; numpixels = dy; }   for(int i = 0; i <= numpixels; i++){ if(map.getRGB((int)x, (int)y) == 0xff000000){ return true; }   num += numadd; if(den < num){ num -= den; x += sx1; y += sy1; }   x += sx2; y += sy2; }   return false; }

I also graphed this one's performance, obviously it's much better since Bresenham's Line algorithm is $O(N)$. Also his $N$ is smaller than my $N$ because his is the length of the longest component (x or y) of the line while mine is the length of the line. This one didn't need to be on a logarithmic scale.

Obviously it's much faster but it's not actually accurate enough; sometimes particles can still pass through my image and sometimes they will stick to the edge when they're supposed to be bouncing off. I might end up using a collider that checks with the intersection method of java's GeneralPath class. I also thinking it could be fast doing a somewhat more accurate check after the initial check with my current algorithm to be certain whether I've hit or not. There's more testing preform.

Categories: Articles | Tags: , , | Comments RSS | Trackback URL