How to determine Pathing Distance

[Noggog]

Heya,

 

I'm trying to make a script that will evaluate which of several points is the farthest, based on pathing distance, rather than absolute distance. This would mostly be at work indoors where the farthest pathing distance could be a room right below the entrance that isn't actually a long absolute distance away.

 

Is this possible? If so, what's the best way to go about this?

[Astymma]

Heya,

 

I'm trying to make a script that will evaluate which of several points is the farthest, based on pathing distance, rather than absolute distance. This would mostly be at work indoors where the farthest pathing distance could be a room right below the entrance that isn't actually a long absolute distance away.

 

Is this possible? If so, what's the best way to go about this?

 

Hmm, about the only thing I can think of would be to use the various OBSE PathGrid functions to calculate distances. Not that this would be trivial mind you, it seems to me it would be a fairly complicated algorithm but doable.

[Noggog]

Complicated doesn't bother me 8)

 

Whether or not it's CPU heavy in the end is what I'd be concerned with.

 

Thanks for the link! I'll take a looskie! 8)

[fg109]

I took a look at those and tried to come up with a way to use them to find the shortest path. This is what I came up with after over an hour, and there's no guarantee that you'll end up with the shortest path... It's probably going to use up a ton of CPU power running it too.

 

1. find all nodes in area and add them to an array
2. determine distance each node is from destination by applying the distance formula (a^2 + b^2 = c^2; do it twice for 3D) and add the results to a different array
3. determine which nodes are connected to the start node (call these A nodes)
4. for the A node closest to the destination, find the nodes connected to it (call these B nodes)
5. add the A node to an array (let's call it path1)
6. for the B node closest to the destination, find the nodes connected to it (call these C nodes) while ignoring the one that's the A node
7. if there are no such C nodes, then you've reached a dead end; add the B node to an array (deadends1) then start from the A node again
8. otherwise, add the B node to path1 and then add the distance from the A node to the B node to an array (distance1)
9. for the C node closest to the destination, find the nodes connected to it, etc.
10. repeating those steps, you'll eventually you'll find 1 way to get from the start to the end, but you can't tell if it's the shortest way
11. for each node in path1, check to see if any of them are connected to each other (eg. A is connected to C or F to J)
12. if two of them are connected, check the distances (eg AC versus ABC or FH versus FGHIJ)
13. if the distance is shorter, then that means the nodes between are unneccessary
14. erase the relevant entries in path1 and distance1 but do not add the nodes to deadends1
15. keep checking the revised path1 until there are no unneccessary nodes
16. go back to the starting node and repeat steps 4 to 15 to find a new path, while making sure none of the nodes are in path1 or deadends1
17. add the nodes in this path to path2 and dead ends to deadends2 and distance between the points to distance2
18. then find all the nodes in deadends2 that can be connected to a node in path1 and add them to an array (bridges)
19. for the first node in bridges, find the nodes it's connected to in path1 and path2 (let's call these Node1 and Node2)
20. add up the distances in distance1 from start to Node1, and the distances from Node2 to the end of distance2
21. add these sums together, and add it to an array (bridgedistance) then repeat for all the nodes in bridges
22. then you find the shortest distance out of the sum of distance1, sum of distance2, and each entry in bridgedistance
23. the nodes in this path will become the new path1, so add all the other nodes that were in path1, path2, and deadends2 to deadends1
24. create the new distance1 array, and erase the path2, distance2, and deadends2 array
25. repeat steps 16 to 24 until you can't find any more paths

 

Didn't have time to script it, but I'm pretty sure all the steps are possible.

[QQuix]

You may also check Dijkstra and/or A* algorithms

[fg109]

You may also check Dijkstra and/or A* algorithms

I feel like I wasted all my time trying to think up a search pattern. :sad:

[QQuix]

Not really. Thinking is never a waste of time.

You may have created a better one.

Or you may have reinvented the Dijkstra algorithm and we should call it the Dijkstra-fg109 algorithm.

[fg109]

If only my method worked that well. :biggrin: