# Possibility of multiple paths in pathfinding algorithm

**URL:** <https://discourse.mcneel.com/t/possibility-of-multiple-paths-in-pathfinding-algorithm/191335>\
**Category:** Grasshopper\
**Tags:** windows\
**Created:** [September 17, 2024, 8:37am UTC](https://discourse.mcneel.com/t/possibility-of-multiple-paths-in-pathfinding-algorithm/191335 "2024-09-17T08:37:20Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ainharjar](https://sea3.discourse-cdn.com/mcneel/user_avatar/discourse.mcneel.com/ainharjar/32/606371_2.png) [@Ainharjar](https://discourse.mcneel.com/u/Ainharjar)\
**Post date:** [September 17, 2024, 8:37am UTC](https://discourse.mcneel.com/t/possibility-of-multiple-paths-in-pathfinding-algorithm/191335/1 "2024-09-17T08:37:20Z")

</div>

Hello all, I have been working on a pathfinding algorithm for my uni, which I got to work. It works currently with 2 points (start/end), 1 obstacle, and 1 “highway” path.  
[paths\_2d.gh](https://discourse.mcneel.com/uploads/short-url/bz8uE5Ld6wu45JDyy3euXFbtSzU.gh) (39.5 KB)  
[points\_objects.3dm](https://discourse.mcneel.com/uploads/short-url/hVYeVvHu6vAsGHc0C32yxp89NQ7.3dm) (45.8 KB)

Now the issue is I want the possibility of having multiple start/end points and obstacles. With my current solution of doing it using curve/curve intersection and the shatter components however it doesn’t seem possible atm, maybe I’m thinking about it the wrong way.

 ![image](https://global.discourse-cdn.com/mcneel/uploads/default/original/4X/f/0/0/f00e30818649b10fd439f5ceb6cf63ec96308a28.png)

Any tips of how to go about this?

---

<div class="post-metadata">

**Author:** ![PeterFotiadis](https://sea3.discourse-cdn.com/mcneel/user_avatar/discourse.mcneel.com/peterfotiadis/32/472316_2.png) [@PeterFotiadis](https://discourse.mcneel.com/u/PeterFotiadis)\
**Post date:** [September 17, 2024, 9:10am UTC](https://discourse.mcneel.com/t/possibility-of-multiple-paths-in-pathfinding-algorithm/191335/2 "2024-09-17T09:10:57Z")

</div>

A long thread … but maybe worth reading it.

> [@A\* Shortest Path - Egress Diagram (Almost There But Need Help)](https://discourse.mcneel.com/t/a-shortest-path-egress-diagram-almost-there-but-need-help/164055):
>
> 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 exampl…

---

<div class="post-metadata">

**Author:** ![Ainharjar](https://sea3.discourse-cdn.com/mcneel/user_avatar/discourse.mcneel.com/ainharjar/32/606371_2.png) [@Ainharjar](https://discourse.mcneel.com/u/Ainharjar)\
**Post date:** [September 17, 2024, 12:09pm UTC](https://discourse.mcneel.com/t/possibility-of-multiple-paths-in-pathfinding-algorithm/191335/3 "2024-09-17T12:09:32Z")

</div>

An insane read, thank you for that, made me realise how much knowledge I am still lacking :0

It’s not quite what I’m looking for though, I’ll have to reread it to make sure, but my pathfinding around objects won’t need that amount of complexity/accuracy, especially as my obstacles won’t be as complex.  
My issue lies more with having the possibility to have multiple start/end points, and finding if there are overlapping/near paths which could be combined into a more efficient bigger “highway”.

---

<div class="post-metadata">

**Author:** ![PeterFotiadis](https://sea3.discourse-cdn.com/mcneel/user_avatar/discourse.mcneel.com/peterfotiadis/32/472316_2.png) [@PeterFotiadis](https://discourse.mcneel.com/u/PeterFotiadis)\
**Post date:** [September 17, 2024, 12:21pm UTC](https://discourse.mcneel.com/t/possibility-of-multiple-paths-in-pathfinding-algorithm/191335/4 "2024-09-17T12:21:02Z")

</div>

Well … if by path finding you mean an A\* thingy (shortest path the modern way, that is) then in the latest posts is addressed (I’ve posted portions of code [i.e. Methods] that is **not** internal) the classic way: given N objects and M pairs (start/end Pts) … then find all the possible “visible” line segments (in M Loops), define a Graph and solve it (this requires VV connectivity - per possible Island) via the A\* algo. Then compare (if required) the paths.

Obviously various “options” are possible: like checking segments Ccx Events and/or any imaginable other requirement.

That said the easy case (a poor relative to visibility shortest route) : imagine a Graph derived from a Mesh (any valid Mesh where holes are your object’s footprints). Then a proper A\* algo can very easily find the shortest path from/to any Mesh vertex pair. You can even implement some Z factor (kinda a primitive mountain road path finding). Say something like this:

  
 ![Screen Shot 028](https://global.discourse-cdn.com/mcneel/uploads/default/original/4X/1/3/7/1379fbf603614595feb3e30141e89d4466416a55.jpeg)

That said the general case is a MOO Path finding (Multi Objective Optimization) … but that is another animal.

But all these (while rather easy - more or less) require code.

---

<div class="post-metadata">

**Author:** ![PeterFotiadis](https://sea3.discourse-cdn.com/mcneel/user_avatar/discourse.mcneel.com/peterfotiadis/32/472316_2.png) [@PeterFotiadis](https://discourse.mcneel.com/u/PeterFotiadis)\
**Post date:** [September 18, 2024, 8:42am UTC](https://discourse.mcneel.com/t/possibility-of-multiple-paths-in-pathfinding-algorithm/191335/5 "2024-09-18T08:42:27Z")

</div>

> [@Ainharjar](#):
>
> are overlapping/near paths

BTW:

In general any A-Star solver works either (a) using a from/to Node … Or (b) a from (or to) VS **any other** Node. Like (one of the many Paths is shown using pipes and TextDots [for the Nodes]):

 ![Screen Shot 030](https://global.discourse-cdn.com/mcneel/uploads/default/original/4X/4/f/b/4fbd1a1ca47260a67149aafe8b055cfa5114fd67.jpeg)  
 ![Screen Shot 031](https://global.discourse-cdn.com/mcneel/uploads/default/original/4X/4/8/d/48db74e148be8d74d4ad80d4cdcb92b16e427cca.jpeg)

Meaning that in case (b) you get some sort of “Dendrogram” so to speak. The Solver doesn’t care either if you use a classic Graph or a **Visibility** Graph because works solely against a VV Conn thingy (and the related dist Matrix).