Ask HN: Have you ever seen a pathfinding algorithm of this type?

You're referring to the "Convex Hull". And if you are inside a shape, drawing edges to the visibile vertices of the shape (until you're on the boundary of the convex hull) will easily get you a path out, and, bonus, will eventually draw a perfect shortest path to the end.

See: https://news.ycombinator.com/item?id=42608107#42626311

The blog post is lacking critical details stating what exactly the problem definition is. But making some assumptions, I believe the objective is to find a decently short path using less computation time than A*, rather than to specifically find the shortest path.

I will direct the author to any number of references in the field of robotic motion planning. These are algorithms designed to deal with continuous spaces, which is the limiting case of the author's problem with too fine grained a resolution in the A* search graph.

Checking the textbook on my shelf, Principles of Robot Motion (2005), I find an algorithm called "Tangent Bug" within the first 30 pages, which is similar in spirit to the author's proposed approach. The textbook goes on for 500 more pages to develop a host of more sophisticated techniques, including "sampling-based planning," which the author may find extremely useful.

Edit: Just recalled this excellent blog post of Casey Muratori on using one of the sampling algorithms, "RRT", for The Witness: https://caseymuratori.com/blog_0005

It would do just fine - but that's because OP is essentially grabbing on the intuition behind Visibility Graph search, which is (or was) a very common path planning algorithm using just obstacle boundaries.

The algorithm in a maze would just use "intersections" as successors, rather than "Next next step down the hall".

This is, in fact, an optimal search algorithm for this problem, and scales much better than any grid search in this case.

The difficulty has always been in how many things you look at. Tiles or objects. With static maps you can quite easily structure things so that you don't have to look at very much at all. When things are dynamic tests such as 'look at the thing in the way' suddenly get harder because you have to determine for any given point A) is something in the way? and B) what is it?

The simplest and most memory hungry thing would be to have a tile map where every tile has a precalculated map on the direction to go to reach every other tile. If you used that as a basis for optimisation you can rapidly improve, for instance an easy first step is to not store any direction data for areas where the path in a straight line is optimal.

Optimize more and you can reduce the scale of data and compute required to calculate the map you can eventually calculate the map quicker and often for only the start and end points you care about. Follow those optimisations far enough and you end up with many of the algorithms used today.

If you have a lot of things moving in a dense area, often the optimal is to maintain a bitmap of 'Something is here' making presence detection trivial.

If you then do a 8 passes over that bitmap for each direction you can go (for square tiles) you can create 8 further maps with a count recording when that pass last saw an obstruction. That lets you implement a very fast jump point search where instead of scanning tile by tile you can jump to the next obstruction in order to either find the way around or find the dead end.

I think the algorithm mentioned in the article is essentially a jump point search but not going into how the "select the optimal point for bypassing the obstacle" is done. Again this comes back to static/dymamic and how to determine that point. If using object outlines, can objects scale or rotate? You could probably do a reasonable version of jump point with convex hulls around objects and simple fast-out distance functions. A single object system would have difficulty dealing when multiple objects have overlapping bounds though. Two S shaped objects that are overlapping in their bounds might have a path possible through them but it is likely to not involve the optimal passing point of each individual shape alone is not on the path between them.

So the ideal is different for static/dynamic, dense/sparse, or memory availability, but all of those factors come back to how they influence how you decide what to look at and how to ignore irrelevant information.

So far, no one has mentioned "Bug Algorithms", which have a similar structure of (1) walk in the direction of the goal, (2) walk around obstacles as they are encountered, (3) leave the obstacle to proceed when some condition is met. They are very simple to implement (though not optimal) and there are a number of variants to play around with. Howie Choset has some good lecture slides that describe them [1]. However, as some others have mentioned, something like Jump Point Search [2] is likely a better option given the described scenario.

[1] https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg... [2] https://en.wikipedia.org/wiki/Jump_point_search