A* Shortest Path - Egress Diagram (Almost There But Need Help)

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:
image

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:

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")
1 Like

You can build a visibility graph, see this post:

Edit: I just realised you had already linked to that topic/post, was a bit hung over earlier. Taking the issue of implementing the shortest path algorithm aside, if you make a visibility graph that should output the result you’re looking for. Failing that, you might relax/minimise that path polyline using Kangaroo2 (anchoring vertices coincident with the obstacle vertices).

1 Like

Thanks Anders, the Kangaroo idea is a good suggestion, I’ll look into that.

And although I did link that post I missed the part about visibility graph creation and you’re right in that I believe that’s the direction to go.

The sample floorplan is very simple but it would be solving for more realistic floorplans like a commercial/residential buildings with multiple floors.

Previously I was using Megarachne but this resulted in squiggly lines as well and again im trying to find a native solution.

The stairs will be an easy connection independent of the graph. Each level will have its own visibility graph generated.

Very similar to the image in your post showing the stair with the exception of a more direct path not the Manhattan distance style.

1 Like

Regarding wall-hunger paths: I have the same issue, and I also wonder how to avoid them, and I also think the key could be proper triangulation. However I tried many triangulation methods and still couldn’t find best in these cases. I also tried to find some navmesh algorithms they use e.g. in Unity, but I couldn’t find proper examples. It seems that people have these algorithms implemented in game engines, and just use them. Anyway if you will find some cool meshing algorithm: I’d love to add it to Megarachne (or even better: recieve a pull request :smiley: ). Cause I think it could be a key in many scenarios to have such component, which will create a decent navmesh.

Firstly, thank you for your plugins @w.radaczynski , they are a great asset!

Coming from Unreal Engine Blueprints, Nav Mesh was my first idea and this was the closest I got along that method.

Model Space:

You can see the light green is the “navigable surface area” generated from the union of all walls cut at 1’ off the floor plan, offset 1’, and region union joined.

Here’s the resulting vertices from A* Shortest Path via your Megarachne plugin.

I’ve tried various polyine refits,rebuilds, and such but can’t seem to get these kinds of locations to “reach out” and return the longest line possible aka the most direct path and simplifying the polylines only result in the path “skipping” when it can’t, thus colliding with walls for instance:

I think some kind of recursive line trace from each consecutive “Shortest Path” point has to happen that fires out a ray (aka line) to each next 2 points and if there are no collisions with the walls, return the longest of the 2 lines, and then start the line trace again from the longest line end point to the next in the path and so on.

I guess this needs recursion? Part of me is thinking it may be natively possible in Grasshopper with shifting lists but I haven’t been able to come up with a solution yet.

EDIT:

You can see here by using a Delauny Edge Network and connecting all possible points and then culling against the colliders we can get the small areas where multiple paths are possible.

I think the answer lies in these “local clusters” of choosing the longest line between the “start” and “end” point of each respective cluster. I believe we can determine the start and end by checking the common overlapping start and end points of these lines.

The yellow are possible paths in the non colliding local cluster, the red are the culled paths and the purple is the A* solved path

1 Like

Wow! Maybe that’s an approach we should check! Rather than trying messing up with triangulation we should take given path from A* as polyline + obstacles and try to simplify it further as you’ve mentioned. I haven’t thought about it this way, that we should do such polyline simplification while looking at its intersections with obstacles. Earlier what I did was only converting it to some sort of a spline, which ends up with curvey path, which was slightly more natural, but then it also intersected with obstacles.

1 Like

Okay in testing this, in theory, it works.

Red line is the longest possible path at a local “cluster” of possible non-colliding paths derived after the A* has already been routed.
The reason A and B are not accounted for at those small kinks is that those lines were considered to be “collided” because they ended at the navigable surface wall corner. That will be an easy fix though…

I am fairly confident now that this can be achieved without recursion.

Here’s the portion of the script handling the local cluster longest line logic:

By creating a data tree of the local cluster lines unique start points and unique end points, we can create all possible lines in the local cluster from shortest to longest run. Then using curve length sorting, return only the longest run.

The next step would be to split the A* solved path with this new longest intermediary path and the result should be an A* star path, simplified, and with collision avoidance.

Here you can see the purple is the new path simplifed at the local example cluster, the red is the original A* path

shortest_path_old_version_rework_01b_path_simplification_isolated.gh (71.1 KB)

1 Like

