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

51–60 of 77 posts

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

#51

Post by Farer »

mrkeen wrote: post #24

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.

I haven’t watched the video yet, but I really like the title: “on slow computers.” I'll give you feedback again after I watch it. The document you mentioned also seems to have a lot to learn from.

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

#52

Post by Farer »

deathanatos wrote: post #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 ar…

@deathanatos

Yes, as you mentioned, the idea of "it doesn’t have to be the optimal path" aligns perfectly with my thinking as well.

In the case of the algorithm I’m currently working on, it wouldn’t enter those concave areas directly. Instead, it would "look" at the obstacle first, recognize that the path is blocked, and then proceed toward one of the corners at the bottom or top of the concave shape. Afterward, it should be able to exit again using the same approach.

However, to make it behave more like a creature with vision in certain situations, it might be good to enhance the algorithm slightly so that it can preemptively recognize "Ah, this is a concave obstacle." That way, it could avoid inefficient behavior while still maintaining its "realistic" navigation style.

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

#53

Post by Farer »

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…

@wormlord

Yes, as you mentioned, the fact that "it’s not guaranteed to always find a solution" is perfectly fine for me. That’s because it feels more natural.

Moreover, since my goal isn’t to always find an answer in the shortest time, this approach aligns even better with my intentions. In my case, I’d like to handle aspects like "trial and error" as part of the learning concept for entities such as rabbits or wolves.

And of course, I’m aiming for something that works well in *dynamic situations*, not just static ones.

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

#54

Post by Farer »

Tossrock wrote: post #14

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

Oh! This seems like something even AIs haven’t suggested before. The fact that it attempts paths in real-time without preprocessing is what I like the most! I definitely need to research this further! I’ll definitely take a look at it. Thank you!

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

#55

Post by Farer »

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…

Oh~ This is definitely worth referencing as well. Thank you for the information!

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

#56

Post by malux85 »

Farer wrote: post #50
malux85 wrote: post #9

Earlier quoted context omitted.

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!

It would be great if it could be applied universally, but it seems that accommodating all situations in the real world won’t be easy. In the end, I feel like it might have to transition into the realm of inference, much like AI that mimics human reasoning.

This has been done, many times before, it turns out the neural network just learns a crapper version of A*, and of course, any domain knowledge from whatever environment it's in, there was a post on this very thing last year on hacker news.

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

#57

Post by Farer »

zbs1970 wrote: post #39

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…

Wow~ You’re one of the developers of Ultima, a game I truly loved! The concept of using "highways" is really fascinating!

However, in my project, everything is in plain view for everyone to observe, so I won’t be able to use any cheats like that!

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

#59

Post by Farer »

MrHuggs wrote: post #36

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

Oh, as expected, A* couldn't be fully utilized on older hardware. I can totally relate, as I’m running my server on a Mini PC with an *N100 CPU* right now.

Hearing stories about the challenges and solutions for low-spec hardware like this is incredibly fascinating.

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

#60

Post by Farer »

zamalek wrote: post #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 us…

Yes, I’m also trying to explore as many options as possible. However, I do have a strong desire to minimize preprocessing as much as I can.
Post reply on HN