3 ms·

It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it'

by johnfn 2y ago

It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.

malux85 2y ago
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!
- Farer 2y ago
  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.
  - malux85 2y ago
    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.
jvanderbot 2y ago
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 grid search in this case.
- Farer 2y ago
  I also hope it works as well as you’re thinking.
  - jvanderbot 2y ago
    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.
Lerc 2y ago
The difficulty has always been in how many things you look at. Tiles or objects. With static maps you can quite easily structure things so that you don't have to look at very much at all. When things are dynamic tests such as 'look at the thing in the way' suddenly get harder because you have to determine for any given point A) is something in the way? and B) what is it? The simplest and most memory hungry thing would be to have a tile map where every tile has a precalculated map on the direction to go to reach every other tile. If you used that as a basis for optimisation you can rapidly improve, for instance an easy first step is to not store any direction data for areas where the path in a straight line is optimal. Optimize more and you can reduce the scale of data and compute required to calculate the map you can eventually calculate the map quicker and often for only the start and end points you care about. Follow those optimisations far enough and you end up with many of the algorithms used today. If you have a lot of things moving in a dense area, often the optimal is to maintain a bitmap of 'Something is here' making presence detection trivial. If you then do a 8 passes over that bitmap for each direction you can go (for square tiles) you can create 8 further maps with a count recording when that pass last saw an obstruction. That lets you implement a very fast jump point search where instead of scanning tile by tile you can jump to the next obstruction in order to either find the way around or find the dead end. I think the algorithm mentioned in the article is essentially a jump point search but not going into how the "select the optimal point for bypassing the obstacle" is done. Again this comes back to static/dymamic and how to determine that point. If using object outlines, can objects scale or rotate? You could probably do a reasonable version of jump point with convex hulls around objects and simple fast-out distance functions. A single object system would have difficulty dealing when multiple objects have overlapping bounds though. Two S shaped objects that are overlapping in their bounds might have a path possible through them but it is likely to not involve the optimal passing point of each individual shape alone is not on the path between them. So the ideal is different for static/dynamic, dense/sparse, or memory availability, but all of those factors come back to how they influence how you decide what to look at and how to ignore irrelevant information.
Farer 2y ago
@johnfn The approach I’m considering would be similar to how humans navigate: using only visible information to continuously infer and find the way in real-time. It would essentially break down the flow of how humans navigate into small, incremental steps. Look with their eyes, make a judgment, move, and repeat the process again and again... Of course, trial and error could also occur. This might actually make it feel more natural.

by johnfn 2y ago

malux85 2y ago

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!

Farer 2y ago
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.
- malux85 2y ago
  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.

jvanderbot 2y ago

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 grid search in this case.

Farer 2y ago
I also hope it works as well as you’re thinking.
- jvanderbot 2y ago
  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.

Lerc 2y ago

The difficulty has always been in how many things you look at. Tiles or objects. With static maps you can quite easily structure things so that you don't have to look at very much at all. When things are dynamic tests such as 'look at the thing in the way' suddenly get harder because you have to determine for any given point A) is something in the way? and B) what is it? The simplest and most memory hungry thing would be to have a tile map where every tile has a precalculated map on the direction to go to reach every other tile. If you used that as a basis for optimisation you can rapidly improve, for instance an easy first step is to not store any direction data for areas where the path in a straight line is optimal. Optimize more and you can reduce the scale of data and compute required to calculate the map you can eventually calculate the map quicker and often for only the start and end points you care about. Follow those optimisations far enough and you end up with many of the algorithms used today. If you have a lot of things moving in a dense area, often the optimal is to maintain a bitmap of 'Something is here' making presence detection trivial. If you then do a 8 passes over that bitmap for each direction you can go (for square tiles) you can create 8 further maps with a count recording when that pass last saw an obstruction. That lets you implement a very fast jump point search where instead of scanning tile by tile you can jump to the next obstruction in order to either find the way around or find the dead end. I think the algorithm mentioned in the article is essentially a jump point search but not going into how the "select the optimal point for bypassing the obstacle" is done. Again this comes back to static/dymamic and how to determine that point. If using object outlines, can objects scale or rotate? You could probably do a reasonable version of jump point with convex hulls around objects and simple fast-out distance functions. A single object system would have difficulty dealing when multiple objects have overlapping bounds though. Two S shaped objects that are overlapping in their bounds might have a path possible through them but it is likely to not involve the optimal passing point of each individual shape alone is not on the path between them. So the ideal is different for static/dynamic, dense/sparse, or memory availability, but all of those factors come back to how they influence how you decide what to look at and how to ignore irrelevant information.

Farer 2y ago

@johnfn The approach I’m considering would be similar to how humans navigate: using only visible information to continuously infer and find the way in real-time. It would essentially break down the flow of how humans navigate into small, incremental steps. Look with their eyes, make a judgment, move, and repeat the process again and again... Of course, trial and error could also occur. This might actually make it feel more natural.