Line of sight

steveyg90 · July 1, 2016, 9:53am

Hi,

Implementing line of sight at the moment so mobs will only attack if can see you. I’m using the following code
to do a ray, where xo,x1 is the bad guy and x1,y1 will be the player, this look efficient enough, seems ok?


public static void RayCast(int x0, int y0, int x1, int y1)
        {
            int dx = Math.Abs(x1 - x0);
            int dy = Math.Abs(y1 - y0);

            int sx = x0 < x1 ? 1 : -1;
            int sy = y0 < y1 ? 1 : -1;
            int err = dx - dy;

            while (true)
            {
                if (x0 == x1 && y0 == y1)
                    break;

                int e2 = err * 2;
                if (e2 > -dx)
                {
                    err -= dy;
                    x0 += sx;
                }
                if (e2 < dx)
                {
                    err += dx;
                    y0 += sy;
                }
            }
        }

Am I right in thinking only need to cast the one ray as not aiming for pixel perfectness?..

KaiHH · July 1, 2016, 10:21am

How 'bout figuring whether there actually is a line of “sight” by checking whether the line is obstructed by scene geometry via doing line-segment vs. “object” intersection tests?
Currently, this method seems to just walk each integer coordiante of every pixel touched by the line-segment.

Pseudo-code:


for each scene object within (x0, y0)-(x1, y1) do:
  if (object intersects line-segment: (x0, y0)-(x1, y1)) then
    return line of sight does not exist
return line of sight exists

When your scene objects are simply axis-aligned rectangles (big pixels) then you can simply use/copy this method, which handles all possible intersection cases (including edge-on intersections) between a line-segment and an axis-aligned rectangle:

github.com

JOML-CI/JOML/blob/master/src/org/joml/Intersectionf.java#L3343


 * @param p0
 *              the line segment's first end point
 * @param p1
 *              the line segment's second end point
 * @param v0
 *              the position of the first vertex
 * @param v1
 *              the position of the second vertex
 * @param v2
 *              the position of the third vertex
 * @param epsilon
 *              a small epsilon when testing line segments that are almost parallel to the triangle
 * @return <code>true</code> if the given line segment intersects the triangle; <code>false</code> otherwise
 */
public static boolean testLineSegmentTriangle(Vector3fc p0, Vector3fc p1, Vector3fc v0, Vector3fc v1, Vector3fc v2, float epsilon) {
    return testLineSegmentTriangle(p0.x(), p0.y(), p0.z(), p1.x(), p1.y(), p1.z(), v0.x(), v0.y(), v0.z(), v1.x(), v1.y(), v1.z(), v2.x(), v2.y(), v2.z(), epsilon);
}

/**
 * Determine whether the line segment with the end points <code>(p0X, p0Y, p0Z)</code> and <code>(p1X, p1Y, p1Z)</code>
 * intersects the triangle consisting of the three vertices <code>(v0X, v0Y, v0Z)</code>, <code>(v1X, v1Y, v1Z)</code> and <code>(v2X, v2Y, v2Z)</code>,

steveyg90 · July 1, 2016, 10:26am

Sorry, didn’t make myself clear, the code is just a ray cast, of course would need to check for intersections within my game geometry (Array of 2d tiles in my case).

Many thanks for the link, appreciate it.

LiquidNitrogen · July 2, 2016, 1:40am

That algorithm is pretty efficient, I’ve used it for constructing tile based field of view for the player, checking every tile every frame with no problem. The only thing is you may want to do some kind of additional tests if the target is blocked, since it can often get snagged on corners which you should be able to see past. (Although that might be more of an issue when detecting visibility of wall tiles, more so than detecting objects within a room)

steveyg90 · July 3, 2016, 3:44pm

Yeah seems efficient and just checking for tiles in the way. Just using as want bad guys to chase if can see player. Take it only one ray needs to be cast?