Improve the logic used to filter ray emission angle when computing polygons to always include rays that target exact endpoints while only filtering rays that are ancillary to those endpoints due to angle offsets or radial density.

[aaclayton]

Not sure if this will be regarded as an actual "bug", or just an enhancement request, but long-distance sight is still broken in 0.7.5.

Unfortunately, due to all the vision changes in 0.7.x, I don't think there's any longer an easy workaround that my token-vision-tweaks module can apply to fix this, which used to be options.cullMax = Math.max(options.cullMax, options.cullMin); in SightLayer.computeSight. Now, not even increasing the density of the rays to ridiculous levels (e.g. 0.0001) seems to fix this. I've also tried increasing SightLayer.EXACT_VISION_THRESHOLD to 10000000000000000 and this does not get resolved, so it's not because of that optimisation.

Example image attached, note how far away from the selected unit (top-left corner), some of the tents (which have walls around them) are partially see-through.

[aaclayton]

Hi @MrManly, this issue is closed - but continued discussion about various sight computation limitations continues here: https://gitlab.com/foundrynet/foundryvtt/-/issues/5313

In response to your message however - the rays which are "wasted" are still necessary. We only know that these extra rays are wasteful after-the-fact, we don't know that ahead of time. If (for example) there was a gap in your cave wall, we would not be able to identify that gap without these rays.

I agree that when the ray does collide with a wall, it's a waste of computation - but we don't know ahead of time that will be the case so we have to fire it!

[aaclayton]

Originally in GitLab by @MrManly

Hey, I have noticed an issue with the current vision algorithm (see screenshots). A LOT of rays are "wasted" on redundant information at close range. Because of that however it seems that obstacle walls that are slightly farther away are not not registered at all.

The screenshots have been made with all modules disabled. I have tested removing some wall detail and it didn't really do anything.

[aaclayton]

For this particular problem, I am going with a solution that avoids filtering rays which target a specific wall endpoint based on their angle-of-emission. This does result in more rays being cast and could have negative impacts on performance - which is worth monitoring.

I can counter-act this by reducing the EXACT_VISION_THRESHOLD from 500 to 200 which will work better for large maps which tend to have a very dense layout with lots of walls.

[aaclayton]

marked this issue as related to #4878

[aaclayton]

I'm working on this issue for 0.8.2. The example setup @dev7355608 shared is particularly helpful. Also @mainecoon1's intuition about the quadtree testing order seems valid.

This ended up being a separate (but related) issue which I have forked over to #4878 and resolved - commentary on the resolution is in that issue.

[aaclayton]

Thanks for the thoughtful analysis @mainecoon1 - this is consistent with my own theory about why the correct collision is not detected - the algorithm for determining neighboring quadtree nodes needs to sort by depth in descending order (to test the smallest neighbors first) which it currently does not do.

EDIT: Actually your example shows a good illustration of why the neighbor set isn't sufficient in this case. I'll have to think more on the right way to perform this check or alternative algorithms that can substitute.

[aaclayton]

Originally in GitLab by @mainecoon1

It appears the issue is due to how the quad-tree is traversed, and how rays can be considered "complete" before they've crossed every eligible quad-tree node.

After rays are generated, the quad-tree is traversed starting with the leaf node containing that the origin point of the light/viewer. It tests all rays against walls in this node, then finds all adjacent nodes by testing a rectangle slightly larger than the node, against the quad tree.

As the quad-tree may have uneven distribution of sub-divisions, the technique above can result in finding and testing a large node with few walls that are further away than walls in intervening smaller nodes that have yet to be added for a testing pass. A collision at this point can cause the ray to be marked complete, and never tested against other intervening walls.

[aaclayton]

Originally in GitLab by @anathemamask

Additional data as provided by @RogueEntityX

Disclaimer I apologize, as this may be long and meandering. It's an issue I do not fully understand, nor am I aware of the full impact or implications. This is a bug which seem to do with core, but may also be related to scene imports from Roll20, DDB, or other sources.

Back in November, I was helping a user in Discord chat (which we eventually took to DMs). His issue was that he had a scene (from DotMM, supposedly imported from Roll20) where a player token was able to see through a normal wall (from here out referred to as Offending Wall, or OW), but only when standing in certain locations.

Player View || DM View (Walls Layer)

This issue occurred when any token with vision was within 2 grid squares from the right most wall (RMW). Note that emission from a light source on the left of the OW could be seen by the token, but the emitted light itself did not extend through the OW to the right, even though the token could see through the OW to the left. I did doublecheck the Wall Direction settings, which was set to Both. If the token was more than 2 grid squares away from the RMW, the OW would then block vision as expected. Also, with light sources turned off, the token could still see through the OW with a high enough vision distance.

I had joined the user's Foundry instance as GM (via browser) to further investigate, and try to remedy the issue, as well as had him export and send me a copy of the scene to test in my own world (in the native app). The issue also appeared in my test world and his, with no modules enabled. I tried the following troubleshooting:

1) Extending the "door" wall up -- resulted in only limiting the position the token could be at to fewer grid spaces along the RMW--more perpendicular to the OW, a smaller angle, rather than anywhere along the RMW). 2) Deleting and recreating the entire OW -- no change. 3) Placing a second wall over top of the OW -- no change. 4) Placing a second wall >= 3 subgrid points to the right or >= 2 full grid squares to the left of the OW -- vision is properly blocked by the newly placed wall. Anywhere in between and the same issue still occurs.

