Path Optimization

Hello David,

Im trying to build a definition (potentially using Galapagos) that could optimize a path along a surface (topography).

I basically want to go from points A to B along the surface and find the most "comfortable" path for doing so. This means being within a tolerable distance in Z from the previous point while eventually finding your way to destination B.

So far Ive tried populating the surface with a grid of points and testing neighbors for potential next point destinations along the route.

Do you think Galapagos is the right tool for this? My problem is that

1. I cannot loop the next point along after the first iteration
2. With only one fitness criteria I dont know that out of the potential points along the route its picking up the one that gets me to B eventually.

The other thing I thought of was to instantiate random routes along the grid from A to B and then testing for a desired average slope but I'm having trouble getting that to work as well (new to galapagos).

Thanks in advance for your time and efforts

M

Replies to This Discussion

Permalink Reply by Jacek Jaskólski on September 13, 2010 at 12:56pm

This is interesting. Have you managed to get somewhere?
Maybe this topic could be of some help.

Permalink Reply by msgrom on September 13, 2010 at 1:19pm

Hi,

Thanks for the link. Thats very helpful.

To help describe the problem the attached image describes the better routes along a topography. What im trying to build to get there is a series of evaluation parameters so that the path understands where it would be better to go and what routes to try to avoid.

Im still having trouble building it though

Thank you for your interest and if anyone has any thoughts Id greatly appreciate it.

M

Attachments:

Screen shot 2010-09-13 at 11.10.53 AM.png, 316 KB

Permalink Reply by Jacek Jaskólski on September 14, 2010 at 1:41am

Here's a little something I've managed to do with Galapagos:

The path is created by the Curve on Surface component with two intermediate points.
The solver tries to minimize the sum of the slopes at N=100 division points on the curve, by controlling the uv coordinates of the intermediate points. At the same time it tries to make the path as short as possible.

I've attached the definition.

Attachments:

test_19_optimized road.ghx, 315 KB

Permalink Reply by melaniesrud on May 10, 2016 at 4:16am

Hi im trying this but when i imput the surface gaves me this error

any idea why?? thanks!

Permalink Reply by Wiet Mazairac on September 14, 2010 at 1:46am

Hello,

You say; "...being within a tolerable distance in Z from the previous point...".

This means if the point differ to much in height no route will be found. Is this what you want or do you want to find the route which rises the least?

Permalink Reply by Paul N Jeffries on September 14, 2010 at 6:56am

Hello Mateo,

If you wanted to do this properly (which you probably don't), you could try writing an A* pathfinding algorithm for it between a set (wouldn't necessarily have to be a grid) of nodes on the surface, where the 'movement cost' was a function of distance and height increase (or anything else you wanted, that's the beauty of it). This would obviously require a bit of semi-tricky VB.NET scripting, but then you did learn from the best...

Of course you might get the same result through galapagos eventually, but this method would be (computationally, at least) a lot faster and more exact.

Paul

Permalink Reply by msgrom on September 14, 2010 at 10:34am

Hello Jeffries...

It seems like an A* pathfinding algorithm is the way forward for someone looking forward to doing this properly (that would be me). Ill get back to you when I get stuck with the semi tricky scripting.

Dont forget to say hi to mr. Clark for me. Good to hear from you.

Best,

M

Permalink Reply by brendon_carlin on September 17, 2010 at 8:38am

Hey Paul and Mateo,

i guess i also learned from the best (thanks paul), though i hope my lack of skills doesnt reflect on you. ;)

here is a very quickly resolved version of an pathfinding code, the fitness test is very simple and not well tested. but this might help.

best

Attachments:

pathfinding fit.ghx, 53 KB
pathfindinf fit.3dm, 143 KB

Permalink Reply by Charles Aweida on September 17, 2010 at 4:14pm

Nice Brendon! very cool to see this in C#

Permalink Reply by Andrés Utz on March 28, 2013 at 1:52pm

the definition looks good...but dont work for me...any idea?

old?

Permalink Reply by efthymis on April 14, 2013 at 10:53am

replace GetClosestPoint with ClosestPoint within the script

Permalink Reply by Richard Schaffranek on January 1, 2014 at 1:23pm

Within the old download (version 3.2) of SpiderWeb there is a sample that solves the problem without the use of galapagos.

http://www.food4rhino.com/project/spiderweb

RSS