Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast, Optimal, Any-Angle Pathfinding (Polyanya)

research.monash.edu

Post reply on HN
Print view View original

1–9 of 9 posts

Re: Fast, Optimal, Any-Angle Pathfinding (Polyanya)

#4

Post by tuukkah »

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

Re: Fast, Optimal, Any-Angle Pathfinding (Polyanya)

#5

Post by krazii »

SturgeonsLaw wrote: post #3
krazii wrote: post #2

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.

Re: Fast, Optimal, Any-Angle Pathfinding (Polyanya)

#6

Post by krazii »

tuukkah wrote: post #4

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.

Re: Fast, Optimal, Any-Angle Pathfinding (Polyanya)

#7

Post by stefs »

krazii wrote: post #2

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

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?

Re: Fast, Optimal, Any-Angle Pathfinding (Polyanya)

#8

Post by krazii »

stefs wrote: post #7
krazii wrote: post #2

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

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.
Post reply on HN