Tracing Point A to Point B, detecting rectangular obstacles in 2D

General Discussions
#1

Hey there!

I’ve run into a rather simple still puzzling problem in my game. In my tilebased game, I need the enemies to look for the player’s units at intervals, to seek targets.
I currently do this by (per player-controlled unit) dividing the distance between the enemy and the unit into a list of points, and checking if any of the points are occupied by f.ex a wall. If so, the trace returns false (sight impared), otherwise true (clear view).

http://81.216.242.88/misc/method1.png

My second idea is to calculate the angle of the “line” between enemy and unit, then for each object that is an obstacle, calculate the angles of each corner against the enemy coordinate.
If all of the corner’s angles are less, or more than, the angle of the “line”, the obstacle is outside the line of sight, if they differ… the obstacle is in the line of sight.

http://81.216.242.88/misc/method2.png

Problem is if angles are calculated to be negative and are wrapped positive, angles which would differ are suddenly on the same “side” of the line.

The second approach appear significantly faster, but if I can’t fix my problem it’s not much use. Help would be much appreciated.
Posting source to help explain my algoritm;


    public boolean trace(Coord coord1, Coord coord2) {
        double angle = CommonMath.angle(coord1.x, coord1.y, coord2.x, coord2.y);
        double distance = CommonMath.distance(coord1, coord2);
        
        List<Thing> list = main.getThingHandler().getList();
        
        Coord coord3;
        for (Thing thing : list) {
            if (thing.isObstacle()) {
                coord3 = thing.getCoord();
                
                if (CommonMath.distance(coord1, coord3) > distance) continue;
                
                /*
                 * Retrieve angles for each of the obstacles corners
                 */
                double angle1 = CommonMath.angle(coord1.x, coord1.y, coord3.x - 0.5, coord3.y - 0.5);
                double angle2 = CommonMath.angle(coord1.x, coord1.y, coord3.x + 0.5, coord3.y - 0.5);
                double angle3 = CommonMath.angle(coord1.x, coord1.y, coord3.x - 0.5, coord3.y + 0.5);
                double angle4 = CommonMath.angle(coord1.x, coord1.y, coord3.x + 0.5, coord3.y + 0.5);
                
                /*
                 * Which side of the line of sight are we on?
                 */
                boolean rel1 = angle1 < angle;
                boolean rel2 = angle2 < angle;
                boolean rel3 = angle3 < angle;
                boolean rel4 = angle4 < angle;

                /* 
                 * Are all of the corners on the same side of the line of sight?
                 */
                if ((rel1 != rel2) || (rel2 != rel3) || (rel3 != rel4)) {
                    return false;
                }
            }
        }
        
        return true;
    }
#2

I see this +/- 0.5 with the coordinates.

The tiles are all numbered by integer (x, y) coordinates, right? Shouldn’t you really be looking at (x, y), (x + 1, y), and (x, y + 1) when you’re getting these angles?

When you’re talking about the “angle” of the line, do you mean the angle above the horizontal-axis? It might be helpful if you provided code for CommonMath.angle.

I guess you’re “line of sight” is really more like a “circle of sight” because they can see in all directions, right? I don’t think it makes any difference either way for the purposes of your problem, but any tidbit of information may be useful.

#3

The first idea isnt that bad, but I would use Bresenham’s line algorithm or a variation of that. Optimally you would start tracing that line from the origin towards the target(s). This allows you to break out of the loop as soon as you hit a wall.

This should work pretty well and quickly. (Well, its not perfect, but most players wont notice that anyways.)

#4

I agree with onyx. As logna s you have a regular grid you shoudl make use of it. A simple grid walk will tell you if there is a wall between the center of the looker and the cenetr of the object looked at, which is close enough I suspect.

#5

Thanks everybody!

Turns out the reason the second idea was faster was that the first implementation was slow. No obstacles are currently moving in my game so I could safely cache the obstacles in a boolean array and look them up. I’ll compare it with to the Bresenham’s line algorithm, it looks very efficient.

You are absolutely correct that their sight is really a circle of sight, though they look at each player unit with a single line of sight.
My coordinate class is a Point2D.Double decendant to allow other than on-tile placements. Basically X.0 (1.0, 2.0, 3.0…) values are in the center of a tile, +/-0.5 is between two tiles.


    public static double angle(double x1, double y1, double x2, double y2) {
        double dx = x2 - x1;
        double dy = y2 - y1;
        
        return Math.atan2(dy, dx);
    }

However, since the first / Bresenhams sollution has end up the faster one, I’m mostly posting to fill your much appreciated curiosity! :slight_smile:

#6

Did you consider the Line2D.intersects(Rectangle2D r) and Line2D.intersectsLine methods? These are quite fast as they don’t use any trig methods.

#7

That’s a really good idea!
I haven’t even thought of them, I guess I thought they were slow since they are so… well, exact.
I’ll do a test and see, it’d be simple to implement and also work with non-tilebased sensing.

Edit;

Primary testing shows that the figure 1 method, with a detail level of distance * 2 is two times faster than the Line2D.intersects method. However, both methods show up as 0 msecs in my game so I compare the nanosecond result.
Intersection requires a fraction of the code, it’s clean, and native. Why didn’t I think of this myself?

Thank you very much, this is the slickest sollution by far!

#8

Line2D.intersects is going to be somewhat slower, although for a small bunch of tiles you probably won’t notice a difference. However it won’t scale nearly as well with bigger levels - it’ll be O(n) rather than O(1).

#9

This is very true, scaling things up a bit, step-tracing remains at 0-2 ms while intersecting Rect2D’s at 40 ms.

So looks like I’ll use step-tracing for dirty tracing, and rects if I need some pretty tracing. Thanks everybody :slight_smile: