Line-Of-Sight - An (Inital) Solution

[dulux-oz]

Part 1
Introduction
This thread has been created for the expressed purpose of discussing and developing a Line-Of-Sight (LOS) system for use within our games. It has come about from a discussion in August 2013 around the creation of Custom Pointers and some further thoughts and correspondence since then. The original discussion can be found in Posts #16-19 of this thread (https://www.fantasygrounds.com/forums/showthread.php?19253-Custom-Pointers-Coding-Toolkit-Over-Several-Posts).

At the time of creation of this thread (Feb 29, 2016) the solution present here is only an "Initial Solution" in that, while the method (algorithm) and resulting function(s) will determine if LOS exists between two Tokens on an Image, it does so ONLY for the most primitive case: that of an Attacker and a Target, but without the possibility of any walls or other objects that the Target might "hide behind" - see the Further Remarks section.

Finally, all quotes have been edited for clarity.

Background
Back in August 2013 I developed a Custom Pointer Toolkit (available here (https://www.fantasygrounds.com/forums/showthread.php?19253-Custom-Pointers-Coding-Toolkit-Over-Several-Posts)) which simplified the creation of non-standard Pointers for use within our games. A Pointer is the Line, Circle, Square and Cone shapes that we draw on Images to indicate various things. At the time Zeus asked the following:

just to clarify something. If we know the start/stop point of a pointer as well as its area coverage, it should be possible to track the image area covered by a pointer (mapped to x,y points in an image control). If this is the case then I believe this would be all that would be necessary to initiate a basic mechanism for determining Line of Sight to any targeted token (also on the same image).

I am thinking it maybe possible to attach an invisible 25-45 degree wide cone to all tokens, facing out from the current facing direction of the token. As the token rotates, so too does the LoS cone. Now to determine LoS we simply have to check to see if the x,y position of the target token falls within the LoS cone area, if it does we have LoS, if not we don't have LoS etc. etc.

To which I replied:

You wouldn't need to actually draw the "Invisible Cone" (although that's not a bad way to think about it) - you simply need to check if the Target coordinates were within an area defined by the coordinates defining the (LOS) Cone.

The functions used to draw a Cone in the Toolkit take as arguments the Starting Coordinates of the Pointer, the Ending Coordinates of the Pointer and the Angle-Of-Arc of the Cone (the Field-Of-Vision, or FOV). This is convenient, because with these three things, plus the Coordinates of the Target, it is relatively simple to solve our problem - let me explain.

The Target lies in our Line-Of-Sight (ie within the "Invisible LOS-Cone") if (Conditions):

The Target is between the two "arms" or straight-edges of the LOS Cone, and
The distance from the Starting Point (the Attacker) to the Target is less than or equal to the length of the LOS-Cone.

Thus (Remarks):

The LOS-Cone (the Pointer) is a symmetrical cone along its major axis. Let this major axis be known as the LOS-Line.
The angle that the LOS-Line lies relative to an arbitrary Control-Line is given by the math.atan2() function.
The angle that the line from the Starting Point to the Target (hereafter known as the Target-Line) lies relative to the arbitrary Control-Line is also given by the math.atan2() function.
Therefore the angle that the Target-Line and the LOS-Line make is simply the subtraction of the two math.atan2() results (from Remarks 1 and 2).
If the absolute value (math.abs()) of the result from Remark 3 is less than or equal to half of the FOV then we have fulfilled Requirement 1 (half the FOV because the LOS-Cone lies symmetrically on either side of the LOS-Line).
If the length of the Target-Line is less than or equal to the length of the LOS-Line than we have fulfilled Requirement 2.
If both Requirement 1 and Requirement 2 are fulfilled (ie TRUE) then the Target is within Line-Of-Sight.

I then gave a code sample (the fpLOSTrue function) and a few usage remarks.

At the time of this discussion there was some brief excitement that we were well on the way to achieving (basic) LOS, but this was quickly dampened when I posted:

Not quite, no.

The Pointer Toolkit will allow us to draw a Cone Pointer based on its Starting Point and Ending Point, provided we supply the relevant function with a "hard wired" Angle-Of-Arc, which will then be drawn by FG for us.

The fpLOSTrue function will allow us to determine if a Target Point lies within the area defined by a Cone with a Starting Point, Ending Point and a FOV (Angle-Of-Arc).

The Starting Points, Ending Points and Angle-Of-Arcs supplied to both Function and Toolkit COULD be the same, but there is no intrinsic relationship between the Toolkit and the fpLOSTrue function.

The hard part is that the Starting Point, Ending Point, and Target Point need to be exposed to us by the FG Code (ie the FG Coders) so that we can use them in both the Function and/or the Toolkit - as far as the Toolkit is concerned, the Starting Point and Ending Point are exposed via the inbuilt onBuildCustomPointer function. However, we would need to have these two Points and the Target Point exposed to us in some other function for us to be able to use them in the fpLOSTrue function, and the to best of my knowledge that exposure function does not exist.

Until it does we cannot do automatic targeting (at least not via this method).

Continued in Part 2.

[dulux-oz]

Part 2
The Method/Algorithm And Function(s)
It has recently come to my attention that there are functions that expose the Target's (and the Attacker's) coordinates to us, and so I've put this thread together with a reworking of my original fpLOSTrue function.

