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).

Graph of algorithm A1's runtime

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.

Graph of algorithm A2's runtime

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

Post a Comment

Your email will not be published. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>
LaTeX is also allowed inside \( \) or $$ $$ tags.