Looks great! I think it would be perfect to have such tool in some “Post-processing” category. That is something I missed personally as well! Let me know if you can pack it as a C# component and pull request it here: GitHub - paireks/Megarachne at Version_1_1_0. If not the pull request, then maybe I could try to rewrite it. Let me know what you think, I’d love to add it and use it myself :wink: 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!

1 Like

I’d love to finalize and package it but I’m a total scripting newbie and just started in Python last month and mostly just beat ChatGPT into submission :grimacing: 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.

That being said I would love to learn how to package it, it’s something I’ve been watching tutorials on but haven’t had time to actually commit to learning fully so I’ve been relying on user objects for now that I can hopefully package down the road when I learn how.

EDIT:

Getting closer!

Realization is that if there are two common end points found per local cluster that can represent the “longest line length”. I just need to massage the logic to ensure it doesn’t ignore the tighter collision bounds corners.

1 Like

Mama mia: If your inspiration/guide/whatever is that thing … I would suggest … well … you can imagine what.

Other than that:

  1. See this? It’s a random (with regard voids) 2d Grid of positions according some user defined x/y resolution (rectangles are drawn “around” them for vis purposes). Then the goal is to use an A-Star routing algo to go from A to B (forget Dijkstra’s stuff: too old ).


  1. So the only thing remaining is to create the Grid having your objects in mind: say doing a BBox, then a BrepFace, then a Grid like the above (where void [i.e. null] means that Face does not contain the given point) … then use an A-Star.

Start from some “reasonable” resolution … then go to Mars (A-Star is very fast anyway so don’t bother with var resolutions).

I can provide an indicative C# on that matter (minus the A-Star: strictly internal thingy etc etc).

1 Like

Hi @PeterFotiadis ,

Yea, ChatGPT tends to poke the fire and for good reason.

However, I wouldn’t call it an inspiration/guide but rather compare it to using a pneumatic framing nailer as opposed to driving nails with a hammer while the end goal is building a house. To me, it’s a tool that has the potential to speed up some repetitive processes but it doesn’t mean it makes me a fine carpenter and as much as I’d like to build the house by hand and learn to perfect the trade craft, it isn’t cost or time feasible currently. It doesn’t mean I don’t value quality or “learning and doing it the right way” but there is a reason that Japanese timber framers co-exist along side stick framers. Both have value for different reasons.

Anyways,

If I understand your solution in regards to the context I am working in. Would the rectangular grid be composed of possible vertices of the wall offset edges? Or do you mean it actually has to be a parallel XY grid ?

Rectangles Highlighting Possible “Nodes”:

Gridded Rectangles Remaining After Collision As Possible Nodes:

Man … in fact you are talking to a @#@$@# computer: that’s the start of the end … blah, blah. That said I hate computers.

Other than that (if we skip Plan B: doing a Graph [a Del Mesh as Graph in fact] from “as even as possible” rnd pts contained in that BrefFace where the inner Loops are your objects) I’ll provide soon a simple C# that prepares the Grid for A-Star routing > an ortho grid without var density spots (why bother? you tell me).

@PeterFotiadis is this what you mean by var(iable) density spots?

Well thank you, I do have the A* solver itself mostly sorted (optimizing the path further is step 2 I’m trying to solve) so I’d love to test with your C# grid implementation.

Indeed

1 Like

Making some progress in “Post-Processing” the A* Path to be simplified:

Step 1: Getting All Possible Connections Post Collision Check

Step 2: Group Lines By Shared Start Point & Return Longest Line Per Group

Step 3: Group Remaining Lines By Shared End Point & Return Longest Line Per Group

Step 4: Build New Polyline Path From Remaining Vertices

Modifications Needed:

Failure Case 01:

Failure Case 02:

“Optimized” A* Star Path (Original Path In Blue, Simplified Path In Red):

Length Difference:

Graph Space:

shortest_path_old_version_rework_01c_path_simplification_isolated.gh (68.5 KB)

1 Like

Well …

