i am trying to find a way to get the shortest path between a list of points within a parameter with obstacles, where i am able to define the start- and endpoint.
What i have come up with so far is a way to take the shortest path between points but it follows the list structure of the points. I need a way to determine the overall shortest path when all points a connected.
I looked at the traveling salesman problem, but as far as i understand, it donsn’t work with obstacles and within a parameter (I haven’t been able to get it working).
Search “shortest path” at all forum at first.
Also look into Topologic https://topologic.app/learning/, “Diversion Workflow”,“Shortest Paths” on this page.
And Topologic in Youtube, and Topologic DYN examples.
import clr
import sys
import System
from System.Collections.Generic import List, IList, Dictionary
#
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *
import Autodesk.DesignScript.Geometry as DS
#import Revit API
clr.AddReference('RevitAPI')
import Autodesk
from Autodesk.Revit.DB import *
import Autodesk.Revit.DB as DB
#import specify namespace
from Autodesk.Revit.DB.Analysis import *
clr.AddReference('RevitNodes')
import Revit
clr.ImportExtensions(Revit.GeometryConversion)
#import transactionManager and DocumentManager (RevitServices is specific to Dynamo)
clr.AddReference('RevitServices')
import RevitServices
from RevitServices.Persistence import DocumentManager
from RevitServices.Transactions import TransactionManager
doc = DocumentManager.Instance.CurrentDBDocument
def decoTransaction(commit):
def subDecoTransaction(func):
def wrapper(*args, **kwargs):
TransactionManager.Instance.ForceCloseTransaction()
t = Transaction(doc, func.__name__)
t.Start()
ret = func(*args, **kwargs)
if commit:
t.Commit()
else:
t.RollBack()
t.Dispose()
return ret
return wrapper
return subDecoTransaction
def toList(x):
if isinstance(x, (list, dict)) or \
(hasattr(x, "GetType") and x.GetType().GetInterface("ICollection") is not None):
return x
else : return [x]
def get_Location(elem):
if isinstance(elem.Location, LocationPoint):
return elem.Location.Point
else:
bbx = elem.get_BoundingBox(None)
return bbx.Min.Add(bbx.Max).Multiply(0.5)
@decoTransaction(commit = False)
def get_paths(lst_pta, lst_ptb, view):
lst_pathT = DB.Analysis.PathOfTravel.CreateMultiple(view, lst_pta, lst_ptb)
return [[c.ToProtoType() for c in pathT.GetCurves()] for pathT in lst_pathT]
#Preparing input from dynamo to revit
door_site_entry = UnwrapElement(IN[0])
doors_build_entries = toList(UnwrapElement(IN[1]))
lst_xyz_entry_site = List[XYZ]([get_Location(door_site_entry) for d in doors_build_entries])
lst_xyz_entry_build = List[XYZ]([get_Location(d) for d in doors_build_entries])
OUT = get_paths(lst_xyz_entry_site, lst_xyz_entry_build, doc.ActiveView)
I believe the minimum spanning tree algorithm is what I am looking for. What I am trying to create is a way for Dynamo to plan the roads on a construction site. The variables are the different entries both for the site and the main construction.
The idea is that the roads should not go through certain areas, such as the construction itself, crane areas, and so on.
So far, I have tried a few ways to achieve this, and the closest I have gotten is the attached graph and picture.
What is it you are really optimizing for? The shortest path from a site entry to the focal points on site won’t be in the minimum spanning tree, or in the shortest path based on a topology. Look into VASA as it will allow you to account for obstructions, areas of 'harder navigation (i.e. you’re driving up a cliff face), and the like.
My aim is to find the optimal path for a road to be established on the site. It will be part of a larger project in the end, but for now i need to find the shortest path that can connect all points going around my obstacles
Vasa is your best bet then. You’ll likely need to write some Python or C# to make it scale to your needs and outline how to decide which point to connect in which order, and note that in some cases it might be better to connect a point to an existing path rather than to another point.
This example shows point to point (I don’t have the source graph anymore, but you can likely build it in a few minutes).
