Optimizing pathfinding

[TiltedTeapot]

I've noticed significant improvements with this new implementation of A compared to the current one. I will have to make and run some tests to compare the two versions better. I believe this implementation could see further improvements with reworks to the entire A (I left it as is for backward compatibility). This implementation will also make multithreading easier for both individual searches and parallel searches.

Implements fixes for Issue #442

[TiltedTeapot]

This is my first time writing in Rust so any advice would be helpful!

[TiltedTeapot]

Current results on (windows10 tr2920X):	Test	Current A*	New A*
Tests on master	~0.97s	~0.33s

[TiltedTeapot]

When creating a partial path, is the objective to find the most efficient path to the nearest accessible vertex to the objective vertex or the most efficient path to get as close as possible to the objective vertex @mrDIMAS?

In the first case we expect the path to end at the closest available vertex. In the second case we expect the path to get as close as possible to the objective without wasting energy.

for example the first case would go all the way around the other side of the objective's island if it was closer, whereas the second case would not.

[TiltedTeapot]

Current results on (windows10 tr2920X) single thread:	Test	Current A*	New A*
Complete grid (size 10^2)	~0.049s	~0.051s
Complete grid (size 40^2)	~0.968s	~0.277s
Complete grid (size 100^2)	~13.269s	~1.087s
Complete grid (size 500^2)	>300s	~19.037s
Island (size 100^2)	>300s	~15.519s
backwards travel (size 100^2)	~19.199s	~1.899s

*All benchmark times are total from 1000 iterations

[TiltedTeapot]

Final Results (windows10 tr2920X) on single thread:

Test	Current A*	New A*
Complete grid (size 10^2)	~0.049s	~0.045s
Complete grid (size 40^2)	~1.023s	~0.194s
Complete grid (size 100^2)	~14.569s	~0.509s
Complete grid (size 500^2)	>300s	~2.822s
Island (size 100^2)	>300s	~4.626s
backwards travel (size 100^2)	~21.135s	~0.781s

*All benchmark times are total from 1000 iterations

[TiltedTeapot]

I tried for about a week to get favorable results on multithreading a single search but honestly, unless you are trying to find the best path it is only slower.

The implementation I settled on is significantly faster but does use more memory. I am happy with the result as it is

[TiltedTeapot]

I renamed the path generation methods and separated returning vertex indices and returning positions into different methods instead of using a generic func. These changes make the names clearer and how to use the methods less confusing. I left the build() method as depreciated.

[mrDIMAS]

Very nice results! Sorry that I didn't respond, I was busy with other stuff (navmesh path straightening - a.k.a string pulling). About the algorithm itself - I'm I correct that it is still classic A, but with binary heap that gives major optimization (that basically replaces linear search with O(n) complexity to binary search with O(log(n)) complexity)? I'm a bit confused about the iteration counter (for i in 0..1000), why it is needed in the first place? I'm not an expert in A by any means, so excuse my potentially dumb questions.

[TiltedTeapot]

It appears we are in vastly different time zones, so long delays in responses are inevitable. I am by no means an expert on A* myself, but I did quite a bit of research for this PR; I will give some background information to help explain my implementation and answer your questions. Don't worry about asking dumb questions I would rather answer them than realize something in my code has no purpose 😂. I also have a bunch of solutions to a problem I noticed at the end, please let me know what you think.

Background

A is more often used to find the best path across a set (graph) of nodes (vertices) and connections, instead of a path that is good enough. A very fast when the graph is optimal, but can waste a lot of time when it is not. In most cases this is due to A being blind to the big picture because it only looks one set of neighbors in the future. For example, when A is trying to find a path between 2 islands (sets of nodes that do not share a connection), it will search every node on its starting island looking for a connection that doesn't exist. A can see major differences in efficiency based on use-case and Implementation. A is generally quicker than other search algorithms when the graph is simple, but consumes a comparatively high amount of memory.

Q&A

