Navigation System featuring Dijkstra-Algorithm

Recommended Posts

Hey Folks,

recently i was playing a bit with setting up the dijkstra algorithm in arma.

With the following code you will be able to navigate from your position to a marker on the map.

Have Fun!

Video Tutorial:

Parts of the Algorithm:

• Create Road Map, Gets all connected roads on the map and save them in an array
• Run the Dijkstra Algorithm, Defines the graph for the RoadMap with recent starting point

• Finding the Path, Gets the position of the destination marker on the map and finds the shortest path
• Create Local Markers, Create markers for every path node
• Delete Markers on Passing, When passing the navigation markers they will be deleted from the gui

```// Create Road Map

_iterationCounter = 0;

while {_iterationCounter < 1000} do
{

{
_distance = _x distance _nextRoad;

if((_finishedRoads find _x) == -1) then
{
};

_iterationCounter = _iterationCounter +1;
};```

Run the Dijkstra Algorithm

```// Run the Dijkstra Algorithm

// Init Distances
_distanceArray = [];
_workQueue = [];

_distanceArray pushBack [_startRoad, 0, null];

_workQueue pushBack [0, _startRoad];

while { count _workQueue > 0} do
{
_workItem = _workQueue deleteAt 0;
_actualRoad = _workItem select 1;

// Get the connected Roads out the RoadMap
{
_road = _x select 0;
_connRoad = _x select 1;
_connDistance = _x select 2;

{

// Calculate Distance between the Roads

// Search for Parent in Distance Array and get his Distance
{
_parentRoad = _x select 0;
_parentDistance = _x select 1;
_parentParent = _x select 2;

{
_roadDistance = _roadDistance + _parentDistance;		// Add distance of parent to new distance
};

} foreach _distanceArray;

// Save new Road in Distance Array
};

if(count _workQueue  > 0) then {_workQueue sort true;};
};```

Finding the Path

```// Now Finding the Shortest Path to Destination
_destinationPath = [];
_destinationLength = 0;

_startNode = _distanceArray select 0;

// Get the Destination Node from Marker
_destinationMarker = allMapMarkers select ((count allMapMarkers) -1);

_nearestDestinationRoad = (getMarkerPos(_destinationMarker) nearRoads 10) select 0;

_selectedNode = [];

// Find DestinationRoad in Array
{
_nodeRoadx = _x select 0;

{
_selectedNode = _x;
}
} foreach _distanceArray;

// Get the Distance to Destination
_destinationLength = _selectedNode select 1;

diag_log format ["StartNode: %1, SelectNode: %2, DestinationLength: %3", _startNode, _selectedNode, _destinationLength];

// Get the Path to Destination
while{!(_selectedNode isEqualTo _startNode)} do
{
_nodeRoad = _selectedNode select 0;			// Select the Road in the Node
_destinationPath pushBack _nodeRoad;		// Save the Road in the Path
_nodeParent = _selectedNode select 2;		// Node Parent to find

// Find Node Parent in Distance Array
{
_nodeRoadx = _x select 0;

if(_nodeRoadx == _nodeParent) then
{
_selectedNode = _x;
}
} foreach _distanceArray;
};

_destinationPath pushBack (_startNode select 0);```

Create Local Markers

```// Create Local Markers to navigate to the path
{
_streetMarker = "VR_3DSelector_01_exit_F" createVehicleLocal getPos(_x);
// _mapMarker = createMarkerLocal ["markername",[getPos(_x select 0) select 0,getPos(_x select 0) select 1]];
// _mapMarker setMarkerShapeLocal "ICON";
// _mapMarker setMarkerTypeLocal "DOT";
} foreach _destinationPath;```

Delete Markers on Passing

```// Delete Local Markers when passing them
[] spawn {
while{true} do
{
_nearestObjects = nearestObjects [player, [], 10];
{
if(typeOf _x == "VR_3DSelector_01_exit_F") then
{
deleteVehicle _x;
}
} foreach _nearestObjects;
sleep 0.1;
}
}```

Edited by Spiderswine
Update for Full Function
• 5
• 1

Share on other sites

this might be useful to you:

thanks for sharing the script!

• 1

Share on other sites

Thanks for posting, but my aim was to set up a navigation system for players on a server, luckely this works now a bit better ;)