Have you ever seen a pathfinding algorithm of this type?

You're referring to a visibility graph.

https://en.wikipedia.org/wiki/Visibility_graph

On a visibility graph you can run any search algorithm. The key thing is this graph is sparse (the number of nodes is really limited by the amount and complexity of the obstacles, not the distances).

This algorithm follows almost perfectly your outlined steps. In particular it draws a line to the destination, and if it encounters an obstacle it "walks" paths (generates successors for A*) along the exterior of an obstacle until it can "See" (draw a straight line to) the destination or another obstacle. By using "obstacle free distance to destination" as a heuristic at each node, this will provide optimal paths.

You can, just from the wikipedia page, deduce a good response to the problem of "select the optimal point for bypassing the obstacle". (Maybe try the vertices of the convex hull / AABB - and don't worry, it may take a few iterations to truly wrap around an obstacle)

This will perform much, much better on sparse environments than a grid, because a grid has to iterate O(n) for n grid cells, while a visibility graph has to iterate O(n) for n obstacles (of a given complexity).

Very nice!

The core optimization you're trying sounds fairly similar to JPA*, which I believe is fantastic on open maps but eh on dense ones.[0]

Maybe take a look at HPA* (hierarchal A* - partition the map, pathfind on high-level map, then pathfind at lower granularity).

You can also encode into the hierarchy information about whether a rabbit exists in the chunk in the first place, to reduce the initial search for nearest-rabbit.

Factorio had a good blog post on it [1], and Rimworld too but it also enabled arbitrary-sized partitions. [2]

I'm kind of just guessing based on your basic description though; what's the full scenario in mind?

[0] http://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JPS...

[1] https://factorio.com/blog/post/fff-317

[2] https://www.youtube.com/watch?v=RMBQn_sg7DA

It 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.

Have a look at:

   Simon Peyton Jones on Getting from A to B fast route finding on slow computers [PWL London]
   https://www.youtube.com/watch?v=L1XDdy-hOH8

It goes from 0 all the way up to A*, then beyond. I think the new stuff is based on https://www.cs.tau.ac.il/~haimk/papers/sp-wea.pdf but I'm not sure since the paper isn't explicitly named in the video.

- Run A* on the optimistic pathfinding graph (no obstacles on the unknown cells).

- Follow the path found (if there's none, that's it)

- As you follow the path, sense the world and take note of new obstacles.

- If there's an action you can't make because of a new obstacle, re-run A.

There's ways of re-using the state from previous A runs (as long as the goal is still the same) that becomes handy on complex maps where the path you wanted to follow is blocked deeply.

BTW, if you tie-break nodes on lower heuristic value (h-value), then you'll be more likely to search deeper paths, which makes optimizations like trying to follow a straight line kind of useless, but as always, run benchmarks before guessing.

Also, if you have a tight deadlines for the search algorithm, like having to make another tick on the game happen, there's some real-time variants of A* that have a bound for how many nodes A* can expand on each run. I don't think you'll need real-time A* though, I remember that this approach using Dijkstra was fast enough for a project back in Uni on now 15yo hardware, so newer hardware using A* must be good enough ever for large graphs.

> Among the outline information, select the optimal point for bypassing the obstacle. (This part is the core)

Core … and a bit too vague. I'd be curious what happens to it if you run into a concave object. Image running into the back curve of a crescent, or, since diagonals are not legal moves,

       XXXXX
     XXX   X
           X
           X
 S - - >   X    E
           X
           X
     XXX   X
       XXXXX

Once you're inside such a shape, following the outline is not the optimal way around it (you'd waste time in the little alcoves at the top & bottom, and I could make those alcoves considerably more pathological, too). You'd want to head for one of the opening's corners.

Of course, the optimal path S → E avoids walking into that entirely.

Since it seems to be a game, though, the other consideration is "should the entity use optimal pathfinding?" Confounding an opponent with an odd shape could be just called "gameplay". (Different opponents might even have different levels of intelligence, and thus, different pathfinding. Some 2D games I have played have this exact mechanic.)

Yes 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.

It sounds like you're looking for Any Angle pathfinding. The fastest known algorithm for 2D grids is ANYA: https://ojs.aaai.org/index.php/ICAPS/article/view/13609