So the method is, given:

the Image instance that the Tokens are on
the Attacker's Token
the Target's Token
the FOV for the LOS-Cone
the length for the LOS-Line
a secondary function (fpLostLOS - described later)

the following function returns a Boolean (True/False) if the Attacker has Line of Sight on the Target.


function fpLOSTrue(oImage,oAttackerToken,oTargetToken,nFOV, nLOSLineLength)

if nFOV< 0 or


nFOV> 360 then
return false;
end
if nLOSLineLength < 1 then

return false;
end
local nAttackerXCoord,nAttackerYCoord = oAttackerToken.getPosition();
local nTargetXCoord,nTargetYCoord = oTargetToken.getPosition();
local nTargetLineAngleRadians = math.atan2( nTargetXCoord - nAttackerXCoord, nTargetYCoord - nAttackerYCoord ); -- These might be around the wrong way ie maybe (nAttackerYCoord - nTargetYCoord) or similar
local nLOSLineAngleRadians = math.rad(fpAttackersFacing(oAttackerToken,oImage)) ;
local bReq1 = ( math.abs( nLOSLineAngleRadians - nTargetLineAngleRadians ) <= math.rad(nFOV)/2);
local nTargetLineLength = math.sqrt( ( nAttackerXCoord- nTargetXCoord )^2 + ( nAttackerYCoord- nTargetYCoord )^2 );
local bReq2 = ( nLOSLineLength- nTargetLineLength >= 0);
return (bReq1 and bReq2 and not fpLostLOS(oImage,oAttackerToken,oTargetToken,nFOV, nLOSLineLength));
end


The Attacker's facing is given by the getOrientation function of the Attacker's Token's instance, which returns a number representing the cardinal direction the Token is facing, with 1 being straight up the Image and then proceeding clockwise until the maximum (rn) is reached, which is the first position anti-clockwise from the straight-up position. rn depends upon the settings of the Image, and is given by the Image's getTokenOrientationCount function. Thus the Attacker's facing is given as (the angle in degrees from the straight-up position):


function fpAttackersFacing(oAttackerToken,oImage)

return (oAttackerToken.getOrientation()-1)*360/oImage.getTokenOrientationCount();
end


The FOV is an arbitrary value between 1 and 360 (degrees). In a typical Human the FOV is about 114 (for true stereoscopic vision and therefore depth perception) and near 180 (if stereoscopic vision is not required). Animals can have a FOV up to 360. For the typical purposes I see LOS being used (targeting to hit with weapons, spells, etc) we should probably use a FOV of 114 (or even less).

The LOS-Line is also an arbitrary value (at least 1). It would be dependent upon the conditions prevalent at the time ie if using torches in a dungeon than 40 feet would be appropriate, while with Darkvison it might be 60'. To get the actual value required we would need to know the scale of the Image so that we could work out the number of pixels that our choosen value would be. As an example, if the scale was set to 50px per 5'. then 40' of torchlight would give a LOS-Line length of 400.

The secondary function fpLostLOS returns a Boolean indicating if LOS has been Lost. The details of this function would probably be Ruleset-specific, and it is included in this Inital LOS discussion as a placeholder for determining all of the "special circumstances" outlined in the Further Remarks section. For the moment it is defined as:


function fpLostLOS(oImage,oAttackerToken,oTargetToken,nFOV, nLOSLineLength)
-- Determine if anything causes LOS to be lost and Return TRUE if so, FALSE otherwise.

return false;
end


I now turn this over to me fellow Devs for comment and further development.

Further Remarks
Note that the above code uses the center-points of the tokens and has no regard for the tokens' size.

Note also that while fpLOSTrue() can be used to target along a Line, within a Cone shape of any FOV (even greater than 180-Degrees) or even within a Circle, it does not and cannot work with a Square shape (the geometry formulas and logic would be different).