Q: Is this still classic A, but with binary heap that gives major optimization (that basically replaces linear search with O(n) complexity to binary search with O(log(n)) complexity)? A: Yes, my implementation is even more akin to classic A. In your case you enumerate over every vertex each iteration O(n), Mine only pops a binary heap of neighbors of searched vertices O(log n). If we take into account search set composition and search method for complexity; yours: *O(vertices iterations), mine: O(log(neighbor vertices)* iteration). So not only is the search method more efficient but so is the set we are searching. A BTreeSet is actually most similar to classic A*, but I found it was slower in most cases because we don't search most of the vertices we store and the time spent sorting them is wasted.

Q: Why does your search algorithm need a maximum amount of search iterations? A: The short answer is that it doesn't. The long answer is that when the graph is large (high vertex count) and very complex (has lots of isolated islands, islands with a single connection, or valleys where there are no connections) A quite plainly sucks. A will search a large portion or all of the vertices before it reaches its conclusion. In the case of 500^2 (250 000) vertices if there is a possible path and the complexity is not extreme, A should reasonably be able to find it in less than 10 000 iterations. I understand that for users of games that are created on Fyrox it would be aggravating to see a possible path (probably one that in A's case would be considered extremely complex) and have the game tell them "There is no path". Therefore, I agree that a maximum amount of search iterations is probably not the best way to handle this problem but I left it in my code to raise awareness of this problem.

How best assist A* in its worst case scenarios

When A* is trying to find a path between 2 islands (sets of nodes that do not share a connection), it will search every node on its starting island looking for a connection that doesn't exist

When the graph is large (high vertex count) and very complex (has lots of isolated islands, islands with a single connection, or valleys where there are no connections) A* quite plainly sucks.

Don't do anything

The simplest solution would be to just let A* run its course and eat the time loss.

Benefits

• It's easy to implement.
• Gives some control to the programmer.
• Fastest in best-case situations for A*.

  Drawbacks

• Programmers either need to not use our A* if this case is common for them or make their own implementation.
• Wastes a lot of time every time A* encounters a bad case.
• Most programmers will not notice this issue.

Make it explicit in the documentation

The next simplest solution would be to just let A* run its course and eat the time loss, but make it explicit to the programmers.

Benefits

• It's easy to implement.
• Gives some control to the programmer.
• Fastest in best-case situations for A*.

  Drawbacks

• Programmers either need to not use our A* if this case is common for them or make their own implementation.
• Wastes a lot of time every time A* encounters a bad case.

Let the programmer set a maximum for iterations

We can leave it as but let the programmer set a maximum iteration count.

Benefits

• It's easy to implement.
• Allows the programmer to either decide where the cutoff point is.
• Allows the programmer to decide not to use a maximum at all.
• Fast in best-case situations for A*.
• Potentially cuts out a lot of bad situations for A*.

  Drawbacks

• Programmers need to have an understanding of how A* works to set a reasonable limit.
• A* makes assumptions which may be wrong (aggravating the user).
• Will be janky on high-complexity graphs.

Strictly enforce that there are no Islands

Make sure there are no Islands on a single graph at runtime

Benefits

• The programmer has to decide how to handle islands and connections.
• Fast in best-case situations for A*.
• A* never has to handle worst-case situations.

  Drawbacks

• The programmer has to decide how to handle islands and connections.
• Performance hit each time we validate the graph.
• Complicated to implement (we have to figure out if there are any islands).
• Makes A* more restrictive.

Other possible solutions

• Search for the path from the start and end point either in parallel or alternating (solves issues with small islands)
• Expose a search enumerable (might be referred to as Iterator in Rust) for A* that lets the programmer solve the problem.
• Instead of returning a partial path after max iterations, stop and use a different algorithm to check for connections.
• Any other complex solution

[mrDIMAS]

Got it! I think for now configurable iterations count is ok. It is worth to document it though, to not confuse users.

[TiltedTeapot]

Got it! I think for now configurable iterations count is ok. It is worth to document it though, to not confuse users.

Sounds good I will implement that and I'll look into how easy it will be to expose an iterator as well

[TiltedTeapot]

Alright, that should have the required fixes, I will look into exposing an iterator now.

[TiltedTeapot]

Alright I hope that solves all the issues brought up in your review and more!