4 ms·
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
by 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 agoAnd I suppose when encountering them (since they were culled not truly removed) switching to a backup collision avoidance mechanism or replanning?
- crispweed 9y agoThe 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..