As far as walls and other obstructions would be concerned - if the obstruction "breaks" the Target-Line (an excellent candidate for the fpLostLOS function) then the Target would fall out of LOS. We might like to think about using more than just the Center-points of Tokens as, by its definition, a point has no length or width (it's a Zero-D object). We would have to have some sort of 2-D (or at least a 1-D object, like a line) breaking the Target-Line ie you would need to determine the Token's "Corners" or "Radius" (for a Square or Circular Token, respectively). On the other hand, if we consider the idea that if you can see >= 50% of the Target then they are targeted, then using the center-point of the Token fulfills this requirement.

Also, we may want to consider characters/monsters as a special case, because if a party member is standing between the Attacker and the Target but is closer to the Attacker than the Target than LOS may not exist (again, another excellent candidate for the fpLostLOS function), but if closer to the Target then LOS may occur (with a cover bonus of some sort, obviously - perhaps another function as part of the fpLostLOS function to indicate this?). Also needed to be taken into accout are the relative heights of the creatures represented by the Tokens - a Halfling is not going to stop LOS on or for a Giant, for example, no matter where they stand relative to each other.

[LordEntrails]

Interesting discussion.

Remarks;
- Without the consideration of obstacles, LOS is only important if; a) sight range is limited (i.e. light source dependent), or b) facing is important (some rulesets don't have facing).
- FOV of 114 degrees (or similar), assumes that the character can not turn their head.
- With obstacles, using center points for LOS determination may mix the concepts of LOS and cover (at least this is true in 3.5E rulesets).

With obstacles, what about considering a shadow type approach? I would think open-source code for 2D ray-tracing would be easily found. It would allow for complex obstacle shape definitions later on. Combining that along with range would make dungeon crawling with torches easily simulated.

Using the shadow type approach, it's possible to also combine that with the existing masking. You would have to consider the possibilities of the masking revealing parts of a token (maybe really cool, not sure how people feel about that in regards to deviation from RAWs in some rulesets).

There are more remarks if the shadow approach is to be considered.

As for tokens (monsters etc) as obstacles, I disagree with this approach, at least in the first few iterations of the tool. Because, even though tokens have a size, rarely does such a creature actually take up a large portion of their floor-print/size. DnD RAW agrees with this in most cases (though such obstacles might provide cover). Plus, even if a creature/token casts a shadow, in most environments, their is still reflected light that reveals what lies in those shadows at least to some degree (and why I would not suggest token obstacles be considered at this point).

Final remark, consider later, that dual ranges (i.e. bright light & dim light) on range sensitive LOS determinations may be needed.

[YAKO SOMEDAKY]

I'm curious about the line of sight
Is there any prediction implements - it tests for the Fantasy Grounds would be that a principle of Dynamic Lighting?

[Mad Nomad]

Line of sight would be cool. This may be more focused on line of sight for rolls and effects or something but to me the biggest gain with a line of site solution would be if it could automatically unmask parts of the map, or provide an easier way to unmask part of the map based on line of sight.

For example a character rounds a corner on my map and can now should be able to see around the wall down the hall.
I would think a good approach would be to tie line of site to the grid system.

A "simple" solution would be to allow rapid and easier demasking base don the grid.

1. Click demask grid squares button
2. Click on a bunch of the grid squares that are now visible to character.
3. Click confirm demask

An intelligent version could work mostly the same way but automatically do that grid demasking based on a grid radius from the token.
So as token movement is confirmed, If token has Line of sight value =3 grid squares, then all stuff within 3 grid squares of the tokens new position are automatically de masked. The only issue with this would be unmasking tokens behind walls. So as a GM you'd need a way to designate some grid lines as impenetrable by the auto reveal. So I can picture drawing a line on my grid that does this.

Sorry if I took this in a different direction than the original intention.

[Varsuuk]

In a "would love" category, I'd like to see an automatic unmasking as characters moved based on a light source or natural sight. The unmasking would be 360 unless the light source was a different shape. Possibly an option could be added to set your bullsEye type lantern to swing/scan as walk but that is less of a concern for me at this point, the 360 for sight is already a fudging thing to cover eye scanning but not taking into account that it is not constant because it would be distracting.


After one passes an area and it falls out of everyone's light (I'm thinking horsepower for individual areas of sight is too high) then it gets a new "mask" shading that is very light or a color filter etc to indicate an area you have seen but isn't under direct observation anymore.

[YAKO SOMEDAKY]

I would like to see in practice this dynamic lighting .... or better this line of sight