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.