Fix Threading

[jocopa3]

This should resolve the root of issue #6. There are some situations where two or more pathfinding threads may be running at the same time as old threads are never formally cancelled. This change also guarantees that PathfinderConfig.refresh() is always called on the client thread and is refreshed before creating a new Pathfinder.

There is one side-effect that may not be desirable: if the recalculate distance is too small (<=2) and a player is running around, then a path finding thread may be cancelled before it even begins leading to times where no path is drawn. I figure most people probably leave that value at the default or set it higher and wouldn't notice. If it is an issue, it can probably be addressed by cancelling the current pathfinding thread inside the invokeLater call rather than as early as possible.

[Skretzo]

There is one side-effect that may not be desirable: if the recalculate distance is too small (<=2) and a player is running around, then a path finding thread may be cancelled before it even begins leading to times where no path is drawn. I figure most people probably leave that value at the default or set it higher and wouldn't notice. If it is an issue, it can probably be addressed by cancelling the current pathfinding thread inside the invokeLater call rather than as early as possible.

This may have been an issue introduced by me in 49d14eff46112831e4e3eaf1ef609e5b16bdf61f because WorldPoint.fromLocalInstance(...) seems to be quite slow. I have hopefully fixed this in the latest commit 8efa7f951e2b5bd1c74524733f60f518b7fbae73. As for what people set that value to, I agree that most people keep it at the default, but I have also seen quite a few people set it to 0 so that they always see an updated path. This is a known challenge because this leads to a new path being created every tick when they walk/run around, and sadly long and complicated paths currently require up to several seconds to calculate. Feel free to try your suggested cancel approach or just test if the issue is still there.

I should probably also point out that the version of the plugin that is currently live in the client is b57d79bfc2ded948195b68d645bd26024fe5d817, which can now also be found in the v1.9.3 branch. Some of my later changes in 487dda0c815bfb33396d7904e53c5887d5638b9b are necessary to get more accurate paths, but slows down the pathfinding noticeably for longer paths. I think we have to accept this slower pathfinding, but it also introduced a bug which I am yet to fix. I think you also encountered this bug so if you found a fix for that too I would like to look a little bit at that before going forward with this PR.

Also, it seems like GitHub uses some kind of smart merging as it claims there are no conflicts in the ShortestPathPlugin.java after 8efa7f951e2b5bd1c74524733f60f518b7fbae73, but that might confuse us when testing this PR.

[jocopa3]

I should probably also point out that the version of the plugin that is currently live in the client is https://github.com/Skretzo/shortest-path/commit/b57d79bfc2ded948195b68d645bd26024fe5d817

Didn't catch this before. That explains some of the differences I see from latest compared to the live build including some noisy exceptions.

Also, it seems like GitHub uses some kind of smart merging as it claims there are no conflicts in the ShortestPathPlugin.java after https://github.com/Skretzo/shortest-path/commit/8efa7f951e2b5bd1c74524733f60f518b7fbae73, but that might confuse us when testing this PR.

I can rebase the branch to capture the latest commit so it incorporates your latest fixes.

I think we have to accept this slower pathfinding

I mentioned this in private but will also mention here for transparency. I've found quite a few pathing bugs and slower path finding comes down to the handling of this branch in CollisionMap which causes the search radius to expand unnecessarily in specific spots. Altering that branch slightly to account for fairy rings as a hack-fix improved performance 2.5x on my (admittedly overpowered) machine but I don't want to PR such a specific hack as a "solution".

I'm experimenting with a bi-directional BFS locally which also seems to speed up path finding a bit. The bi-directional approach seems desirable for this problem as it makes detecting unreachable destinations quicker without exhausting the whole search space, but I don't have a clever way to find the optimal closest reachable point without searching everywhere just yet.

Should be noted bi-directional BFS is not assured to be truly optimal when transports/teleports are considered due to them having varying costs, but I don't think the current pathfinding algorithm is truly optimal in those cases either at the moment. There is a more recent paper that covers a few different optimal bi-directional heuristic searches that may prove be useful if I have time to look into it further. (See also: https://codereview.stackexchange.com/questions/143527/nba-very-efficient-bidirectional-heuristic-search-algorithm-in-java)

[Skretzo]

Should be noted bi-directional BFS is not assured to be truly optimal when transports/teleports are considered due to them having varying costs, but I don't think the current pathfinding algorithm is truly optimal in those cases either at the moment. There is a more recent paper that covers a few different optimal bi-directional heuristic searches that may prove be useful if I have time to look into it further. (See also: https://codereview.stackexchange.com/questions/143527/nba-very-efficient-bidirectional-heuristic-search-algorithm-in-java)

My main concern with using A* or a variant of it is actually not the transports/teleports, but rather if the standard walking path without transports/teleports remains accurate to the in-game pathfinding. If not, then your in-game character ends up walking a different path than the suggested shortest path because there are usually several possible shortest paths. Maybe not a big deal, but it looks a bit weird in my opinion. A bi-directional BFS sounds interesting though.

[Skretzo]

I just now updated the collision map for the master branch. This was actually important because it prevents some buggy pathfinding where the path suddenly noclips across the map. It was actually caused by legitimate walkable tiles "floating in the air", typically found at z > 0 (black tiles on the minimap). These tiles are unreachable for players (unless you are a jmod), so I just set them to be blocked instead.

[jocopa3]

Force-pushed to rebase and capture latest commits. Up to date with branch skretzo:master.