Live data from Hacker News

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

blog.breathingworld.com

11–20 of 77 posts

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

#11
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

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

#12
> 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.)

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

#15
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.

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

#16

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

And for non-grids (arbitrary constant cost 2d meshes) you can use polyanya.

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

#17

> 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 ar…

Unless the "outline" is like tensing a rubber band around the object. In that case, the collision would happen outside the convex part.

Anyway, the details are not enough for me to fully grasp the algo described.

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

#18
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!

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

#19
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.

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

#20

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 q…

This is a visibility graph search. You can use the convex hull of any obstacle.
Post reply on HN