Shortest path finding issue

[Varstahl]

I was doing some testing with lights and paths, when I did a simple test across a wall and this happened:

Instead of choosing the 29 feet path, it went all around the wall on the other side and chose the 77 feet path. The wall is grid-aligned (despite me roughly drawing the wall position by hand).

[Exote]

Yes, this has been annoying me for a while. The problem originates from the module I am using for pathfinding (and maybe from polygon based mesh pathfinding in general?)

Using the examples from the module hxdaedalus-js

https://rawgit.com/hxDaedalus/hxDaedalus-Examples/master/hxDaedalus-Examples/web/DaedalusPathfinding.html

As far as I can tell it is initially optimising the route based on the number of navigation mesh triangles a path passes though, rather than the resulting distance.

[Varstahl]

Judging by my "awesome" visualization which took me way more time than it should've, it is working on the shortest path, the problem is that it's considering shortest whatever can be solved with a lesser amount of waypoints:

Which, on a 2D grid system would be equivalent, and I think A* might bring the same results. I didn't investigate hxDaedalus enough, and I'm not an expert on pathfinding, so I don't know if there's a different way to weight the distances.

If I'm not mistaken there was an option in the libDaedalus hx is using that forced a maximum distance to be considered as a step, and if there's an option to do it while using hx, setting it to 5 units would increase significantly the path length of the longer paths, at the cost of a bigger drawing time.

Edit: path sampling

[Exote]

The path sampling seems to refer to stepping along a path for use in animation once a path has been calculated. Rather than in adjusting how the path is calculated.

[Varstahl]

Ah, yeah, seems I misread that. I was also looking at their implementation of the A* algorithm, and I might have found the issue: euclidean distance squared.

I've found several instances inside the hxDaedalus implementation of this technique, although I'm not a 100% sure that's what causes this bug.

Eventually, if we were to reimplement portions of hxDaedalus and adapt the A* algorithm, it would be possible to just alter the distance calculation using manhattan, diagonal or euclidean distances, fixing #9 in the process while having minimal to no impact on the codebase.

I'll tinker some more with the library and see if I'm correct about the assumption.

[Varstahl]

GOT IT. Their A* algorithm is broken. Here's the problem, visualised:

cyan = walls, purple = triangulation edges, white circles = middle points, green = start, orange = red

Basically the algo performs quite well up until the point where there are no big wide gaps, because if they do they only calculate the passing points as the middle between the two vertexes of the segment. In my tests above, the middle point would drift some 2000+ pixels, which would skew the path toward the right one. I "fixed" it for my case scenario by checking the closest vertex of the segment and using that to go through, and now Route Finder performs fairly well. To actually fix it, we need to add a "shortest intersection" between the current position and the the open path segment, which I didn't do yet.

So, here comes the question, now. Do we:

1. remove the hxdaedalus-js dependency, patch the compiled version, minimize it, ship it with the module and call it a day
2. fork hxdaedalus, make the adjustments needed and maybe make it into an external module for foundry.
3. on top of 1 or 2, use multiple distance methods and cell snapping, to allow proper distance calculation for different tabletop styles, and fix Option that moment through a (friendly token) is counted as difficult terrain (10" instead of 5") And DMG Movement Rules for diagonal (5/10/5) #9 in the process.

I'm up for anything, including doing nothing, since this is your module I'll let you choose.

This is the place that needs fixing, for reference:
https://github.com/hxDaedalus/hxDaedalus/blob/a777af0b66529c05bc470cd53e0643832a3446d7/src/hxDaedalus/ai/AStar.hx#L178-L181

[Norc]

I think my problem is another case of this issue. I have hostiles (skeletons) blocking movement for the player (selected):

versus going one tile lower:

No modules enabled, Foundry 0.60 and Route-Finder 0.3.11.

[Varstahl]

Yeah, it looks like the same issue. I'm currently fixing hxDaedalus and kinda want to optimise it a bit, reduce it to the most useful things and publish it as a separate foundry module. Pathfinding in Foundry could be quite useful to a lot of people if implemented correctly. Think automated patrols across dungeons and things like that.

At the moment I only tested a hackish version but it temporarily works "alright". If you open route-finder/node_modules/hxdaedalus-js/hxDaedalus.js and replace this two lines here

https://github.com/hxDaedalus/hxDaedalus/blob/a777af0b66529c05bc470cd53e0643832a3446d7/src/hxDaedalus/ai/AStar.hx#L180-L181

entryPoint.x = ( innerEdge.originVertex.pos.x + innerEdge.destinationVertex.pos.x ) / 2;
entryPoint.y = ( innerEdge.originVertex.pos.y + innerEdge.destinationVertex.pos.y ) / 2;

with

var v = innerEdge.get_originVertex().get_pos();
var w = innerEdge.get_destinationVertex().get_pos();
entryPoint = fromPoint.distanceTo(v) <= fromPoint.distanceTo(w) ? v : w;

it should perform significantly better. I'm working on a generalisation, hope to have it available today.

[Varstahl]

Ok, so, after having spent way too much time on this:

• Here's the long and boring explanation of what I done did
• Here's the hxdaedalus-js PR, if they ever accept and update
• Here's my version of the Daedalus library, which I will improve for the specifics of Foundry and eventually convert into a full fledged module removed it after considerations about Daedalus viability
• And finally here's the modified hxDaedalus JS

@Norc I've tested your scenario as well, it seems to be working much better. If you want to try you can download the JS linked above, replace the node-modules version, and compile the addon with webpack.

Of course since A* needs specific fine tuning, it won't ever be perfect, that's the tradeoff for its speed.

Post scriptum

Wouldn't you say this is rather a-maze-ing? No? I'll see myself out.

[Exote]

Hey,

Sorry, I've been quiet on this for a few days, busy at work etc.

I had a look this afternoon at removing all the external modules and attempting to write a foundry specific implementation.

Not ready as a module yet, but as a start:
https://github.com/Exote/foundry-vtt-router-finder-grid/blob/master/scripts/js/index.js

The general problem is that while the main system is grid based the walls are not, so regular wall/no wall grid arrays won't work.

I opted to use the inbuilt foundry methods of raycasting from each grid cell to find if a token would be allowed to walk to the adjacent squares. This allows a linked list to be built about which grid squares can link together.

After this is it pretty much boring old A*, I've added config to allow different weights to diagonal vs orthogonal.

[Varstahl]

I've thought of it but that won't work (as) nicely, I think. There's a lot of overhead which increases proportionally to the size of the grid and the number of walls, it could easily tank the performance.

The changes to the A* I introduced reduce the travel distances by quite a lot and work quite predictably and accurately. The only thing left to do would be to lock them to the grid during funneling, and that's where all the grid customization can take place.

I love how your module is agnostic, I wouldn't want to lose that. Then, again, if you implement the pathfinding system by itself detached from Route Finder, it'd be easy for Route Finder to use whatever system a user decides to have on their system, RouteFinder+Grid or RouteFinder+Ariadne, or even other new and different pathfinding modules that would come up at a later date.

Edit: I was thinking back and maybe you're correct, while it most definitely changes and increases the computation, it's the best way to get the most accurate path.