Should I code this pathfinding algorithm?

[Mr.Peanut]

I have an algorithm written in FORTRAN77   that given an array of locations, will return the shortest possible route that connects every  location in the array, with fixed endpoints.  Is this worth trying to script for OpF? Here are some example  images.



 

 

 

 

 

[bored_onion]

seems like it could be useful for pathfinding for ai improvements. other than that the pictures look real pretty...

[.pablo.]

awesome idea, plz explain how you made it

[Mr.Peanut]

Hmmm. I really thought there would be a little more interest in this.

The thing is this algorithm really just calculates the best way to "connect the dots" between two fixed endpoints. A true pathfinding algorithm would discard unnecessary dots.

The method used is called simulated annealing.  The cost function is distance.  Two random points are chosen. 50% of the time the segment is reversed. 50% of the time the segment is inserted somewhere else along the path.  In turn, whether each of these changes is implemented depends on a probability calculated from the change in cost.  This means that most of the time a change will be made if it reduces cost, or the change may not be made at all.  Occaisionally a change will be made that increases the cost.

It does not require recursion only iteration.  The main difficulty in coding it is that array handling in OpFl is clumsy.  Unless there is more interest expressed, I can't be bothered, since I don't need the function myself, I just thought it was an interesting experiment.

[Bluelikeu]

Nice idea, sounds good for AI pathfinding improvements.

Are you sure that you can program it in Operation Flashpoint?

I think that certain methods would be needed to be used that aren't in OPF scripting.

Thanks,
Bluelikeu

[Mr.Peanut]

I've coded it.  Now I just need to test it with some sort of point and click map interface.
Hold on tight.... ;D

(the next morning)
My god, if I had known in advance how hard it is to debug in OpFl, I might not have started this! You can't even read the entire error message to find out where the error lies...

Not sure how efficient this algorithm is.  The tradeoff is speed vs. numerical stability. Might be more efficient to simply check the n! permutations.

[Unnamed]

Not sure how efficient this algorithm is.  The tradeoff is speed vs. numerical stability. Might be more efficient to simply check the n! permutations.

How long we talking about?

A dealy of say 10 seconds would not be long in IMHO, if you where calculating the best route from one end of an island to the other. As long as it does not lag OFP while calculating, I would expect the time to vary depending on the task.

[Bluelikeu]

I don't think that delays will matter, as the person would have no problem waiting for the coordinates to be found.

@Mr. Peanut
I would be nice if you could give us the algorithm before you fully convert it. Would be nice to see what is going on without OFP scripting boundries in the way.

Thanks,
Bluelikeu

[General Barron]

Hmmm. I really thought there would be a little more interest in this.

The thing is this algorithm really just calculates the best way to "connect the dots" between two fixed endpoints. A true pathfinding algorithm would discard unnecessary dots.

The method used is called simulated annealing.  The cost function is distance.  Two random points are chosen. 50% of the time the segment is reversed. 50% of the time the segment is inserted somewhere else along the path.  In turn, whether each of these changes is implemented depends on a probability calculated from the change in cost.  This means that most of the time a change will be made if it reduces cost, or the change may not be made at all.  Occaisionally a change will be made that increases the cost.

It does not require recursion only iteration.  The main difficulty in coding it is that array handling in OpFl is clumsy.  Unless there is more interest expressed, I can't be bothered, since I don't need the function myself, I just thought it was an interesting experiment.

Whew! I need to take more CS classes... I think I only understood "recursion" and "iteration"  .

Anyway, although making an algorithm like that is way above my head, at least I understand what it does. Although I can't think of any uses for it off hand, I'm sure it could be very handy in some kind of large-scale, dynamic mission. I'll report back if I can think of a good use for it, to express some more interest.

[DBR_ONIX]

This could be extremely usefull for missions like CessnaFun!
Take the taxi.. In lots of places, you call for a cab, it drives over open ground (If theres a t-junction between you and cab).. But with this you could put points over map, and it would drive the quickest way to you..
Go for it  ;D
- Ben

[MachoMan]

Whew! I need to take more CS classes... I think I only understood "recursion" and "iteration"  .

Anyway, although making an algorithm like that is way above my head, at least I understand what it does. Although I can't think of any uses for it off hand, I'm sure it could be very handy in some kind of large-scale, dynamic mission. I'll report back if I can think of a good use for it, to express some more interest.

Simulated annealing is a method used to find a solution to a mathematical problem that you are unable to solve with math, while it does have a sollution (Odd but true), it is also used when calculating is possible, but would simply take to much time. It is often used for solving NP problems.
It will find a "optimal" sollution to a problem, where "optimal" is as near optimal as your algorithm allows.

It does not require recursion only iteration.  The main difficulty in coding it is that array handling in OpFl is clumsy.  Unless there is more interest expressed, I can't be bothered, since I don't need the function myself, I just thought it was an interesting experiment.

Fortran isn't a dream either