Hey there, it is a little bit ambiguous what you mean by "find an algorithm that performs better". Do you mean in terms of runtime, or in the "quality" of the path?

Sooner or later, someone will link to Amit's pages, so it may as well be me :-). Since you are talking about ray casting, perhaps your "performance" question is about the shape/quality of the path. From Amit's: "The most common question I get when people run pathfinding on a grid is why don’t my paths look straight?" [0]

I also recall a video by the 8-Bit Guy [1] where he discussed his pathfinding hacks for Planet X16. Due to hardware limitations, he had to get creative with his path finding. Probably not super-relevant to your project, both could be fun/inspiring in the sense of finding a less traditional way of doing things that really fits your project needs.

--

0: https://www.redblobgames.com/pathfinding/a-star/implementati...

1: https://youtu.be/HP4ObKlCe6w?feature=shared&t=360

I think this part also needs to be considered. Many pathfinding algorithms, including A* , aim to find the optimal path. However, my goal started with replicating how humans visually find their way.

In such cases, humans cannot see the back side of obstacles. Additionally, there are situations where the exact destination may not be known. They simply infer based on what they can see in front of them. "There's an obstacle over there. Which way would be better to go around?" My approach began from this perspective.

This flow of pathfinding is entirely different from A*. So, the algorithm has been modified a bit now. I changed it so that it does not investigate the entire shape or full outline of obstacles. The flow is as follows:

1. Attempt to move in a straight line in the direction I want to go. 2. Detect an obstacle. 3. Explore the visible outline of the obstacle, focusing on the side that seems closer to the destination. 4. When reaching the endpoint of the outline, select an appropriate detour point nearby.

The final detour point will, of course, be a location where a straight-line movement from the starting point avoids hitting the obstacle. Once I reach the detour point from the starting point, I repeat the process.

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

We used this algorithm in the RTS Outpost 2 in 1997. I think the original Command and Conquer did something similar.

Given the hardware of the time and the (relatively) large maps, we couldn't just use A.

Fun fact: There was a building called the "Robot Command Center." If you had one, path finding was upgraded by first running this method, and then running A constrained to some distance from the initial path. The result was a more efficient path that removed silly bits of backtracking and so forth. I've not seen another RTS where there was an upgrade that affected path finding.

In addition to the other options posted here, you can do what 3D games do: they have polygons covering all navigable areas. You then find which polygons connect source to destination, then create lines/curves across them (you never have to path find within an area because other don't contain obstacles). The harder problem is creating these maps, but there are quite a few solutions to that (e.g. voronoi). You could use a quadtree, and your navigation graph would consist of the set of the deepest nodes.

Your current solution seems like it could be a minefield of edge cases.

IMO, sounds like you want A* with JPS https://en.wikipedia.org/wiki/Jump_point_search

Very similar to the pathfinder I wrote for Ultima in 1990. At the time I was too young and naive to know that there were lots of existing similar graph algorithms (this was before the internet and, more importantly, I was 20 years old and therefore already knew everything LOL).

One nice thing we added to those "large" game worlds back then was to pre-compute "highway" routes and then path-find at run-time to a nearby "on-ramp" to save time. Also, we cheated by teleporting NPCs when no-one was looking.

Is 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

Step 4 is going to be tough. How do you handle concave obstacles?

The article mentions wolves and rabbits, what if a rabbit is in a cave. That is to say the obstacle you need to waypoint around is in fact something you need to go inside of. The wrong waypoints to navigate around the obstacle becomes circle the obstacle indefinitely.

I would probably go with a hierarchical A* that way you can get the high level path quickly and do the local fine grain pathfinding in small chunks as you go.

It seems to be almost completed. Would you like to finish it together?

We are now at the final stage. When looking for a detour in the direction blocked by the map boundary and failing to find one, the program attempts exploration on the opposite side. It's getting very close to being complete.

https://github.com/Farer/bw_path_finding

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

I wrote a similar algorithm for pathfinding around vector shapes in Javascript, the implementation was surprisingly simple.

https://github.com/Wazzaps/FastPathfinder

can 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.

It 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.

You should probably just use a quad tree to put your objects into and traverse that with a path finding algorithm.