Pathfinding somewhat inconsistent wall edge behavior

[Weissrolf]

The new pathfinding feature of Drag Ruler is great, albeit a bit inconsistent with wall edges.

Way there: https://i.imgur.com/puH2PAr.png Way back: https://i.imgur.com/4oWr5ez.png

I think it may have to use a larger measuring line in order to hit those middle-of-the-wall wall-lines better. https://i.imgur.com/6HMSaTa.png

[manuelVo]

The pathfinding algorithm is built so that it generates the shortest possible path. If the walls in a scene are laid out in a way where foundry allows a diagonal step around the corner, the routing algorithm will use that step. If you want to prevent this from happening, you need to change you wall layout to one that will disallow diagonal steps around the corner. This can be achieved by either drawing a box of walls that represents the actual thickness of the wall or by adding a little piece of invisible wall sticking out of corners. Just big enough to prevent the diagonal steps, but small enough that it doesn't hinder regular movement around the corner:

There is no good way for me to prevent cutting corners in the pathfinding algorithm. The algorithm used has no concept of what a corner is. It just tries to move the step that's most likely to bring it closer towards its goal and if it doesn't hit a wall during that step, the move is considered valid, and it will continue from the new space. So since the algorithm doesn't know anything about the walls on the scene (except those it ran into when it tried to move) there are no good avenues to pursue to try to avoid cutting those corners.

As for the inconsistency, this is a result of the pathfinder stopping its work as soon as it has found the shortest path. If there are multiple shortest paths, it'll stop searching as soon as the first shortest path is found. Since in the two screenshots you're walking the path in two different directions, the decisions made by the algorithm are slightly different, which leads the algorithm to find different routes. Trying to fix the inconsistency would require to not only calculate one shortest path, but all shortest paths and then to select one of them. This would incur a performance cost which isn't worth it for the improvement it would provide.

[Weissrolf]

Thanks for the thorough explanation! :)

[Weissrolf]

One idea. Premade maps don't come with specially prepared edges and it seems like quite a chore. As a solution maybe shift or skew the module's measuring line slightly towards the direction it is heading to have a higher chance to hit edges?

So if the movement is diagonally to the right then don't measure center to center, but slightly off-center to the right. Straight movements would not be affected by this.

[Weissrolf]

But I mean to remember that you are using the methods of Foundry? So this seems like a better feature request for Foundry then.

[manuelVo]

Placing such walls can be easily done with a mall macro:

const length = 0.15; // The length of the generated wall segment, in number of squares

const lengthPixels = length * canvas.dimensions.size

function insertPointWithAngle(points, point, angle) {
  let xmap = points.get(point.x);
  if (!xmap) {
    xmap = new Map();
    points.set(point.x, xmap);
  }
  let anglearray = xmap.get(point.y);
  if (!anglearray) {
    anglearray = [];
    xmap.set(point.y, anglearray);
  }
  anglearray.push(angle);
}

const points = new Map();
for (const wall of canvas.walls.placeables.filter(w => w.data.move !== CONST.WALL_SENSE_TYPES.NONE)) {
  const wdata = wall.data;
  const p1 = {x: wdata.c[0], y: wdata.c[1]};
  const p2 = {x: wdata.c[2], y: wdata.c[3]};
  const angle_p1 = (Math.atan2(p2.y - p1.y, p2.x - p1.x) + 2 * Math.PI) % (2 * Math.PI);
  const angle_p2 = (angle_p1 + Math.PI) % (2 * Math.PI);
  insertPointWithAngle(points, p1, angle_p1);
  insertPointWithAngle(points, p2, angle_p2);
}

points.forEach((xmap, _) => xmap.forEach((angles, _) => angles.sort()));

const new_walls_raw = []

for (const [x, xmap] of points) {
  for (const [y, angles] of xmap) {
    for (let i = 1;i < angles.length;i++) {
      const angle1 = angles[i - 1];
      const angle2 = angles[i];
      const angle_diff = angle2 - angle1;

      if (angle_diff < Math.PI) continue;
      const angle_between = angle_diff / 2 + angle1;
      new_walls_raw.push({x, y, angle: angle_between});
    }
    const angle1 = angles[angles.length - 1];
    const angle2 = angles[0] + 2 * Math.PI;
    const angle_diff = angle2 - angle1;
    
    if (Math.PI <= angle_diff) {
      const angle_between = angle_diff / 2 + angle1
      new_walls_raw.push({x, y, angle: angle_between});
    }
  }
}

const new_walls = new_walls_raw.map(w => {
  const p2x = w.x + Math.cos(w.angle) * lengthPixels;
  const p2y = w.y + Math.sin(w.angle) * lengthPixels;
  const c = [w.x, w.y, p2x, p2y];
  const flags = {macro: {autogenerated: true}};
  const sight = CONST.WALL_SENSE_TYPES.NONE;
  const light = CONST.WALL_SENSE_TYPES.NONE;
  const sound = CONST.WALL_SENSE_TYPES.NONE;
  return {c, flags, sight, light, sound};
});

canvas.scene.createEmbeddedDocuments("Wall", new_walls);

And this one get's rid of them:

canvas.scene.deleteEmbeddedDocuments("Wall", canvas.walls.placeables.filter(w => w.data.flags.macro?.autogenerated).map(w => w.id));

[thatlonelybugbear]

Just needs to initialize xmap and anglearray somewhere, so I guess a let xmap = points.get(point.x); and let anglearray = xmap.get(point.y); would suffice!

Really helpful one! Cheers!

[manuelVo]

Right. Seems I missed those. Updated the macro in case anyone else is stepping by and picking this up.

[Weissrolf]

The default length of 0.15 might be too low for some movement angles. For my test map 0.25 seems to work well.