Find Shortest Path - Function Suite

[Mr.Peanut]

I've not yet finished the docs, but here's a fully functioning demo.  Given a set of locations with a fixed start and end, it calculates the shortest route connecting all locations.  Be forewarned, the algorithm is a little slow. Let me know if it misorders the locations.  I've tuned it for speed, not for accuracy.  Please let me know what you think.  Enjoy  ;D


To my horror I've found the demo has a bug.  The map reset does not clear the previous tour.  Only the first tour functions correctly.  I am looking into this. Very stange.

Fixed the bug. Updated download.
No comments?

Crap Crap Crap!
I went back to the demo last night and it did not work! Will investigate and update download ASAP.

Okay.  Fixed it.  Just dropped a couple underscores when I made a small change to a function.  The version posted now works.  I promise!  

[Homefry31464]

Takes time for people to post... I'll test it out later....

[surpher]

Hi Mr Nut, Tested this yesterday, works fine. All locations visited in the correct order, I even moved it to Nogova to test it on the roads, no problems at all. :thumbsup:

[Mr.Peanut]

Thanks, Surph.

I'll comment the interface and write some docs, specifically the use of the tuning parameters.

I just thought a tool of this sort would generate a bit more interest...

[Unnamed]

To be honest I could not really see what it does, from the example mission supplied. It just looked like it was following the waypoints in the order they were selected on the map. I'm sure there must be more to it than that?

I saw this as a possible method to allow the AI to navigate Islands, depending on the type of vehicle and roads. Or allowing the AI to dynamically navigate around enemy areas, or blockades, supply routes e.t.c If you could associate each route with the road systems Object ID's, you could automatically generate the waypoints.

A more practical example of what it can do, would help me.

[Mr.Peanut]

When you choose the points on the map, the first and last point you select will be your starting point and ending point, respectively.  It does not matter what order you choose the points in-between.  The function sorts the points to give the shortest path that passes through them all.  It is not a trivial problem to solve economically.

The method does not care about the distance by road or sea, or if there exist any physical barriers, it only cares about the distance as the crow flies.  The fact that OpFl can barely do this type of calculation in anything resembling a reasonable amount of time indicates any more sophicated methods would run too slowly to be useful, since functions literally halt all other processes.

[Mr.Peanut]

Submitted and pending...