Fast, Optimal, Any-Angle Pathfinding (Polyanya)

research.monash.edu

76 points·krazii··8 comments

Great algorithm! The paper is from 2017. Anyone using this so far?

Slides of a tutorial by the original author: https://harabor.net/daniel/index.php/2019/03/20/gdc-2019/

Here's the original implementation in C++: https://bitbucket.org/dharabor/pathfinding/src/master/anyang...

A Rust crate: https://crates.io/crates/polyanya

I implemented it for the path finding of zombies in my game. However, it was a little overkill for what were supposed to be brain dead zombies so I have since gone with something simpler and less optimal.

Here is a visualisation of the algorithm I made a while back. https://m.youtube.com/watch?v=pJCNh5qsIuE

That's interesting, to me it looks like it mimics the eyes sweeping left to right, searching for the best option

An analogy with vision is definitely appropriate. From each node in the path you you push forward to the visible neighbor nodes. The efficiency of the algorithm comes from exploring the space polygon to polygon.

i admit to being too lazy to read the paper, so maybe you can answer this: does this work on weighted graphs too? by that i mean what if movement costs differ from distance?

I think so. As long as you can calculate your cost based on any two points that have a straight line path between them.

This is a great paper, did my master thesis on adapting in to autonomously navigating large bodies of water with a boat/ship or similar. For which it worked great!

It's almost weird it haven't gotten more attention yet! Awesome post ^^

Reply on news.ycombinator.com