There are no complicated labyrinths in the game world.These are continents, islands.The most difficult thing is the strait that needs to be circumvented.There are also separate obstacles - stones, trees that can be easily circumvented.the end of the continent.Need the fastest algorithm.
  • less than 20 years from
    Toward More Realistic Pathfinding
    – Clear Cod Aug 13 '18 at 17:00
  • Fast!=Optimal
    This is probably not about the speed of the algorithm, but about the shortest path.
    Therefore, I propose to optimize the title of the question.
    – Concerned44 Aug 13 '18 at 23:13
  • The path may not be the shortest.If only the search for the path was the fastest.

    In the case of an empty field without obstacles, in general, the “shortest”=“fastest”.Although, judging by tests, A * behaves not in the fastest way.
    – Mystery36 Aug 13 '18 at 23:39

6 Answers 6

https://qiao.github.io/PathFinding.js/visual/
  • Judging by the tests, the fastest Best-First-Search. – Mystery36 Aug 13 '18 at 18:18
Lazy Theta *
More link using the same algorithm.
  • Brilliant.
    This is the same A *, only beautiful.
    – Mystery36 Aug 14 '18 at 22:56
  • Mystery36, it's not at all the same A *.It makes the path shorter. – Concerned44 Aug 14 '18 at 22:56
My article on A *
I think this algorithm is the fastest(I do not know exactly the name of the algorithm, but the essence is as follows):
1.We write the equation of a straight line between the current coordinate of the object and the destination(www.math.by/geometry/eqline.html).
2.Moving along this line to the first obstacle
3.If you come across an obstacle, we begin to go around it, say, on the right.At each step, we check if we are on our line
4.If we are again on the straight line, and this is not the point from which we started the detour, we continue to go further along the straight line to the destination or the next obstacle.
5.If you find yourself again at the point from which you started the detour, or at one of the points on the line that is farther from the destination, which is the point from which you started the detour(i.e.turned back), then we try to bypass the obstacle on the left.
6.If here we returned to the point from which we started walking, then the desired destination point is unattainable.
What is the fastest pathfinding algorithm?

it does not exist.Everything depends on the input data, including: mesh size, size and density of obstacles, the need to smooth the path, static/dynamic obstacles, dimensions of the object itself(important/unimportant), fog of war(generally similar to dynamic obstacles, but not always), and a lot of factors.

Start with a-star, if it fits under the primary data.
All polls use A *, occasionally JPS.If the speed is not enough, then optimize the graph that is being searched for, for example, replace the uniform grid with key points.