Implementations of Obstacle Avoidance Algorithms

Question

Programming

Who in the know tell me:

1. what are the best algorithms for avoiding obstacles now? (names are of interest)
2. When evaluating “best”, we take into account the speed of calculation, work in three-dimensionality, taking into account a three-dimensional body that moves (i.e., so that bypassing an obstacle would not decide to climb like Winnie the Pooh into a hole into which it cannot crawl, and so so that he doesn’t invent to build such a path in principle, i.e. so that after passing 100 steps, it doesn’t turn out that the 101st turned out to be narrow, and again you need to return to step 1), complex volumetric obstacles. And it is also important that the space does not have to be divided into equal cubes, and the path would be built according to the minimum number of reference points. Those. the option to go to square 1, and then to the square on the right, three squares straight ahead is not good.
3. Ready-made implementations are of interest. Those. without open source is not interesting.

Answer 1

The algorithms are the same as many years ago - waypoints and pathfinding algorithms .

Answer 2

The Navigation Mesh algorithm you found is perhaps the best option at the moment. It, for example, is used by the Unreal Engine .
You can also look at the AA*, HPA*, HAA* algorithms, they take into account the size of the object. There was an article recently .

Answer 3

I'll answer myself, who tried recast - code.google.com/p/recastnavigation/ ? It looks like what you need...