I then attempted to recreate the scene: 1) Right-click to duplicate the scene -- no change. 2) Manually create a new scene, drag-select all walls, copy and paste to the new scene -- no change. 3) Manually create a new scene, ALT+click to select connected walls, copy and paste to the new scene -- no more issue, problem seemingly solved.

I exported the .json and sent it back to the user, who imported it and confirmed it was working in his world. I have not heard back from him on any issue with it since.

---

Just today, 7 Feb 2021, there was another user in Discord with a seemingly similar problem. The user says it was imported from a DDB adventure module.

Player View || DM View (Walls Layer)

The token is able to see through the wall/door marked by the circle when in the area roughly outlined by the red polygon area. In this case, dragging the "door" wall further across the NW wall, or dragging the NW wall across the door resolved the issue visually, but then makes that part of the scene not usable as intended (upon moving them back, the issue reappeared). I asked the user to attempt to recreate the scene as I had in the previous instance, and said that it worked at first, but after replacing the terrain walls around the tents in the scene, the issue reappeared, or appeared intermittently. I had the user send me the exported scene and tried to recreate it myself. I was able to resolve the issue with a new scene and copied walls, but was not able to reproduce the user's claim of it recurring after copying over the terrain walls (Note: in the screenshot above, I had moved the terrain walls out of the way to be able to determine the area in which the token experienced the issue.)

After helping this user honeybadger, mxzf, and some of the other helpers and mods suggested I use CONFIG.debug.sightRays = true to get some screenshots of the sight calculation lines, and create this report.

I am also including the original exports of the scenes as given to me (but without the bg images).

[aaclayton]

marked this issue as related to #4271

[aaclayton]

marked this issue as related to #4270

[aaclayton]

marked this issue as related to #4273

[aaclayton]

@dev7355608 that looks like a useful setup which reproduces a clear problem - thanks for sharing it as a test case. My plan for this is to make the optimization improvements to the different component algorithms of the system and then after those optimizations are made do some testing to catch any remaining issues (including this one).

[aaclayton]

Originally in GitLab by @dev7355608

I reduced the column scene as much as possible, I think. If I delete one more wall, the rays hit the wall they are supposed to. But only after reloading interestingly: I can delete all but these two walls, and still the rays don't hit the wall they're supposed to.

[aaclayton]

Originally in GitLab by @dev7355608

@aaclayton The "column problem" is different. The wall the rays should actually collide with only appears in the batch after the one in which it is concluded that the closest point has already been found. Not sure why this is happening, but that seems to be the problem.

[aaclayton]

Originally in GitLab by @dev7355608

@aaclayton I just had a quick look at the code when I read about #4430 and discovered this issue.

I figured out what the cause of problem is (at least of the problem shown in first image of this issue, not sure about the column case). It's the tolerance of the ray angles in _castRays. For very large maps tol needs to be 500 to 1000, which has a noticeable performance impact of course.

    // Define de-duping cast function
    const cast = (ray, tol=50) => {
      let a = Math.round(ray.angle * tol) / tol;
      if ( angles.has(a) ) return;
      rays.push(ray);
      angles.add(a);
    };

We only need the higher precision for wall endpoint rays, right? Maybe it's better to do something smarter like this:

    let cast = (ray, toWallEndpoint=false, tol=50) => {
      let a = Math.round(ray.angle * tol) / tol;
      if (toWallEndpoint) {
        angles.add(a);
        const endpoint = ray.B;
        const x = Math.round(endpoint.x);
        const y = Math.round(endpoint.y);
        const p = `${x},${y}`;
        if ( destinations.has(p) ) return;
        destinations.add(p);
      } else if ( angles.has(a) ) return;
      rays.push(ray);
      angles.add(a);
    };

    // Track rays and unique emission angles/destination points
    const angles = new Set();
    const destinations = new Set();
    const rays = [];

and use cast(ray, true) in the wall endpoint loop.

[aaclayton]

Originally in GitLab by @DerGote

@aaclayton Thank you for adding the example to this issue! Furthermore I can provide the .json file, which might help tracking down this nasty bugger. ;) Cheers!

[aaclayton]

Another example provided by @DerGote

Environment Details

• Foundry VTT Version: 0.7.9
• Operating System: Windows
• How Are You Using Foundry: Firefox
• Which Game System: Pathfinder 1
• Modules Enabled?: no

Issue Description

Tokens can uncover fog of war and gain vision to areas, that should be obstructed by walls. In order to reproduce this, the walls have to be behind two or more "columns" (for me a column was represented by a hexagonal wall structure), which cast their vision blocking "shadow" on a square shaped wall formation. As a result the visible area between two columns is ignoring walls behind those columns. This behavior does not occur without the columns. Also see attached video:

[aaclayton]

Example scene attached which demonstrates the issue at the following position:

[aaclayton]

I want to get my hands on a scene that is as simple as possible while producing this type of clip-through artifact. I have some ideas about aspects of the algorithm I could change to ensure better fidelity but I need to develop a good test sandbox for it.

[aaclayton]

Originally in GitLab by @anathemamask

Per instruction, screenshot dump and discord link:

https://discordapp.com/channels/170995199584108546/713259405667205193/780635861393997874

https://i.imgur.com/rtyJyFY.png

https://i.imgur.com/tf8ToR9.png

https://i.imgur.com/EYUNQFu.png

https://i.imgur.com/JjwpQOy.png

https://i.imgur.com/6T2gNVP.png

https://i.imgur.com/Qr1YsJ8.png

https://i.imgur.com/TpIw77l.png

https://i.imgur.com/VeilEbp.png

https://i.imgur.com/FBJPQV7.png