Do your characters use Dijkstra's algorithm?
I assume they turn the boundaries of every object into a point and remove the paths who have surrounding edges that are too close, but how do they deal with spherical obstacles or other ones with complex shapes?