3 ms·

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 eul

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 2y ago
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 https://en.wikipedia.org/wiki/Visibility_graph
- dietr1ch 2y ago
  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.
  - jvanderbot 2y ago
    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.
    - dietr1ch 2y ago
      > 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.
      - jvanderbot 2y ago
        I don't think we're disagreeing
Farer 2y ago
@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.

jvanderbot 2y ago

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 https://en.wikipedia.org/wiki/Visibility_graph

dietr1ch 2y ago
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.
- jvanderbot 2y ago
  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.
  - dietr1ch 2y ago
    > 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.
    - jvanderbot 2y ago
      I don't think we're disagreeing

Farer 2y ago

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