sarogahtyp 1104 Posted April 26, 2019 Hey guys, I need some help please. I wrote a sqf implementation of Dikstra's Shortest Path algorithm. The algorithm itself is working but my problem is that the manipulated input array (_allNodes) which I gave as parameter 3 does not contain the solution at the end. I guess that somwhere during the script the pointer connection to the input array gets lost but I cant discover where. situation the script is feeded with as picture: https://imgur.com/UMT9v1B I start the script from initServer.sqf with: private _nodeThings = [3,1,0,2]; private _index = [0, 3, _nodeThings, [[10, 0, 1], [9,0,2], [15, 1, 3], [5, 2, 3]]] spawn saroSSSP_fnc_shortPathDijkstra; waitUntil {scriptDone _index}; // DEBUG _notext = " "; _text = "Nodes after script"; diag_Log _text; diag_log _nodeThings; diag_log _notext; // DEBUG parameters are described here: Spoiler 1. number - ID of start node 2. number - ID of end node 3. array - nodes list - format: [ [ID1, positionASL], [ID2, positionASL], ..., [IDn, positionASL] ] ID1-IDn - numbers, ID of the specific node ID range has to be 0 to n and each ID between 0 and n has to have a node (no leaks) ID may provided unsorted cause they get sorted anyways positionASL - position above sea level format(alternative, faster): [ ID1, ID2, ..., IDn ] 4. array - connections list - format: [[fromID, toID], [fromID, toID], ..., [fromID, toID]] fromID - number, connections start node ID toID - number, connections end node ID format (alternative, faster): [[distance, fromID, toID], [distance, fromID, toID], ..., [distance, fromID, toID]] distance can be any distance format you prefer (distance, distanceSqr, distance2D may be worse with multiple floors) 5. boolean - Oneway - do we have Oneway connections? true means we have such. false means not. returned nodes array (3.) - array of nodeIDs in order to pass from first (start node) to last (end node) element or boolean false - indicating that input data was not valid boolean true - indicating that there is no possible solution complete Script here: Spoiler /* !!! WIP !!! - don't use, it's not ready... Author: Sarogahtyp Title: SSSP(D) - Sarogahtyps Simple Shortest Path - Dijkstra algorithm https://en.wikipedia.org/wiki/Dijkstra Description: Dijkstra-algorithm - sqf implementation This algorithm is much more time consuming than A* algorithm if only 1 floor is necessary if multiple floors are needed then it has to be tested if A* (multiple floor solution) is faster or not Arguments: if you use alternative format at 3. then you have to use alternative format at 4 as well and vice versa if you have precalculated distances (maybe at mission start) for 4. then alternative format is faster if you would calculate 1. number - ID of start node 2. number - ID of end node 3. array - nodes list - format: [ [ID1, positionASL], [ID2, positionASL], ..., [IDn, positionASL] ] ID1-IDn - numbers, ID of the specific node ID range has to be 0 to n and each ID between 0 and n has to have a node (no leaks) ID may provided unsorted cause they get sorted anyways positionASL - position above sea level format(alternative, faster): [ ID1, ID2, ..., IDn ] 4. array - connections list - format: [[fromID, toID], [fromID, toID], ..., [fromID, toID]] fromID - number, connections start node ID toID - number, connections end node ID format (alternative, faster): [[distance, fromID, toID], [distance, fromID, toID], ..., [distance, fromID, toID]] distance can be any distance format you prefer (distance, distanceSqr, distance2D may be worse with multiple floors) returned nodes array (3.) - array of nodeIDs in order to pass from first (start node) to last (end node) element or boolean false - indicating that input data was not valid boolean true - indicating that there is no possible solution */ private _correctList = params [ ["_startNode", objNull, [0]], // numbers allowed only ["_endNode", objNull, [0]], // numbers allowed only ["_allNodes", objNull, [ [] ]], // arrays allowed only ["_allConnections", objNull, [ [] ]], // arrays allowed only "_oneway" ]; // check for valid parameter data types if (!_correctList) exitWith {_allNodes = false;}; //check if first element of _allNodes is number or array and if it is array then with exact 2 elements private _correctNodes = _allNodes params [["_firstElementNodes", objNull, [0, []], [2]]]; //check if first element of _allConnections is an array and if it has 2 or 3 elements private _correctConnections = _allConnections params [["_firstElementConnections", objNull, [[]], [2, 3]]]; // exit if at least one of both first elements has wrong format if (!_correctNodes || !_correctConnections) exitWith {_allNodes = false;}; // determine arguments 3. and 4. format private _alternativeFormat = count _firstElementConnections isEqualTo 3; private _sqrt2 = 1.41421; //set maximum possible distance private _maxDist = worldSize * _sqrt2; //ensures that ID is the same as the array index of each element _allNodes sort true; if (!_alternativeFormat) then { // calculate distances and insert as first element of each connection _allConnections = _allConnections apply { _x params ["_fromID", "_toID"]; _fromPos = (_allNodes select _fromID) param [1]; _toPos = (_allNodes select _toID) param [1]; _dist = _fromPos distanceSqr _toPos; [_dist, _fromID, _toID] }; }; // insert distance to start value, predecessor node ID and already viewed state for each node. // delete positions as not needed anymore _allNodes = _allNodes apply { _nodeID = if(typeName _x isEqualTo "ARRAY") then {_x param [0]} else {_x}; _dist = if(_nodeID isEqualTo _startNode) then {0} else {_maxDist}; [_dist, _maxDist, false, _nodeID] }; _unviewedAvailable = true; _solutionFound = false; // define a name for the script scope to be able to break all loops scopeName "main"; while {_allNodes findIf {(_x param [2]) isEqualTo false} > -1} do { //sort by distance _allNodes sort true; // select node with shortest distance value (_allNodes is sortet ascending by distance) private _index = _allNodes findIf {_x params ["", "", "_viewed"]; _viewed isEqualTo false}; _currentNode = _allNodes param [_index]; _currentNode params ["_currDist","","", "_currID"]; // change viewed state of current node to true _currentNode set [2, true]; //get all connections to all neighbors of current node _neighbConns = _allConnections select { _x params ["", "_fromID","_toID"]; (_fromID isEqualTo _currID) || (_toID isEqualTo _currID) }; //get all not viewed neighbors of current node _neighbNodes = _allNodes select { _x params ["","","_neighbView", "_neighbID"]; _isNeighbor = _neighbConns findIf {_x params ["", "_fromID","_toID"]; (_fromID isEqualTo _neighbID) || (_toID isEqualTo _neighbID)} > -1; (!_neighbView && _isNeighbor) }; //process all neighbor nodes of current node { _x params ["_neighbDist","","", "_neighbID"]; // find the index of the connection between current node and this neighbor node private _index = _neighbConns findIf {_x params ["", "_fromID","_toID"]; _neighbID isEqualTo _fromID || _neighbID isEqualTo _toID}; // get distance value of the that connection private _connDist = (_neighbConns select _index) param [0]; private _thisDist = _currDist + _connDist; // if we found a shorter distance then set current node as predecessor of this neighbor node and update the found distance for it if ( _neighbDist > _thisDist ) then { _x set [0, _thisDist]; _x set [1, _currID]; //check if this neighbor is the end node if (_neighbID isEqualTo _endNode) then { _solutionFound = true; breakTo "main"; //breaks all scopes except main scope }; }; } count _neighbNodes; }; if (!_solutionFound) exitWith { _allNodes = true; _text = "No Solution found:"; diag_Log _text; diag_Log " "; }; // rearrange _allNodes array to get it sorted by node ID again // also get rid of not needed data _allNodes = _allNodes apply { _x params ["", "_predID", "", "_nodeID"]; [_nodeID, _predID] }; _allNodes sort true; // build solution path array from end node to start node private _solution = []; private _currNode = _allNodes param [_endNode]; while {!((_currNode param [0]) isEqualTo _startNode)} do { //current nodes ID is part of solution _solution pushBack (_currNode param [0]); //next current node is predecessor of actual current node _currNode = _allNodes param [(_currNode param [1])]; }; _solution pushBack _startNode; // reverse it to get start point first and end point last reverse _solution; _allNodes resize (count _solution); { _allNodes set [_forEachIndex, _x]; } forEach _solution; // DEBUG _notext = " "; _text = "Solution Nodes:"; diag_Log _text; diag_log _allNodes; diag_log _notext; // DEBUG diag_log Output at end of script is: 7:03:17 "Solution Nodes:" 17:03:17 [0,2,3] diag log of initserver.sqf after script is ran is this: 17:03:17 "Nodes after script" 17:03:17 [0,1,2,3] As you can see, the "Nodes after script" are not the same as the "Solution Nodes" inside the script. I looked at it nearly a day and I don't get it... please help 🙂 SOS... 1 Share this post Link to post Share on other sites
JB47394 30 Posted April 26, 2019 In your script, you have the line _allNodes = _allNodes apply... Apply will create a new array which is then assigned to the local variable _allNodes. After that, the caller's array is never touched again. Instead, You have to modify the existing array. So use a forEach on _allNodes and fiddle with the array contents. 1 1 Share this post Link to post Share on other sites
sarogahtyp 1104 Posted April 26, 2019 @JB47394 Thank you for your fast reply. 2 minutes ago, JB47394 said: Apply will create a new array Are you sure? I doubt that this is the case but I can't proof currently. Share this post Link to post Share on other sites
JB47394 30 Posted April 26, 2019 1 minute ago, sarogahtyp said: Are you sure? Absolutely sure. 1 Share this post Link to post Share on other sites
sarogahtyp 1104 Posted April 26, 2019 2 minutes ago, JB47394 said: Absolutely sure. yeah I tested it. You are right, sadly. Wasn't the answer I'd liked to get but better a bad news which is a solution than vice versa. Thx a lot. Share this post Link to post Share on other sites
