The temporary waypoints from FindLocation will prefer to connect to an unreachable edge over a reachable edge, so long as it is closer

[MomoPewpew]

We've been running into some problems where specific coordinates could not be reached via findlocation. After a lot of digging and testing, I finally understand why.

I was under the impression that the FindLocation command would bring you as close to the coordinates as possible, and then connect the remainder via a temporary edge. But the way that it's done right now is the opposite: It will connect the temporary node to the nearest point along an existing edge, and then try to bring you to that connection. The problem is, this is not always the shortest route, or even a possible route.

Example screenshot:

If I'm at the lapis block and I try to navigate to the redstone block's coordinates, then that navigation will fail regardless of my distance setting. Because the redstone block will connect to the emerald line, and then the navigator concludes that navigation is impossible because the emerald line cannot be reached from the lapis line.

This is the case even when distance settings would have allowed the redstone block to connect to the lapis line directly.

I'm not sure what the most elegant solution to this problem is, or even whether a solution is desired. But this is the nature of our problem.

[CubBossa]

Hey, thanks for reaching out. I haven't stumbled across this issue since I run extensive tests on my hogwarts map and its a single connected graph, so usually there always is a shortest way.

The way I programmed it is rather simple, I have an injector that adds external locations like player location or target location via temporary node to the nearest edge in a 90° angle, like you noticed. And then just starts the usual navigation process.

The navigation algorithm is a modification of the dijkstra algorithm, which finds the shortest path to any nodes on the graph. To programm a solution for your specific case, I would need to find the closest point on any edge to the target location to be 100% correct or if I just wanted to approach the optimal solution find the nearest node and check its neighbouring edges and if sections of them are even closer to the target than the node. And then I'd check if the target is within reach from that point on.

From a users perspective, this would make more sense. So I'll leave this issue open to track progress on an implementation for "findlocation":

• Inject player and target locations
• Run a shortest path search with modified dijkstra
• Render result or if no path found:
• Find nearest point on graph to target location that is still part of the players island by iterating edges with linear effort
• Check if distance from nearest point to target location is within config range for "findlocation"
• Render result or print message

I'll cache the point edge distance results from step one to reuse in step 4, so there won't be a big performance impact

[CubBossa]

changed my mind.

• Sort all edges of the players island by distance
• Pick the edge with the smallest distance
• Inject target into that one if distance smaller than config value, otherwise say no path found

[CubBossa]

Now the final mechanism connects external nodes to ALL islands of the graph if the nearest edge is nearer than the configured min distance. It makes the most sense but doesn't mean there is always a way. Like you can see in the image, only the center path is valid, but if the island of the centerpath doesn't provide a connection from its start node entry point to the target node entry point (due to directed edges), it will not find a possible way of course. Which is intended behaviour. In the end, the graph should do most desicion and the entry points should only help to connect external nodes into the graph in the most fitting way.

[CubBossa]

Left to do: regression that makes the playernode no longer a grouped node, hence not rendering particles from player position on but from first graph node.
And I need to check the function to extract islands against directed edges. a->b is one island if starting from a, but two islands if starting from b?

[MomoPewpew]

I tried out the fix, and in the case that I described it seems to work great!

Regarding the islands with directed edges:

I tried out a case similar to my example above, but where the "second island" is connected to the main island via a directed edge. This causes an uncaught error to occur.

I suspect that this is because the two groups are treated as being a part of the same island, so the 'end' node only connects to the unreachable part of the island

[19:15:27 ERROR]: [PathFinder] Unknown error while finding path.
java.lang.IndexOutOfBoundsException: Index -1 out of bounds for length 0
        at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100) ~[?:?]
        at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:106) ~[?:?]
        at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:302) ~[?:?]
        at java.base/java.util.Objects.checkIndex(Objects.java:385) ~[?:?]
        at java.base/java.util.ArrayList.get(ArrayList.java:427) ~[?:?]
        at PathFinder-5.3.1.jar/de.cubbossa.pathfinder.navigation.AbstractNavigationModule.lambda$navigate$5(AbstractNavigationModule.java:137) ~[PathFinder-5.3.1.jar:?]
        at java.base/java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:178) ~[?:?]
        at java.base/java.util.AbstractList$RandomAccessSpliterator.tryAdvance(AbstractList.java:708) ~[?:?]
        at java.base/java.util.stream.ReferencePipeline.forEachWithCancel(ReferencePipeline.java:129) ~[?:?]
        at java.base/java.util.stream.AbstractPipeline.copyIntoWithCancel(AbstractPipeline.java:527) ~[?:?]
        at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:513) ~[?:?]
        at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499) ~[?:?]
        at java.base/java.util.stream.FindOps$FindOp.evaluateSequential(FindOps.java:150) ~[?:?]
        at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) ~[?:?]
        at java.base/java.util.stream.ReferencePipeline.findAny(ReferencePipeline.java:652) ~[?:?]
        at PathFinder-5.3.1.jar/de.cubbossa.pathfinder.navigation.AbstractNavigationModule.lambda$navigate$6(AbstractNavigationModule.java:137) ~[PathFinder-5.3.1.jar:?]
        at java.base/java.util.concurrent.CompletableFuture$AsyncSupply.run(CompletableFuture.java:1768) ~[?:?]
        at java.base/java.util.concurrent.CompletableFuture$AsyncSupply.exec(CompletableFuture.java:1760) ~[?:?]
        at java.base/java.util.concurrent.ForkJoinTask.doExec(ForkJoinTask.java:387) ~[?:?]
        at java.base/java.util.concurrent.ForkJoinPool$WorkQueue.topLevelExec(ForkJoinPool.java:1312) ~[?:?]
        at java.base/java.util.concurrent.ForkJoinPool.scan(ForkJoinPool.java:1843) ~[?:?]
        at java.base/java.util.concurrent.ForkJoinPool.runWorker(ForkJoinPool.java:1808) ~[?:?]
        at java.base/java.util.concurrent.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:188) ~[?:?]