Using the A-Star way … there’s 3 ways to cut the mustard:

  1. Get a Graph (various options/ways to do that - for instance using var density pts accodring the obvious logic: proximity to some object/crv) and then run the A-Star. See various rnd pts options on BrepFaces and a filtered Del Mesh > thus > edges as Graph plus the VV Connectivity is easily available (and/or the equivalent Adj Matrix):




  1. Get a Grid and then run a “version” of the A-Star (as in the C# captured below). This means that the thing promished is a bit useless IF you use a classic A-Star that requires classic VV Connectivity [as an Adjaceny Matrix]. Unless you have the source code on hand and you know how to code (do you?).

  2. Forget all that and go ride some proper Ducati.

BTW: Using an existed Grid C# I’ve replaced some lines with some others, added Curves as “obstacles” and here’s the result (as I said in the prev post).


BTW: See A-Star in a 3d graph (from a Mesh) that “mimics” a 3d terrain of some sort.

2 Likes

Thank you @PeterFotiadis ,

The more I’ve been reading about this I realize that I am trying to post process the A* path by getting the longest visible run of the path when , as @AndersDeleuran pointed out as one possible option, I need to implement a visibility graph first and foremost and then run the A* algorithm on that graph.

I got discouraged earlier with this route because I was feeding the visibility graph vertices into A* as a vertex graph which would result in collision not being accounted for. By creating a line graph instead, this will force the path upon the non-colliding lines only.

I believe this visibility graph as a line graph input into my A* algorithm will do the trick hopefully.

I’ll report back here my findings when I’ve had a chance to test

4 Likes

Unless a robust backtracing Method is used (like the one that we use in Graphs [Hamiltonian and the likes]) … a Visiblity Graph is not the equivalent of A-Star shortest route. Wait … in fact you can do a suitable Graph that way … but without code is highly unlikely.

Note: If you are not familiar with coding (level required: expert to pro) don’t attempt to deal with things like these.

Anyway: see a var “voxel” take on a BrepFace (cyan: locked rectangles, red further divisible ones according some Recursion loop value):



The above is using a suitable Class for monitoring all related things:

And a centers Graph based on adjacent Rectangles (NOT the same as a Delauney result by any means) using Intervals Ccx for finding neighbors (1M times faster than some Crv/Crv Ccx approach) . This yields V, E Lists and the classic VV (thus an Adj Matrix (*)), VE, EV Conn Trees > meaning ready to A-Star … etc etc.

Note: PRIOR A-Star you’ll need to find Islands (general case) using solely Recursion on a VV Conn Tree - for more than obvious reasons. This yiels Conn Trees with 2 dim paths (and more than one Adj Matrices). Unless you are not familiar with coding … blah, blah. Here’s an Island:

(*) AdjMatrix from a VV Tree:

BTW: There’s many attempts to solve that kind of Visiblity path around. Some are good some bad some ugly. For instance see these:

That said I’m in the real-life AEC market sector (and I don’t like Parametric in Architecture - at least in the way that most people attempt to use it) thus problems like these … well … are more or less a million miles away from my usual challenges/workflow.

2 Likes

Thanks Peter these are really interesting methods! This recent implementation you show reminds me of a coastline quadtree approximation I saw and this could method has some interesting applications both functionally in solving routes and graphically as well. Reminds me of pixel art a bit.

It looks like you are recursively “subdividing” the grid at collision locations down to a level of subdivision either clamped or until no further subdivision is needed (no more collision). Am I understanding that correctly? Generally speaking at least

I did manage to get an A* solution working based off the Megarachne source code for the A* solving (C#) based and am closing in on the Python version. Referencing the Python git hub links you posted I think I’ll find the last bit of logic I need to smooth out that version.

Visibility graph wise I have a version working well from GH components, line generation and collision checking. I’ll be looking to probably script this as well.

I’ll share the current progress shortly.

1 Like

It works as follows:

  1. The first pass (Loop ==1) yiels a “classic” Face subdivision where: rectangle STATE (see class) is “Locked” (no ccx events with any inner curve) or “Divisible” (ccx events plus the indices of the related curves are stored in the class object ).

  2. Then Recursion: is there’s “Divisibles” around … for each next Loop all “Divisble” Rectanges (Parents) are “split”" in 4 (Children). Each Child is tested (for ccx Events) against ONLY the curves that yielded Ccx Events with Parent. So the “Locked”/“Divisible” STATE is updated etc etc. Recursion exits ONLY if (Loop > Loops) because there’s always “Divisible” Rectangles.

Note: Since we monitor various things a suitable Class is required: So anything in 1/2 is using objects defined by the Class.

Tip: if you attempt the visiblity way … DON’T use stupid rectangles and the likes. Use instead the most complex Polylines (i.e. convex + concave) imaginable. Then … well … use Curves (that’s a bit tricky: requires a bounce solver of some sort).

1 Like