# shortest path [RELEASE] Sarogahtyps Simple Shortest Paths - SSSP V-2.0

## Recommended Posts

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:

Spoiler
```
/*
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

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; 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; false};
// determine arguments 3. and 4. format
private _alternativeFormat = count _firstElementConnections isEqualTo 3;

private _solution = [];
private _sqrt2 = 1.41421;

//set maximum possible squared distance
private _maxDist = (worldSize * _sqrt2)^2;

//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
{
_fromID = _x select 0;
_toID = _x select 1;
_fromPos = (_allNodes select _fromID) select 1;
_toPos = (_allNodes select _toID) select 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

{
_nodeID = if(typeName _x isEqualTo "ARRAY") then {_x select 0} else {_x};
_dist = if(_nodeID isEqualTo _startNode) then {0} else {_maxDist};
_allNodes set [_forEachIndex, [_dist, _maxDist, false, _nodeID]];
} forEach _allNodes;

_solutionFound = false;

// define a name for the script scope to be able to break all loops
scopeName "main";

while {true} do
{
// select node with shortest distance value (_allNodes is sortet ascending by distance)
private _shortest = _maxDist;
private _currentNode= [];

{
if (!(_x select 2) && {(_x select 0) < _shortest}) then
{
_shortest = _x select 0;
_currentNode = _x;
};
} count _allNodes;

//if there is no unviewed node then break all scopes - no solution possible
if (_currentNode isEqualTo []) then {breakTo "main"};

_currID = _currentNode select 3;

// 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 select 1 isEqualTo _currID) || (_x select 2 isEqualTo _currID)
};

//get all not viewed neighbors of current node
_neighbNodes = _allNodes select
{
private _neighbID = _x select 3;
(!(_x select 2) && (_neighbConns findIf {(_x select 1 isEqualTo _neighbID) || (_x select 2 isEqualTo _neighbID)} > -1))
};

//process all neighbor nodes of current node
{
private _neighbID = _x select 3;

// find the index of the connection between current node and this neighbor node
// get distance value of the connection

private _thisDist = (_currentNode select 0) + ((_neighbConns select (_neighbConns findIf {_neighbID isEqualTo (_x select 1) || _neighbID isEqualTo (_x select 2)})) select 0);

// if we found a shorter distance then set current node as predecessor of this neighbor node and update the found distance for it
if ( (_x select 0) > _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;
};

//exit if there is no solution for the given nodes/connections set to get from start node to end node
if (!_solutionFound) exitWith {_allNodes = true; true};

{
_allNodes set [_forEachIndex, [(_x select 3), (_x select 1)]];
} forEach _allNodes;

_allNodes sort true;

// build solution path array from end node to start node
private _currNode = _allNodes select _endNode;

while {!((_currNode select 0) isEqualTo _startNode)} do
{
//current nodes ID is part of solution
_solution pushBack (_currNode select 0);

//next current node is predecessor of actual current node
_currNode = _allNodes select (_currNode select 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;

_solution```

Â

Â

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:

Â

Spoiler
```
private _nodeThings = [3,1,0,2];
private _nodeThings2 = [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 spawn";
diag_Log _text;
diag_log _nodeThings;
diag_log _notext;
// DEBUG

_solution = [0, 3, _nodeThings2, [[10, 0, 1], [9,0,2], [15, 1, 3], [5, 2, 3]]] call saroSSSP_fnc_shortPathDijkstra;

// DEBUG
_notext = " ";
_text = "Nodes after call";
diag_Log _text;
diag_log _solution;
diag_log _notext;
// DEBUG```

Â

Â

Â

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

Spoiler
```
/*
Author: Sarogahtyp
Title: SSSP(A) - Sarogahtyps Simple Shortest Path - A*-algorithm
https://en.wikipedia.org/wiki/A*_search_algorithm

Description: A*-algorithm - sqf implementation
This algorithm is much faster than -Dijkstra algorithm but currently support not more than one floor/layer

Arguments: Precalculated distances are not supportet here as A* doesn't need more than a few distances.
It would be just senseless to hold all probably needed distances in memory.

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

4.  array - connections list - format: [[fromID, toID], [fromID, toID], ..., [fromID, toID]]
fromID - number, connections start node ID
toID - number, connections end node ID

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

// check for valid parameter data types
if (!_correctList) exitWith {_allNodes = false; false};

//check if first element of _allNodes is an array with exact 2 elements
private _correctNodes = _allNodes params [["_firstElementNodes", objNull, [[]], [2]]];

//check if first element of _allConnections is an array with 3 elements
private _correctConnections = _allConnections params [["_firstElementConnections", objNull, [[]], [2]]];

// exit if at least one of both first elements has wrong format
if (!_correctNodes || !_correctConnections) exitWith {_allNodes = false; false};
// determine arguments 3. and 4. format

private _tempNode = _startNode;
_startNode = _endNode;
_endNode = _tempNode;
_tempNode = nil;

#ifndef SQRT2
#define SQRT2 1.41421
#endif

//set maximum possible squared distance
private _maxDist = (worldSize * SQRT2)^2;
private _maxDistDoubl = 2 * _maxDist;

// store f-value (heuristic sum) - Predecessor ID - g-value (real sum) - Node ID - Node Position

_allNodes sort true;
private _openList = [[0, _maxDist, 0, (_allNodes select _startNode select 0)]];

private _closedList = [];
private _currentNode = _maxDist;

// define a name for the script scope to be able to break all loops
scopeName "main";
_solutionFound = false;

while {true} do
{
private _shortestHeuristic = _maxDistDoubl;
private _shortestReal = _maxDist;

// get node with best f-value (heuristic sum)
{
if ((_x select 0) < _shortestHeuristic) then
{
_shortestHeuristic = _x select 0;
_currentNode = _x;
};
} count _openList;

private _openNum = count _openList;

//if the open list is empty then break all scopes - no solution possible
if (_openNum isEqualTo 0) then {breakTo "main"};

private _currID = _currentNode select 3;

//delete current Node from open list and add it to closed list
//_openList = _openList - _currentNode;

_d = _openList deleteAt (_openList findIf {(_x select 3) isEqualTo _currID});

_closedList pushBack [(_currentNode select 3), (_currentNode select 1)];

// break to script scope if solution is found
if (_currID isEqualTo _endNode) then
{
_solutionFound = true;
breakTo "main";    //breaks all scopes except main scope
};

//get all connections to all neighbors of current node
_neighbConns = _allConnections select
{
(_x select 0 isEqualTo _currID) || (_x select 1 isEqualTo _currID)
};

//get all neighbors of current node which are not on closed list
_neighbNodes = _allNodes select
{
private _neighbID = _x select 0;
((_closedList findIf {(_x select 0) isEqualTo _neighbID} isEqualTo -1) &&
(_neighbConns findIf {(_x select 0) isEqualTo _neighbID || (_x select 1) isEqualTo _neighbID} > -1))
};

{
private _neighbID = _x select 0;

_tentative_g = (_currentNode select 2) + ((_allNodes select _currID select 1) distanceSqr (_allNodes select _neighbID select 1));
_neighInOListIndex = _openList findIf {(_x select 3) isEqualTo _neighbID};
_heurDist = (_allNodes select _endNode select 1) distanceSqr (_allNodes select _neighbID select 1);

if (_neighInOListIndex > -1) then
{
if (_tentative_g < (_openList select _neighInOListIndex select 2)) then
{
_d = _openList set [_neighInOListIndex, [(_tentative_g + _heurDist), _currID, _tentative_g, _neighbID]];
};
}
else
{
_d = _openList pushBack [(_tentative_g + _heurDist), _currID, _tentative_g, _neighbID];
};
} count _neighbNodes;
};

//exit if there is no solution for the given nodes/connections set to get from start node to end node
if (!_solutionFound) exitWith {_allNodes = true; true};

// build solution path array from end node to start node

private _currNodeIndex = _closedList findIf {(_x select 0) isEqualTo _endNode};
private _currNode = _closedList select _currNodeIndex;

_allNodes resize 0;

_allNodes pushBack (_currNode select 0);

while {!((_currNode select 0) isEqualTo _startNode)} do
{
_currNodeIndex = _closedList findIf {(_x select 0) isEqualTo (_currNode select 1)};
_currNode = _closedList select _currNodeIndex;

//current nodes ID is part of solution
_allNodes pushBack (_currNode select 0);
};

_allNodes```

Â

Â

Â

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

- minor performance optimizations on Dijkstra

- added demo mission which is able to compare both algorithms

Â

-performance optimizations - 65-70% less readability /Â 30-35% better performance

Â

- initial release

• 6
• 7

##### Share on other sites

That is a THOB! (THing of Beauty).Â  Thanks much Sarogahtyp.Â  Excellent work.Â  And your code reads beautifully.Â  Very cool that you provided 2 methods also (one with distances pre-calculated, and one not).

• 2

Demo mission:

Â

Demo video:

Â

• 5

##### Share on other sites

I love this stuff ðŸ™‚ There is a lot to learn here!Â

Â

Â

• 2

##### Share on other sites

Performance Update

Â

Changelog

-performance optimizations - 65-70% less readability /Â 30-35% better performance

• 2

##### Share on other sites

Update

Â

Changelog

- minor performance optimizations on Dijkstra

- added demo mission which is able to compare both algorithms

• 2
• 2

##### Share on other sites

A* vs. Dijkstra Videos - out of the demo mission using 20 - 2000 nodes and 64 - 6778 connections:

Spoiler

A* vs. Dijkstra - 20 nodes - 64 connections

Â

A* vs. Dijkstra - 50 nodes - 164 connections

Â

A* vs. Dijkstra - 100 nodes - 330 connections

Â

A* vs. Dijkstra - 150 nodes - 537 connections

Â

Â

A* vs. Dijkstra - 300 nodes - 1029 connections

Â

A* vs. Dijkstra - 600 nodes - 2066 connections

Â

A* vs. Dijkstra - 2000 nodes - 6778 connections

Â

Â

Edited by sarogahtyp
• 6

##### Share on other sites

Just in case - maybe worth comparing:

Â

Â

Â

• 2
• 1

##### Share on other sites
10 minutes ago, .kju said:

Just in case - maybe worth comparing:

Â

Â

Â

Â

Thank you for linking it. I think Dijkstra is not the best solution for a 2D-Map-Navi but I'll definitly look into it.

##### Share on other sites

Many thanks for this!Â  Quick question aboutÂ input parameters.Â  Should connections list include each connection both ways?Â  For example, if node1 is connected to node2, should connections list include just [fromID1,Â toID2]?Â  Or in this case,Â does connections list need bothÂ [fromID1,Â toID2] andÂ [fromID2,Â toID1]?

Â

Also, in case first choice is the correct (connections list needing justÂ [fromID1,Â toID2]), if you go ahead and provide both ([fromID1,Â toID2] andÂ [fromID2,Â toID1]), will this still work? ... And if so will it take significant performance hit?

Â

##### Share on other sites

For performance reasons I did decideÂ to not support oneway connections.

this mean that it isn't important if a connection is established from fromID to toID or vice versa. both will work and each connection listed in the array will be handled. you don't need to provide a connection twice.

Â

If you really think that oneway connections are important (like jumping out of a window where you cant go back) then just tell and I ll think about implementing it as an option.

• 1

##### Share on other sites

Thanks, good to know!Â  I don't particularly need one-way connections, now or for the foreseeable future.Â  Still curious though (after carefully reading your answer a couple of times):

Â

I understand now you support only two-way connections and that we only need to provide each connection once.Â  <- Considering this,Â will we hurt performance by providing each connection twice (one perÂ each way)?Â  (Because in my case it's easier to build an array of connections that includes each connection both ways...)Â  Hope thatÂ makes sense.

##### Share on other sites

idk, depends on how many connections you provide.

the performance hit will mainly come with this part of code (assuming u use dijkstra code):

``` _neighbConns = _allConnections select
{
(_x select 1 isEqualTo _currID) || (_x select 2 isEqualTo _currID)
};```

if u provide connections twice then the array _allConnections is double sized and the selection above should last longer.

this selection is done once for each provided node (maximum).

##### Share on other sites

Gotcha, that makes sense.Â  OKÂ if I have many nodes, I'll go ahead andÂ pairÂ it down to squeeze out max performance!