Ask HN: Have you ever seen a pathfinding algorithm of this type?
blog.breathingworld.com
Ask HN: Have you ever seen a pathfinding algorithm of this type?
1–10 of 77 posts
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#2[deleted]
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#3It seems that the A* algorithm is not delivering the performance I was hoping for, so I am trying a new approach.
Are there any existing cases, by any chance?
If not, I would like to hear your thoughts on this approach.
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#4Is this faster than A*?
I think that the problem with A* is that it use a mix of horizontal and vertical and 45° lines, but your proposal makes more natural straigh lines. I think it's more nice, but don't think it's more efficient (but I don't have a hard proof).
PS: The guidelines ask to use the original title. https://news.ycombinator.com/newsguidelines.html
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#5Is this faster than A*? I think that the problem with A* is that it use a mix of horizontal and vertical and 45° lines, but your proposal makes more natural straigh lines. I think it's more nice, but don't think it's more efficient (but I don't have a hard proof). PS: The guidelines ask to use the original title. https://news.ycombinator.com/newsguidelines.html
Since I recently felt the limitations of the A* algorithm in my LIVE project, I am planning to proceed with this attempt.
As a result of discussing with many AIs, it was difficult to find existing cases.
As far as I have reviewed extensively, I have come to the conclusion that the A* algorithm also involves a lot of unnecessary computations, so I am trying to minimize such computations themselves.
Since I am continuously running the service in LIVE, I believe I will be able to thoroughly verify its performance.
For reference, the current LIVE service is utilizing a Mini PC equipped with an N100 CPU.
This is also an attempt to achieve performance based on minimal specifications.
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#6It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#7can you specify the algorithm in more detail?
this looks to be solving a different problem than A*, which operates over discrete graphs. this looks to be operating in 2D continuous space instead.
so, what is the algorithm for finding the optimal point on the obstacle's outline for bypass (4)? is it finding the point on the outline nearest the destination?
then, how do you subsequently "backtrack" to a different bypass point on the obstacle if the first choice of bypass point doesn't work out?
there's something interesting here for trying to directly operate on 2D space rather than discretizing it into a graph, but I'm curious how the details shake out.
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#8Yes I have, I did something similar for a project naviagting in a space game.
This is still technically A* if you squint. The straight line is like using a eulicdean heuristic. The "optimal point" is just an abstracted way of navigating around obstacles.
The main thing you lose is that your path is no longer guaranteed to be optimal or guaranteed to be found if a solution exists. This was a problem I encountered, but I was trying to pathfind in a dynamic environment.
If your environment is static, you're better off just doing a pre-processing step where you divide your world into chunks of terrain. Maybe by using a flood fill algorithm and breaking off chunks when they reach the size of 100 tiles. Then you can maintain a graph that tells you if you can traverse from one chunk to another.
Your pathfinding over large distances would consist of an A* search on the graph of pre-computed chunks, and another A* search from your current chunk->next chunk.
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#9It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.
I was thinking this too, A* is a good general performance algorithm, it’s possible the poster found an algorithm that performs better on their use case, but doesn’t generalise as well as A*, custom path finding algorithms that take advantage of domain knowledge are pretty common!
Re: Ask HN: Have you ever seen a pathfinding algorithm of this type?
#10I wrote a similar algorithm for pathfinding around vector shapes in Javascript, the implementation was surprisingly simple.