Hello, I have another Shortest Walk topic to create, I know, I know,
I’ve been trying out various path finding plugins and solutions throughout food4rhino and these forums.
I’m trying to create a simplified version that also does not rely on third party plugins or installed libraries ideally.
I have what I would call a need for a “simple path” in which I want to automate the line drawing of an egress path you may find in architectural construction documents.
Example:
In this example you can see the script working off a start and end point somewhere on a “floor plan” with interior courtyards blocking the Euclidean path.
I cull the colliding lines, and then get the control points of all remaining lines to feed into the A* Algorithm to determine the shortest path of the remaining points. (In this case there aren’t many options…)
Here’s what the pre-collision checked edge network looks like:
And post-collision check edge network:
It works most of the time but sometimes it gets a little “wall hugger” happy:
Fine:
Graph Space:
I can’t tell if my A* algo is failing or incorrectly weighted or if it’s working and I need to run an additional step after the initial path.
I saw this great implementation by @AndersDeleuran and tested it with a trimesh representation of my floorplan and it returns (beautiful but “squiggly” lines) by nature of the triangulation of the mesh as the means of the path routing I imagine? I think this implementation is a bit overkill for what I am going for. (Perhaps I’m using it incorrectly? Either way I really appreciate it!)
Trimesh Example (Green is the Shortest Path from Ander’s script, Purple is a simplified path via Curve Closest Point):
This APE example of a Shortest Path component from @Martin_Manegold and Dominik Zausinger of Rhenso is what inspired me:
https://www.rhenso.com/post/shortestpath
I do need to take “body width” into account further down the road as egress paths need to have a certain clearance width of course. (I can handle this with polyline two sided offsets to ensure space from every possible wall)
Anyways, right now I’m just trying to get the shortest path algorithm nailed down. I feel like I’m close.
Any help is greatly appreciated!
Grasshopper Thus Far:
20230812_Simplified_Path_Finding_Egress_01a.gh (21.7 KB)
Python Thus Far:
#Author: Michael Vollrath
#2023.08.12
#Made With <3 In Dallas, TX
ghenv.Component.Params.Input[0].Name = "Start Point"
ghenv.Component.Params.Input[1].Name = "End Point"
ghenv.Component.Params.Input[2].Name = "Network Node Points"
import rhinoscriptsyntax as rs
import Rhino.Geometry as rg
# Assuming you already have the En list of Point3d nodes and the path list of indices
# Find the nearest nodes to the start and end points
start_node = En.index(Sp)
end_node = En.index(Ep)
# Calculate distances between nodes to build the graph
graph = {}
for idx, node in enumerate(En):
graph[idx] = []
# Define edges based on desired connections and edge lengths
for idx in range(len(En)):
if idx + 1 < len(En):
edge_length = En[idx].DistanceTo(En[idx + 1]) # Calculate the edge length
graph[idx].append((idx + 1, edge_length)) # Add neighbor and edge length
# A* algorithm to find the best path between two points
def astar(graph, start, goal):
open_set = [(0, start)]
closed_set = set()
parent_map = {}
g_score = {node: float('inf') for node in graph}
g_score[start] = 0
while open_set:
current_g, current_node = min(open_set)
open_set.remove((current_g, current_node))
print("Current node:", current_node) # Add this line
if current_node == goal:
path = [goal]
while path[-1] in parent_map:
path.append(parent_map[path[-1]])
path.reverse()
return path
closed_set.add(current_node)
for neighbor, edge_cost in graph[current_node]:
if neighbor in closed_set:
continue
tentative_g_score = g_score[current_node] + edge_cost
if tentative_g_score < g_score[neighbor]:
parent_map[neighbor] = current_node
g_score[neighbor] = tentative_g_score
f_score = tentative_g_score + edge_cost
open_set.append((f_score, neighbor))
return None
# Find the best path using A*
path = astar(graph, start_node, end_node)
# Retrieve the path points from the En list
path_points = [En[node_index] for node_index in path]
# Retrieve the path points from the En list
path_points = [En[node_index] for node_index in path]
# Create Line objects based on the path points
path_lines = []
for i in range(len(path_points) - 1):
start_point = path_points[i]
end_point = path_points[i + 1]
line = rg.Line(start_point, end_point)
path_lines.append(line)
# Print or use the path lines as needed
for line in path_lines:
print(line)
if path:
print("Best path:", path)
else:
print("No path found")
). Cause I think it could be a key in many scenarios to have such component, which will create a decent navmesh.
It would be perfect to have it as a one component with 2 inputs: 1. list of points / lines of path, 2. obstacles and single output of points / lines of simplified path!
while referencing the forums and API docs to help guide it. I am starting to write my own stuff from scratch though so I am actually learning and not just having ChatGPT “do my homework” for me. Though it has really helped speed up my learning process as it lets me rapidly iterate ideas and break through the syntax hurdle of reading programs.
