[HN Gopher] Ask HN: Have you ever seen a pathfinding algorithm o...
___________________________________________________________________
Ask HN: Have you ever seen a pathfinding algorithm of this type?
Author : Farer
Score : 35 points
Date : 2025-01-06 06:01 UTC (1 days ago)
(HTM) web link (blog.breathingworld.com)
(TXT) w3m dump (blog.breathingworld.com)
| Farer wrote:
| 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.
| gus_massa wrote:
| Is this faster than A*?
|
| I think that the problem with A* is that it use a mix of
| horizontal and vertical and 45deg 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
| Farer wrote:
| 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.
| johnfn wrote:
| 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.
| malux85 wrote:
| 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!
| jvanderbot wrote:
| 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.
| Lerc wrote:
| 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.
| sujayakar wrote:
| 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.
| wormlord wrote:
| 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.
| jvanderbot wrote:
| This can be improved on using visibility graphs. In that case,
| the complexity is only determined by the number of obstacles.
| https://en.wikipedia.org/wiki/Visibility_graph
| wazzaps wrote:
| I wrote a similar algorithm for pathfinding around vector shapes
| in Javascript, the implementation was surprisingly simple.
|
| https://github.com/Wazzaps/FastPathfinder
| setr wrote:
| 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
| deathanatos wrote:
| > _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.)
| juancn wrote:
| 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.
| jvanderbot wrote:
| 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
| philsnow wrote:
| Imagine a maze or labyrinth, with the agent and the
| destination both inside of it. Is it useful to try to
| figure out the convex hull of the walls, even if it is
| effectively "the entire maze"?
|
| The agents in the article seem to mostly be finding their
| way around sparsely-distributed, discrete obstacles, so I
| can see how the "raycasting" approach described would work
| well, but in a sufficiently obstructed environment like a
| maze, something like (double-ended) A* is going to both be
| simpler and likely perform better.
| fizzynut wrote:
| You should probably just use a quad tree to put your objects into
| and traverse that with a path finding algorithm.
| Tossrock wrote:
| 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
| gpm wrote:
| And for non-grids (arbitrary constant cost 2d meshes) you can
| use polyanya.
| zamalek wrote:
| 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.
| jvanderbot wrote:
| 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!
| bee_rider wrote:
| Is there a nice way to handle the idea that a creature might
| have a better or worse memory or ability to build a model of
| the environment? That seems like it would be an interesting
| dimension to add to a creature.
| jvanderbot wrote:
| Sure, if you held a deadline to my head and told me to do it,
| I'd just include obstacles that are "within their memory".
|
| Expire them by time, refresh them by range (can see as they
| move). Constantly replan and I bet you'd get something
| reasonable looking, but _only_ if you add an obstacle that
| represents only what the creature can see. If you add the
| whole obstacle (regardless of what it can see), it'll just do
| the optimal thing, which is fine but may not "look right". So
| clip visibility with obstacle, add that, and union it with
| all known obstacles, then replan. Keep it fast by doing a
| union "in place" with known obstacles so your obstacle list
| doesn't grow unbounded.
|
| You can imagine it would walk toward the goal until it sees a
| wall, then it would go either left or right for a step, then
| back for two steps, then left for 4 steps, then back for 8
| ... because the A* "frontier" keeps expanding so it keeps
| searching along that frontier.
|
| And if you're lucky, you just discovered the optimal search
| variant of the "Drunkards walk" search problem.
| bee_rider wrote:
| The ability to reason about obstacles that you can't see
| could be an interesting feature to add for a human-
| equivalent creature, although I guess it will be a real
| mess to simulate something as smart as a person, haha. But
| for example, if you know what a house looks like, you can
| probably speculate about where obstacles might be,
| depending on parts of the roofline that you can see. And
| might be wrong. _And_ your odds of being wrong might be
| influenced by your familiarity with some region's
| architectural conventions.
| jvanderbot wrote:
| Yeah, that's an interesting problem.
|
| I've worked in planning for a bit, mostly for robotics. I
| can honestly say that the _planning_ side of making
| interesting behaviors is really simple. It's the world
| representation that is hard. In the real world it's hard
| to build up a _good enough_ representation to do smart
| things. Most robots can 't reasonably see longer than 50
| yards/100 yards. In games is hard to build up a _bad
| enough_ representation to match the partial information
| in the real world - running just about any planner on the
| map will _just work_ and probably look too good.
| stonemetal12 wrote:
| 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.
| jvanderbot wrote:
| This is a visibility graph search. You can use the convex hull
| of any obstacle.
| cvoss wrote:
| 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
| mrkeen wrote:
| 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.
| Vvector wrote:
| IMO, sounds like you want A* with JPS
| https://en.wikipedia.org/wiki/Jump_point_search
| gjstein wrote:
| 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
___________________________________________________________________
(page generated 2025-01-07 23:01 UTC)