Hacker News Reader

Comment by wormlord | Hacker News Reader

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.

View on HN

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.

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

You would still be choosing a node with the best f-value, so you'll get optimal solutions with any admissible heuristic. In a 2D-grid your heuristic should also be consistent, which will result in pretty good behaviour.

I don't think we're disagreeing

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

Reply on news.ycombinator.com