Search the Community
Showing results for tags 'dijkstra'.
Found 1 result
-
shortest path [RELEASE] Sarogahtyps Simple Shortest Paths - SSSP V-2.0
sarogahtyp posted a topic in ARMA 3 - MISSION EDITING & SCRIPTING
Sarogahtyps Simple Shortest Paths - SSSP V-1.0 the simplest way to find your path 😉 Actually there is the Dijkstra algorithm and the A* algorithm available. Both are able to get a shortest path through a "2D"-map and A* is always faster than Dijkstra on this. How much faster A* is depends on the size of the given situation. As more nodes and connections the given situation has as more A*'si advantage comes in play. Dijkstra's advantage is that it should find the true shortest path always while A* just finds one short Path. Also Dijkstra is much better able to solve the shortest path problem in a house with multiple floors (3D-problem). A* can solve this as well but it's often slower there and finds much longer shortest paths in that situation. A* will solve this through a multiple floor handler which is currently not implemented for it. sqf implementation of Dijkstra algorithm: Usage: First you should read the script header. The script supports 2 different formats of node/connection lists. the first syntax of parameter 3. and 4. is needed if you don't like to precalculate the distances/weights for all connections. In this case you will deliver the node positions as well and the script calculates the distances itself. The alternative syntax for parameter 3. and 4. has no positions but those distances instead. I recommend to implement the script to armas function library by registering it via description.ext file. But it will work with or without a manually done compiling as well. The following lines executes the script twice and writes the solution to .rpt-file via diag_log command. One time the precompiled script is spawned the second time it gets called (works only if environment is scheduled). Yes, you can use execVM as well. It has the same usage as the spawned function: The output for the situation shown in picture above is: 1:56:25 "Nodes after spawn" 1:56:25 [0,2,3] 1:56:25 " " 1:56:25 "Nodes after call" 1:56:25 [0,2,3] 1:56:25 " " Yeah, correct solution ... it works 😄 sqf implementation of A*-algorithm A* - Dijkstra runtime comparsion videos Planned features: - A* algorithm improvement to solve 3D problems (multiple floors) - Travelling Salesman algorithms Known issues: -Dijkstra is currently not getting always the true shortest path due to a bug in implementation Changelog v 2.0 (Download: Scripts Zip - Mission) - added implementation for A*-algorithm - minor performance optimizations on Dijkstra - added demo mission which is able to compare both algorithms v 1.1 (Download SQF) -performance optimizations - 65-70% less readability / 30-35% better performance v 1.0 (Download: SQF - Mission) - initial release- 32 replies
-
- 17
-
-
-
- travelling salesman
- dijkstra
- (and 4 more)