[CubBossa]

NavigationLocation start = route.getStart();
NavigationLocation end = route.getEnd().stream().filter(l -> l.getNode().equals(path.getPath().get(path.getPath().size() - 1))).findAny().orElseThrow();

The exception is being thrown here in the second line. I suppose from path.getPath().size() - 1, which then results in -1 and the according exception Index -1 out of bounds for length 0.

I only wonder how you manged to obtain a path with 0 nodes. It should either respond with NoPathFoundException or a valid path. I'll try some different setups to reproduce but maybe I'd need you to create a minimal example or send me your node database if thats fine.

[MomoPewpew]

I'll happily send you my testing database after work if needed.

The steps to reproduce were as follows:

Create a line of points from A to B, where point B is connected via a directed edge (in the direction of A)

Go to point A

Use findlocation to navigate to coordinates that are on the opposite side of point B

[MomoPewpew]

I have attached my pathfinder plugin folder, including a recent dump.

This is a very simple test setup, where the bug can be triggered by standing on 5539 60 4902 and navigating to 5556 59 4848 (or any location that is behind directed segment)
PathFinder.zip

[CubBossa]

Thanks a lot, I successfully reproduced the error!
My fix will be to throw a NoPathFoundException, because it successfully connected to the graph but with directed edge the graph explicitly didn't allow to navigate to the target. Is this what you had in mind too?

[CubBossa]

Okay so the exception now throws like it should, because the player and target connect correclty to the graph and the graph does not provide a valid path from player to target.
I noticed that you get an empty chat message whenever a path fails, I'll make a more convenient way to prevent the default message today too and maybe release today too after some proper testing

[MomoPewpew]

I'm happy to hear that you had progress!

To me, the ideal solution would be that if a part of an island B cannot be reached from the players current location on part A, then that part is treated as a different island entirely. So it would either handle them as island A and island B, or as island A and island AB

If I understand your algorithms correctly, then this would lead to the target connecting to both parts of the split island (provided that they are both within range). It would then get as close as possible on island A and do the remainder with a temporary line, ignoring the connection to island B.

I'll describe the situation on our server that had us run into this problem:

We have one giant island that covers every intended walkable path in the city

Flying overtop of the city, we have a branching elytra network, that connects a single point in the sky to 50 flying points across the entire city via directed edges. These flying points are in turn connected to every outdoor point on the ground that is within radius 50 of that point.

This works great, and allows our emergency service roleplayers to quickly find any players on the server with their gliders.

But a problem occurs when a player who is currently on the ground tries to find a location that is nearest to one of the "elytra network edges". Since these edges are directed downwards at an angle, and can only be reached from the elytra launch point

[CubBossa]

Your elytra system sounds pretty exciting!

You're right about the algorithm, it should work that way. I'll change it.
Sadly it will reduce performance quite a bit on graphs with a lot of directed edges and no entry distance limit, but I think correctness has priority.

Thanks for having a close look at how things work and discussing with me how to improve. This is pretty much the first time I am having an indepth conversation about what I coded in the plugin and the feedback is really appreciated

[CubBossa]

So the last commit solves the issue with correctness in mind.
Like you suggested islands are now based on directed edges.
This means that a graph with lots of directed edges or worst case a ring of nodes with only directed edges will have that many islands.
This is an absolute bottleneck in the algorithm and I really need to imrpove the performance of it. And also there is a bug that occasionally causes empty paths. Maybe I'll try a totally new approach like just connect to all edges within reach and thats it, dropping the whole island idea. Might be more efficient.

I will work on these two things next week I am without internet for the next 9 days

[CubBossa]

So the per edge connection fixed the scalability issue. The algorithm simply connects the player and the target to each edge that intersects with the sphere of configured radius around them. All those new edges to connect to the intersecting edges have a much higher weight, which will motivate the path finding algorithm to not use these temporary edges a lot and instead get on the actual graph asap. Your scenario would work fine because it will try to navigate across the dead end, fail and try another edge.
Hope that helped! I'll close the issue, just reopen it if problems remain