Search the Community
Showing results for tags 'algorithm'.
Found 4 results
-
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)
-
Voronoi Diagram using Fortune's Algorithm
mrcurry posted a topic in ARMA 3 - MISSION EDITING & SCRIPTING
Voronoi diagram using Fortune's algorithm Here's a set of functions developed for my current project to generate Voronoi diagrams in SQF without the need for addons. What does it do? The code generates the edges of the Voronoi diagram from a given set of sites (positions). If you do not yet know what a Voronoi diagram is or what it's uses are check out https://en.wikipedia.org/wiki/Voronoi_diagram. Example: Using the Altis towns as sites How do I use it? Installation: Download the example mission to get the code. Copy the voronoi folder to your mission. In your missions CfgFunctions class include "voronoi\cfgfunctions.ext" like so: class CfgFunctions { #include "voronoi\cfgfunctions.ext" }; Execution: The only included function you will need to call is VOR_fnc_getEdges: private _edges = [_sites, _width, _height] call VOR_fnc_getEdges; VOR_fnc_getEdges takes an array of sites (position2Ds), and width and height in meters for the area to scan. All sites must be inside the rectangle [0,0] and [width, height]. The function returns an array of edges that constitute the Voronoi diagram. Each edge is an array composed of: [ EDGE_START, - Start position EDGE_END, - End position EDGE_LEFT, - Site on the left EDGE_RIGHT, - Site on the right EDGE_NEIGHBOUR, - Internal usage EDGE_LINE_F, - f in the function for the edge's line: y = fx + g EDGE_LINE_G, - g in the function for the edge's line: y = fx + g EDGE_DIRECTION - 2-dimensional direction vector of the ray going from start to end, not normalized. ] Where do I get it? Link (voronoi_example.Altis.zip) Examples Known issues In some cases some edges may not find an intersection and only intersect with the bounding box. I haven't managed to isolate the issue yet but it seems to be a precision error in the intersection check. Suggestions are welcome. It's slow. For 50 sites a call in-mission takes about ~0.5 seconds which is very slow compared to good c++ code. Not entirely sure yet if it's because of my implementation or just SQF having a hard time with the complexity. In my in-mission testing 50 sites took about 0.5 seconds in an unscheduled environment and in scheduled took 1-2.5 seconds. During mission init the code is significantly faster, clocking in 150 sites in about 0.5 seconds. I can put this down partly to the way I handle data but not sure how much quicker I could make it. If anyone has the energy to dissect the code I'd love hear your input. Feedback Constructive feedback is always welcome. I've probably missed cases where the code will break. If you're reporting a bug please if possible also submit the following: The complete set of sites passed. Height and width passed. -
ArmA 3 really annoys me because it lacks a dictionary data type I know you are going to direct me to the BIS_fnc_addToPairs, but there is no actual dictionary datatype in arma 3. The reason i say this is because. Binary search will allow me to traverse a large array data set much quicker than forEach array; Only problem is sorting the data which is mission specific such as town locations is not possible because attempting to sort the array will result in it's meaning lost. _array = _this select 0; _arrayCount = count _array; _requestedElement = _this select 1; _low = 0; _high = _arrayCount; while {_low <= _high} do { //Comupute mid point _mid = round(_low + (_high - _low) / 2); diag_log format ["_mid: %1",_mid]; _indexReturn = {_x == _requestedElement} count _array; diag_log format ["_indexReturn: %1",_indexReturn]; if (_requestedElement isEqualTo (_array select _mid)) then { _pulledData = _array select _mid; diag_log format ["_pulledData: %1",_pulledData]; } else { if (_indexReturn < _mid) then { _low = _mid + 1; } else { _high = _mid - 1; } }; }; _pulleddata Data Pulled: ["Gravia",[14479.8,17614.3,-21.6749], "Telos",[16207,17296.7,-24.3308], "Athira",[13993,18709.4,-25.735], "Lakka",[12282,15732.3,-23.0026], "Frini",[14612.5,20786.7,-47.0032], "Charkia",[18049.1,15264.1,-28.4237], "Rodopoli",[18753.4,16597.1,-32.1656], "Neochori",[12502,14337,-11.5868], "Pyrgos",[16780.6,12604.5,-18.9913], "Paros",[20885.4,16958.8,-49.8089], "Dorida",[19336.9,13252.3,-37.8615], "Poliakko",[10966.5,13435.3,-28.4601], "Kalochori",[21351.6,16361.9,-20.5678], "Agios Dionysios",[9187.95,15947.8,-124.829], "Syrta",[8625.13,18301.6,-179.297], "Chalkeia",[20194.6,11660.7,-45.8388], "Zaros",[9091.81,11961.9,-19.9013], "Kore",[7062.42,16472.1,-116.425], "Sofia",[25680.5,21365.1,-20.7333], "Kavala",[3458.95,12966.4,-6.1822], "Molos",[26943.9,23170.7,-18.0848]] Numerical keys that are sequential are required for this to work. As a binary search is best used on hash-table keys. Any know of any dictionary methods for arma 3?
-
Minimize number of similar lines in algorithm
cybercoco posted a topic in ARMA 3 - MISSION EDITING & SCRIPTING
I'm sure there's a way to minimize the number of lines in this code. I have three variables, each of them needs to get through a simple math function : f(x)=10x. _var1 = 0.2; _var2 = 0.7; _var3 = 0.5; _array = [_var1,_var2,_var3]; _var1 = _var1 * 10; _var2 = _var2 * 10; _var3 = _var3 * 10; If I have let say ten vars, is it better to use the brute way (see snip above), use a foreach command or use a function (optimization wise). Probably the function, isn't it ?
