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

61–70 of 77 posts

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

#61

Post by Farer »

stonemetal12 wrote: post #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 q…

Thank you so much for providing an example related to the project!

The example you mentioned might need to be delegated to the wolf’s *lifestyle logic*. For more thoughts on this, it would be great if you could check out the link below: https://blog.breathingworld.com/concept-meeting-for-wolf-dev...

In conclusion, the wolf will, of course, have intelligence and will also possess skills for hunting. With those capabilities, the wolf will likely be able to track the traces left by the rabbit and ultimately find it.

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

#62

Post by emmanueloga_ »

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

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

#63

Post by Farer »

cvoss wrote: post #23

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

Oh! That’s exactly correct! It seems I didn’t explain it clearly enough.

As you mentioned, *"the goal is to find a decently short path, not necessarily the shortest one."* That’s absolutely right. The basic idea is that when an obstacle is encountered, *I just need to find the first detour point.* After that, the process can be repeated from that detour point in the same way.

The link you provided is also very intriguing. I’ll take a closer look and provide feedback again afterward!

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

#64

Post by Farer »

wazzaps wrote: post #10

I wrote a similar algorithm for pathfinding around vector shapes in Javascript, the implementation was surprisingly simple. https://github.com/Wazzaps/FastPathfinder

Oh~ That’s awesome! I’ll start analyzing the source code! Thank you!

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

#65

Post by Farer »

sujayakar wrote: post #7

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

The algorithm for finding detour points is as follows. In fact, I’ve improved it a bit through research:

1. Detect a collision with an obstacle on the straight path connecting the starting point and the destination. 2. Decide which direction to explore along the obstacle's outline (for now, the side closer to the destination). 3. If the end of the visible outline is reached, search for an appropriate detour point around that outline. 4. Select a detour point where a straight-line movement from the starting point avoids the obstacle, preferably closer to the destination.

---

If the first detour point selection fails, I plan to search in the *opposite direction* along the outline where the obstacle was first encountered. I’m currently working on resolving this part.

You can check out my progress here: https://github.com/Farer/bw_path_finding

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

#67

Post by Animats »

gjstein wrote: post #29

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, a…

I've done that something like that.[1] It's appropriate where there's a significant cost to detecting obstacles, because it tests few unnecessary cells.

It heads to the goal until an obstacle is reached, then follows the wall. Unusually, it forks and follows both the left and right wall simultaneously. It's not always optimal, but the optimal algorithms such as A* have to test more cells.

This algorithm runs my NPCs in Second Life.

[1] https://github.com/John-Nagle/lslutils/blob/master/npc/obsol...

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

#68

Post by Farer »

emmanueloga_ wrote: post #62

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…

Oh, I saw that blog too. It helped me a lot to be inspired. What I mean by "performance" is that I want to minimize preprocessing, and I want to minimize the amount of computation I can do even when I'm navigating in real time. I'll definitely watch the video you gave me. Thank you!

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

#69

Post by Farer »

wazzaps wrote: post #10

I wrote a similar algorithm for pathfinding around vector shapes in Javascript, the implementation was surprisingly simple. https://github.com/Wazzaps/FastPathfinder

I’ve reviewed the source code. It seems like starting with clear and accurate information about the obstacles could be an issue. Also, if the obstacles become very large, preprocessing will likely be necessary.

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

#70

Post by jvanderbot »

Farer wrote: post #49
jvanderbot wrote: post #25

Earlier quoted context omitted.

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

I also hope it works as well as you’re thinking.

It's not my idea. There's a bunch of video tutorials on it if you want to google around.

And I actually have implemented this for some problems and it actually is as good as the theory says. The hard part is transforming from "Grid with 0/1 obstacles" to "sparse set of visible nodes". That's not trivial and can put the whole thing out of reach.

Post reply on HN