3 ms·

For people interested in path finding, there was some fascinating research done in the 90s: http://faculty.nps.edu/ncrowe/snell2.htm http://faculty.nps.edu/ncr

by Radim 9y ago

For people interested in path finding, there was some fascinating research done in the 90s: http://faculty.nps.edu/ncrowe/snell2.htm http://faculty.nps.edu/ncrowe/snell2.htm They used Snell's law to design pathfinding directly on region polygons, based on ray refraction. This is in contrast to the more common type of "grid searches" (A* being the most prominent example) which superimpose a grid and then do a wavefront graph search on that. I remember implementing this "refraction search" in the 90s as a C++ PoC. It was a fascinating and elegant concept, but a complete bitch to get right due to its "continuous" nature (rays just barely hitting polygon vertices, parallel edges, numerical instability).

rcfox 9y ago
I think it's more popular nowadays to do a search on an adjacency graph of polygons and then smooth the path with something like the funnel algorithm. http://digestingduck.blogspot.ca/2010/03/simple-stupid-funnel-algorithm.html http://digestingduck.blogspot.ca/2010/03/simple-stupid-funne...
- crispweed 9y ago
  Yes, a lot of people are doing this, and it's not a bad approach. There's another approach you can take for continuous space pathfinding, however, which is to use visibility graphs. See http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20graphs.pdf http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20gr..., for example, for some explanation and diagrams. This is the approach I used in PathEngine (www.pathengine.com). A lot of people are put off by the possibility for graph explosion in situations where there are a lot of obstacles in an open environment, but PathEngine works around this quite effectively by detecting these kinds of obstacles and pulling them out of the visibility graph (and pathfinding search).
  - AstralStorm 9y ago
    And I suppose when encountering them (since they were culled not truly removed) switching to a backup collision avoidance mechanism or replanning?
    - crispweed 9y ago
      The trick is to detect obstacles that are likely to have minimal affect on the global result of pathfinding search, e.g. convex obstacles that are in the middle of open spaces, or, more specifically in the case of PathEngine, obstacles that don't combine with other nearby obstacles to form larger blockages. After the initial graph search, the path is modified to avoid these obstacles locally (by pushing the path around the obstacles, essentially), before it's returned from the pathfinding query. So the way it's set up in PathEngine this optimisation is largely hidden from application code (code that calls into the pathfinding API). Leaving this to be handled later on, by agent local obstacle avoidance, could also work..

by Radim 9y ago

rcfox 9y ago

I think it's more popular nowadays to do a search on an adjacency graph of polygons and then smooth the path with something like the funnel algorithm. http://digestingduck.blogspot.ca/2010/03/simple-stupid-funnel-algorithm.html http://digestingduck.blogspot.ca/2010/03/simple-stupid-funne...

crispweed 9y ago
Yes, a lot of people are doing this, and it's not a bad approach. There's another approach you can take for continuous space pathfinding, however, which is to use visibility graphs. See http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20graphs.pdf http://www.cs.kent.edu/~dragan/ST-Spring2016/visibility%20gr..., for example, for some explanation and diagrams. This is the approach I used in PathEngine (www.pathengine.com). A lot of people are put off by the possibility for graph explosion in situations where there are a lot of obstacles in an open environment, but PathEngine works around this quite effectively by detecting these kinds of obstacles and pulling them out of the visibility graph (and pathfinding search).
- AstralStorm 9y ago
  And I suppose when encountering them (since they were culled not truly removed) switching to a backup collision avoidance mechanism or replanning?
  - crispweed 9y ago
    The trick is to detect obstacles that are likely to have minimal affect on the global result of pathfinding search, e.g. convex obstacles that are in the middle of open spaces, or, more specifically in the case of PathEngine, obstacles that don't combine with other nearby obstacles to form larger blockages. After the initial graph search, the path is modified to avoid these obstacles locally (by pushing the path around the obstacles, essentially), before it's returned from the pathfinding query. So the way it's set up in PathEngine this optimisation is largely hidden from application code (code that calls into the pathfinding API). Leaving this to be handled later on, by agent local obstacle avoidance, could also work..