Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.breathingworld.com

Post reply on HN
Print view View original

31–40 of 77 posts

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

#31

Post by bee_rider »

jvanderbot wrote: post #30
bee_rider wrote: post #28

Earlier quoted context omitted.

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.

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

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.

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

#32

Post by jvanderbot »

bee_rider wrote: post #31
jvanderbot wrote: post #30

Earlier quoted context omitted.

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

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

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.

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

#33

Post by philsnow »

jvanderbot wrote: post #21
juancn wrote: post #17

Earlier quoted context omitted.

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.

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

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.

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

#34

Post by jvanderbot »

philsnow wrote: post #33
jvanderbot wrote: post #21

Earlier quoted context omitted.

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

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

You can path-find using only vertices and a can-see function to generate a-star successors.

The convex hull is just where the paths will go if it has to go around an obstacle.

So if your maze is specified as obstacles take the vertices. If your maze is specified some other way it depends how expensive it is to translate it.

What you're suggesting is fine and well and good, but it will in an asymptotic analysis do more work than double ended a* that only expands successors for intersections.

Think about all the iterations where the expanded state is just one more grid cell closer to the end of the hall, vs just jumping to the end of the hall. If you limit to counting only iterations, a geometric approach is faster (vs grid).

That may not be the best way to do it in practice. It's also way harder to implement because let's face it everything is a grid.

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

#35

Post by dietr1ch »

gus_massa wrote: post #4

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

A* searches on a generic weighted graph, there's no vertical, horizontal nor diagonal movements. The only thing that matters is which nodes exists and how they are connected.

If diagonals on a 2D-grid are forbidden, then you need to use the Manhattan distance as the heuristic.

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

#36

Post by MrHuggs »

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.

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

#37

Post by dietr1ch »

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

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

#38

Post by dietr1ch »

jvanderbot wrote: post #22
wormlord wrote: post #8

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…

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

I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely closer to the goal.

If you look at runs, this tie breaking makes A* behave like a greedy algorithm in the absence of obstacles and simply follow a straight path if there's one, and act sort of cleverly when there's a small detour.

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

#39

Post by zbs1970 »

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.

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

#40

Post by jvanderbot »

dietr1ch wrote: post #38
jvanderbot wrote: post #22

Earlier quoted context omitted.

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

I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely closer to the goal. If you look at runs, this tie breaking makes A* behave like a greedy algorithm in the absence of obstacles and simply follow a straight path if there's one, and act sort of cleverly when there's a small detour.

On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths.

The idea goes: Best to just search in that space vs iterating over some other space attempting to indirectly coax out the optimal path. The bonus is that VG-based search is very fast b/c it doesn't search over anything but those. It's just everyone already has grids so they probably just would rather use that.

That's all I'm claiming. That, and TFA is basically the same as VG-based search. So, yeah, there are infinite ways to find paths, some optimal some not, some doing more work, some doing less. They'll all probably be fine but not all come with books of guarantees. OP has done a good job to intuit an optimal algorithm with fantastic performance guarantees in this setting.

Post reply on HN