Jump to content

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.

UMT9v1B.png

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

 

 

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

  • Like 6
  • Thanks 7

Share this post


Link to post
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).

  • Like 2

Share this post


Link to post
Share on other sites

I love this stuff ūüôā There is a lot to learn here!¬†

 

 

  • Like 2

Share this post


Link to post
Share on other sites

Performance Update

 

Changelog

v 1.1 (Download SQF)

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

  • Like 2

Share this post


Link to post
Share on other sites

Update

 

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

  • Like 2
  • Thanks 2

Share this post


Link to post
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
  • Like 6

Share this post


Link to post
Share on other sites

Just in case - maybe worth comparing:

 

 

 

  • Like 2
  • Thanks 1

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

  • Like 1

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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!

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now

√ó