4 ms·
Fast, Optimal, Any-Angle Pathfinding (Polyanya)
- Jumziey 4y agoThis 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 ^^
- krazii 4y agoHere is a visualisation of the algorithm I made a while back. https://m.youtube.com/watch?v=pJCNh5qsIuE https://m.youtube.com/watch?v=pJCNh5qsIuE
- SturgeonsLaw 4y agoThat's interesting, to me it looks like it mimics the eyes sweeping left to right, searching for the best option
- krazii 4y agoAn 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.
- stefs 4y agoi 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?
- krazii 4y agoI think so. As long as you can calculate your cost based on any two points that have a straight line path between them.
- tuukkah 4y agoGreat 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/ 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/anyangle/polyanya/ https://bitbucket.org/dharabor/pathfinding/src/master/anyang... A Rust crate: https://crates.io/crates/polyanya https://crates.io/crates/polyanya
- krazii 4y agoI 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.