Shortest path - taking obstacles and the terrain into account

A few notes that might be worth considering:

A common path finding strategy in video games and robotics is to use a navigation mesh, which enables one to find shortest/weighted paths in topologically complex environments (i.e. with obstacles, holes, terrain etc.) using graph theory algorithms (e.g. Dijkstra’s shortest path). I did a bunch of work on this a long time ago using NetworkX/GHPython for the graph stuff:

But today you could use any of the graph plugins that exist for Grasshopper (edit: as @w.radaczynski points out above, my bad).

An alternative appropriate graph is the visibility graph, where one connects all the vertices of the obstacles and cull any that intersect the obstacles. Which should yield the shortest visible path (i.e. which would be difficult to represent with navigation mesh):

Another alternative that might be appropriate is a medial axis route network graph, which is what we eventually went with while doing the research above:

15 Likes