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 (39.5 KB) points_objects.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.
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”.
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:
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]):
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).
