ANYA and POLYANYA are still potentially some of the best pathfinding algorithms for games, and yet they go largely unused and unnoticed . . . you guys should make some demos or examples with them! Also have you ever tried tackling the problem of pathfinding in a platformer / situation with gravity? There are lots of supposed "solutions" to this out on the internet, but the subject is still surprisingly underdeveloped / not studied enough in game dev in particular.
i am interested however I am developing using RL and results are already spectacular and will work with "online" worlds as well, by definition, RL run time doesnt care about which world is it in. Anyway, nice presentation on ANYA and POLYANYA
Hi, Thanks for your question! Only Anya searches over a grid. Polyanya searches over a navigation mesh. If you have a grid-based representation, it's easy to construct a mesh and doing so usually gives substantial performance benefits. Conventional methods for searching navigation meshes place graph nodes in the middle of polygon faces, or along polygon edges. These graphs are small, fast to update, and fast to search but they do not produce Euclidean-optimal solutions; it's easy infact to construct examples with substantial detours. But is this method faster than Polyanya? That probably depends on the implementation, but I expect similar performance in general. This is because Polyanya expands few intervals from along a given polygon edge, similar to nav-mesh approaches. It may even be faster because we perform aggressive pruning. We never ran the experiments because the comparison is apples-to-oranges (optimal vs. non-optimal) and because the baseline (Anya) was already shown to be competitive with preprocessing-based suboptimal solvers. Visibility graphs are another type of navigation graph. These require substantial offline preprocessing but they guarantee solutions which are Euclidean-optimal. Once constructed, visibility graphs are usually fast to search. I say usually because again it's easy to construct examples where visibility graphs are very dense, which is bad for search performance. Under favourable conditions, I think visibility graphs might be competitive, in terms of speed, with Polyanya. But they have so many disadvantages which makes this approach difficult to recommend (expensive preprocessing, large storage costs, relatively expensive start-target insertions, branching factor explosion).
Wow, that's genius. Really difficult subject to solve
ANYA and POLYANYA are still potentially some of the best pathfinding algorithms for games, and yet they go largely unused and unnoticed . . . you guys should make some demos or examples with them!
Also have you ever tried tackling the problem of pathfinding in a platformer / situation with gravity? There are lots of supposed "solutions" to this out on the internet, but the subject is still surprisingly underdeveloped / not studied enough in game dev in particular.
This dude is a genius, game studios take notes
Super cool algorithm
Thank you for sharing your wonderful research!
Very cool! Thanks!
i am interested however I am developing using RL and results are already spectacular and will work with "online" worlds as well, by definition, RL run time doesnt care about which world is it in. Anyway, nice presentation on ANYA and POLYANYA
Oh I have to play with this!
That's interesting, but think I'll stick with navmeshes and theta* for now.
How do Anna and Polyanna compare to A* with a navigation graph instead of a grid?
Hi,
Thanks for your question!
Only Anya searches over a grid. Polyanya searches over a navigation mesh. If you have a grid-based representation, it's easy to construct a mesh and doing so usually gives substantial performance benefits.
Conventional methods for searching navigation meshes place graph nodes in the middle of polygon faces, or along polygon edges. These graphs are small, fast to update, and fast to search but they do not produce Euclidean-optimal solutions; it's easy infact to construct examples with substantial detours. But is this method faster than Polyanya? That probably depends on the implementation, but I expect similar performance in general. This is because Polyanya expands few intervals from along a given polygon edge, similar to nav-mesh approaches. It may even be faster because we perform aggressive pruning. We never ran the experiments because the comparison is apples-to-oranges (optimal vs. non-optimal) and because the baseline (Anya) was already shown to be competitive with preprocessing-based suboptimal solvers.
Visibility graphs are another type of navigation graph. These require substantial offline preprocessing but they guarantee solutions which are Euclidean-optimal. Once constructed, visibility graphs are usually fast to search. I say usually because again it's easy to construct examples where visibility graphs are very dense, which is bad for search performance. Under favourable conditions, I think visibility graphs might be competitive, in terms of speed, with Polyanya. But they have so many disadvantages which makes this approach difficult to recommend (expensive preprocessing, large storage costs, relatively expensive start-target insertions, branching factor explosion).