Shortest path between points

Hey all,

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).

Any help or inspiration is much appriciated

Refinery_Byggeplads.dyn (112.3 KB)

This seems like it might be more relevant to your goal, though I am not sure what exactly you’re after. minimum spanning tree algorithm - Google Search

Search “shortest path” at all forum at first.
Also look into Topologic, “Diversion Workflow”,“Shortest Paths” on this page.
And Topologic in Youtube, and Topologic DYN examples.

1 Like

yeah if i remember right @GavinCrump have a video as well where he show shortest path with Topologic :wink:

yes here it was :wink:

PS i saw the other day Rhythm have give life again to lunchbox old node "shortest walk…probably could help as well…



maybe for this particular case, you can use the PathOfTravel class (DB.Analysis from Revit API)

import clr
import sys
import System
from System.Collections.Generic import List, IList, Dictionary
from Autodesk.DesignScript.Geometry import *
import Autodesk.DesignScript.Geometry as DS

#import Revit API
import Autodesk
from Autodesk.Revit.DB import *
import Autodesk.Revit.DB as DB
#import specify namespace
from Autodesk.Revit.DB.Analysis import *

import Revit

#import transactionManager and DocumentManager (RevitServices is specific to Dynamo)
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):
            t = Transaction(doc, func.__name__)
            ret = func(*args, **kwargs)
            if commit:
            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
        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)

method to also study


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.

Refinery_Byggeplads.dyn (156.3 KB)

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).
Site Pathways Reduced

1 Like