challenge Calculate Shortest Path between 2 Nodes

[johnnyboy 3801]

Ok scripting gurus, we have another challenge for you.  I'm working on an AI Scripted Path script to run an AI or AI team through a series of positions in buildings or anywhere else.  And @madrussian is working on a badass script to map out all the nodes within any building.  The 3rd piece we need is a script to calculate a path between 2 nodes.  Path algorithms are well defined and can be found on the web.  I like this particular site because it has a well defined example with expected outcomes:    http://hansolav.net/sql/graphs.html

 

I've put their example data into 2 SQF arrays;

Spoiler

_nodes =
[
// Node, Name
[1,"Seattle"],
[2,"San Francisco"],
[3,"Las Vegas"],
[4,"Los Angeles"],
[5,"Denver"],
[6,"Minneapolis"],
[7,"Dallas"],
[8,"Chicago"],
[9,"Washington DC"],
[10,"Boston"],
[11,"New York"],
[12,"Miami"]
];
_connections =
[
// FromNode, ToNode, Distance
[1,2,1306],
[1,5,2161],
[1,6,2661],
[2,3,919],
[2,4,629],
[3,4,435],
[3,5,1225],
[3,7,1983],
[5,6,1483],
[5,7,1258],
[6,7,1532],
[6,8,661],
[7,9,2113],
[7,12,2161],
[8,9,1145],
[8,10,1613],
[9,10,725],
[9,11,383],
[9,12,1709],
[10,11,338],
[11,12,2145]
];

 

All you have to do is implement the algorithm to find the path between 2 nodes.  The expected results are in that website, so when your code calculates the same results, you know it works.  Your code should read the above sample input arrays, and calculate the same path as found in the web link.

 

Any takers?

Bonus Challenge:  Calculate shortest path that touches all nodes.   To clear a building, we need to sweep all rooms...that is different than shortest path between 2 nodes.  We need to calculate shortest path that allows us to touch all nodes.   I'll search for an algorithm for that also.  Basically we choose an entry point (starting node), and go from there.

 

[phronk 905]

_d = [];

_nodes=[all,my,nodes,here];

_currentNode=curNode;

_nodes apply { _d pushBack( _x distance curNode; ); };

 

_nodes sort true;

 

_closestNode=_nodes # 0;

 

 

Something like that maybe? PS: I'm at work so I speed coded it, not sure how well it'll work.

[johnnyboy 3801]

Hacker!  🤠  I'm Tom Sawyer-ing out this task man.  Go for it Phronkster!

[pierremgi 4940]

If you don't want that this topic loops around "the shortest path between two points is the straight line", you need to define what you want first.

I'm not sure you want to "travel" from nodes to nodes everywhere in every rooms, wandering without aim.

Do you intend to run a script (with animation and/or else) between two close nodes, and progress from node to node, from center of a room to a door (or reverse)?

But, if It's the case, why creating so much nodes? On my mind, a center node on each room, a center node on each door/issue should do the trick, then you can truncate the path with intermediate nodes.

 

Also, if you have to "ping" for obstacle(s) (if any), you'd rather scout for line Intersect.

I scripted (three years ago) a little addon to check on map if an enemy could see you, in regard of the relief. I called that enhanced map but on my mind, the principle could be the same: Is there a free "path" between center room and door?, if not where is the best clear line? You can see some visual intersect results "on the fly" in this video (first min.)

[Muzzleflash 111]

UPDATE: You might just want to wait it out. See .kju post below. Path finding is really one of those things you want the engine to do the grunt work of.

 

---------------------------------------------------------------------

 

Graph problems are a vast area with plenty of theoretical and practical considerations.

 

For your basic problem, there are many simple algorithms to find a path between two nodes. You might be able to do all you want using just a single algorithm.

 

11 hours ago, johnnyboy said:

through a series of positions in buildings or anywhere else

Define "anywhere else". Search algorithms that work for enclosed areas are often not so good for open areas and vica versa.

 

So I would advise the following considerations:

- I assume you are running this in SQF, so you might avoid doing calculations that could be done ahead of time.

- How many nodes are there? What is the typical and the max?

- I am guessing these nodes are particular to a specific building model/class

 

And regarding your bonus challenge: you may want to relax that it is the shortest, and rather just have it be one of the shorter but not necessarily the best. This depends again on how many nodes, but the problem is known as the Travelling salesman problem which is well studied. Basically for around ~30 nodes it is just not practical anymore.

 

If you have say, at most 20 nodes, you might just want to compute the best way to get to *any* destination, e.g. where to go next. For 20 nodes you just have to fill an 20*19/2 = 190 element array (a matrix). So you are at node #5 and want to get to #17. You look up in the array for #5 and destination #17 and it says #9. You go to #9, and look up again for #17 and it says #2. You go to #2, and it says #17, you go to #17. Congratulations you have arrived at your destination. The benefits of this approach is you don't really need to "compute" in SQF, you just look up so it is much faster. Though this approach does not scale so well 30 nodes might be doable too, but 100 nodes will require almost ~5000 elements in the array (this might actually also be doable....).

 

If you only have a few nodes you are starting/ending from, and most are just "intermediates", then you can use an even smaller array.

 

For you bonus challenge, I humbly suggest using a minimum spanning tree instead and walking around that instead. Some time ago for fun I tried that approach to create patrolling waypoints. In this example, the outer blue circle is the area to be observed, the red circles are "subtasks" making up teh area. The black dots, which are the waypoints, are placed first in each of the red circled areas, and indicates places with decent vegetation/concealment the problem should go to and observe from. Then the green lines indicate the minimum spanning tree, to reduce travelling times.
https://imgur.com/a/9CBkg

[stanhope 412]

Quick google search for Dijkstra's algorithm brings me to:

https://github.com/H0neyCake/findRoute

https://armaworld.de/index.php?thread/3885-navigation-system-featuring-dijkstra-algorithm/&postID=35249

 

 

[.kju 3245]

make sure to check out in dev branch:

 

Added: calculatePath script command

Added: PathCalculated entity event handler

 

reyhard

startCoordinates: Array - format [x,y,z]
endCoordinates: Array - format [x,y,z] 
typeName: string - vehicle class ("helicopter", "plane", "man", "car', "wheeled_APC", "tank", "boat")
behavior: string - ("CARELESS", "SAFE", "AWARE", "COMBAT" and "STEALTH")

 

it's exposing AI path planning algorithms

imagine sort of fake AI car which is going from A to B

this command will return such paths without need to prerecord it somehow

and PathCalculated is returning AI path

 

 

more in the arma discord at: https://discordapp.com/channels/105462288051380224/105466812870713344/568719347523256321

[madrussian 347]

@.kju

Wow, that totally just blew my mind!  Imagine all the possibilities.

[johnnyboy 3801]

2 hours ago, .kju said:

Added: calculatePath script command

Added: PathCalculated entity event handler

Thanks much .kju.  These are exciting developments!

[johnnyboy 3801]

13 hours ago, pierremgi said:

I'm not sure you want to "travel" from nodes to nodes everywhere in every rooms, wandering without aim.

Do you intend to run a script (with animation and/or else) between two close nodes, and progress from node to node, from center of a room to a door (or reverse)?

But, if It's the case, why creating so much nodes? On my mind, a center node on each room, a center node on each door/issue should do the trick, then you can truncate the path with intermediate nodes.

Hi Pierre.  As you describe, we hope to have already calculated the minimum nodes necessary to navigate a building (room centers and doors).  We will also have already stored the distances per each pair of adjacent nodes.  We then pick a start point and end point, and the algorithm calculates the path (the sequence of nodes) to travel to get from start to end.

 

The second algorithm we want is the shortest path to visit all rooms once from a given start point.

13 hours ago, pierremgi said:

Also, if you have to "ping" for obstacle(s) (if any), you'd rather scout for line Intersect.

I scripted (three years ago) a little addon to check on map if an enemy could see you, in regard of the relief. I called that enhanced map but on my mind, the principle could be the same: Is there a free "path" between center room and door?, if not where is the best clear line? You can see some visual intersect results "on the fly" in this video (first min.)

Initially, I think we won't bother with pinging for obstacles in buildings. The only blockers would be units (vehicles can't be abandoned inside buildings).  Later we may get more sophisticated and try to ping for obstacles.  I'll check out your addon.  Thanks.

4 hours ago, Muzzleflash said:

Define "anywhere else". Search algorithms that work for enclosed areas are often not so good for open areas and vica versa.

"anywhere else" refers to my script using a pre-defined path to go anywhere, and actually has nothing to do with path calculation (sorry for the confusion).

 

4 hours ago, Muzzleflash said:

So I would advise the following considerations:

- I assume you are running this in SQF, so you might avoid doing calculations that could be done ahead of time.

- How many nodes are there? What is the typical and the max?

- I am guessing these nodes are particular to a specific building model/class

@madrussian is calculating the minimum nodes necessary to navigate a particular building class (minimum will likely include doors + each room center + ?).  We then calculate paths per entry point for sweeping house.  I appreciate all your suggestions on how best to calculate those paths, and hope whoever takes on this challenge takes that into consideration.  I know there are many algorithms out there, and we really only need one that works well enough. These building aren't that big so any of the algorithms would probably suffice I'm guessing.

 

4 hours ago, stanhope said:

Quick google search for Dijkstra's algorithm brings me to:

Thanks man.  I saw those too.  I'm hoping for someone to implement one of these algorithms in SQF.  I chose the link provided in top post because it clearly states the problem, and provides a simple test data set, with expected outcomes.  This should make it easiest for someone to write and test their SQF solution.

[.kju 3245]

could be handy: https://github.com/Spiderswine/Arma3Navigation

[cb65 86]

12 minutes ago, .kju said:

could be handy: https://github.com/Spiderswine/Arma3Navigation

Thanks heaps .kju.

[gc8 981]

Arma 2 also had a-star script somewhere...

[sarogahtyp 1109]

I'm working on an A* search algorithm script but it's necessary to have a list of distances from each node to the endnode to get the heuristics of this algorithm work.

So @johnnyboy you (may) have to provide such list :-)

 

Also the lists you already provide have a not ideal format. I ve to reformat em to get it work.

An ideal format would look alike:

[
  [Node ID1, endDist, [toNodeList], [fromNodeList]], 
  [Node ID2, endDist, [toNodeList], [fromNodeList]], ... 
  [Node IDn, endDist, [toNodeList], [fromNodeList]]
 ];

// toNode/fromNode lists should have the format 
 [
  [ID1, weight], 
  [ID2, weight], ... 
  [IDn, weight]
 ];

 

This is not such important because I ve a function to reformat your lists into this format.

Much more important is a list with distances to  the goal or the A* cant work.

Another option is to switch from your pseudo example lists to arma and use positions instead of city names and distances instead of weights. In that case I can get the distances by myself. I think this would be best.

 

EDIT: Also your weights should be distanceSqr values then ...

 

[johnnyboy 3801]

35 minutes ago, sarogahtyp said:

I'm working on an A* search algorithm script but it's necessary to have a list of distances from each node to the endnode to get the heuristics of this algorithm work.

So @johnnyboy you (may) have to provide such list 🙂

Hey Saroga, I'm glad you're taking an interest in this.  My top post has a very simplified array structure with a list of nodes, and a list of node pairs with distances. I'm pretty sure that is the standard input information required for path calculation.  Besides distances, the node-to-node pairs provide the linkage between nodes.

 

I don't understand the format you are suggesting, we will only have the basic data to start with (list of nodes, and node-to-node pairs with distance).  From that you can calculate chains of nodes to get from point A to point B. 

[sarogahtyp 1109]

33 minutes ago, johnnyboy said:

Hey Saroga, I'm glad you're taking an interest in this.  My top post has a very simplified array structure with a list of nodes, and a list of node pairs with distances. I'm pretty sure that is the standard input information required for path calculation.  Besides distances, the node-to-node pairs provide the linkage between nodes.

 

I don't understand the format you are suggesting, we will only have the basic data to start with (list of nodes, and node-to-node pairs with distance).  From that you can calculate chains of nodes to get from point A to point B. 

 

this is nearly correct but we have to agree the data structure and not use a pseudo structure of city names and weights...

your node list should look like:

[
 [Node ID1, position],
 [Node ID2, position], ...
 [Node IDn, position]
]

Node ID would be the number to identify each node as you already have it in your pseudo lists.

position should be a 3D position value [x, y, z] and you have to tell which position format  you prefer.

 

your connection list should look like

[
 [fromNodeID, toNodeID, distanceSqr],
 [fromNodeID, toNodeID, distanceSqr], ...
 [fromNodeID, toNodeID, distanceSqr]
]

this is exactly as you already have it except the distance values.

there we have 2 option:

1. you provide distanceSqr here or

2. you only provide fromNodeID and toNodeID and I calculate the distanceSqr by myself.

 

My intention is just to talk about compatible formats. With such agreement I can take this into account while writing the script.

 

EDIT: with "provide" I just mean to provide it on runtime. Your opening post is good as it is...

Edited April 24, 2019 by sarogahtyp

[johnnyboy 3801]

OK, we are close to agreement.  The example in top post contained "city names" instead of 3D positions.  I made the data in top post match the algorithm link I posted so that whoever built a function would have standard test input to use, with pre-determined calculated correct answers to compare their test results against.  Below I modified this same test data to replace CityName with an empty position array.  The path finding function only cares about NodeIDs for first array (and has no real use for node Position, as its not needed to calculate path).  And you also have the array I called "_connections" which is simply FromNodeID, ToNodeID, + Distance. 

 

Ultimately the node arrays will carry more columns like BuildingClassName, Floor#, isDoor, isStairs, isWindow, isEntrance, doorDir, etc.  But none of that information will be needed for Shortest Path calculation.  What I hope to do is read  the node arrays provided by MadRussian's algorithm, and create the stripped down arrays (NodeID Array, and Node Pairs Array) to pass to the Shortest Path function.  The Shortest Path function then returns a simple list of IDs in shortest path sequence.  Since I do not know the final Node array format yet, we can keep the interface to Shortest path function reduced to only the bare minimum data needed for path calculation.  Does that make sense to you?

Spoiler

_nodes =
[
// Node, position
[1,[]],
[2,[]],
[3,[]],
[4,[]],
[5,[]],
[6,[]],
[7,[]],
[8,[]],
[9,[]],
[10,[]],
[11,[]],
[12,[]]
];
_connections =
[
// FromNode, ToNode, Distance
[1,2,1306],
[1,5,2161],
[1,6,2661],
[2,3,919],
[2,4,629],
[3,4,435],
[3,5,1225],
[3,7,1983],
[5,6,1483],
[5,7,1258],
[6,7,1532],
[6,8,661],
[7,9,2113],
[7,12,2161],
[8,9,1145],
[8,10,1613],
[9,10,725],
[9,11,383],
[9,12,1709],
[10,11,338],
[11,12,2145]
];

 

 

[sarogahtyp 1109]

12 minutes ago, johnnyboy said:

and has no real use for node Position, as its not needed to calculate path

 

this is not correct. to get an idea of a good path and not to calculate every possible path A* uses a heuristic to determine which way could be the best. to feed this heuristic A* needs a weighting value. This value should be the direct distance between every node and the end node. I am only able to calculate this distance if I have the positions of all Nodes. Also if I have those positions then I'm able to get the distances of the connections array by myself.

 

So my suggestion is to provide the positions in the nodes array and not provide the distances in the connections array.

And again, you have to tell which position format to use...

[johnnyboy 3801]

Ok.  Dijkstra's algorithm doesn't need that extra information.  I don't have a sample like that ready.  My AI Movement script is using hard-coded paths for testing (I don't have node pairs and distances), so maybe you can find a sample set online for a test (like I posed for Dijkstra's algorithm), or just create your own simple input set in the format you need.

 

Once we have Nodes and Node Pairs from MadRussian, we should be able to calculate the extra information you are asking for, before calling your A* function.

 

Since we are only talking about path finding for Arma buildings, the universe of possible nodes and paths will be relatively small per building, so we only need the simplest path finding function IMO.

 

To be honest, I don't understand why distances between all node combinations would be relevant in our case.  If you start at a first floor door, and the end point is a window on 3rd Floor, how could the distance between those 2 points be relevant?   We can only reach the 3rd floor by traveling between a series of linked nodes.  So the distance from 1st Floor door to 3rd Floor window would not be relevant (plus it might be misleading as the 3D distance between those points might be short if window is directly 2 floors above door).

[sarogahtyp 1109]

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)


5.   boolean - Oneway - do we have Oneway connections? true means we have such. false means not.

   Return Value - 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;

// DEBUG
_notext = " ";
_text = "Input Nodes:";
diag_Log _text;
diag_log _allNodes;
diag_log _notext;

_text = "Input Connections:";
diag_Log _text;
diag_log _allConnections;
diag_log _notext;
// DEBUG

//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]
};

// DEBUG
_notext = " ";
_text = "Rearranged Nodes:";
diag_Log _text;
diag_log _allNodes;
diag_log _notext;

_text = "Rearranged Connections:";
diag_Log _text;
diag_log _allConnections;
diag_log _notext;
// DEBUG

_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)
 _currentNode = _allNodes param [0];
 _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;};

// DEBUG
_notext = " ";
_text = "After loop Nodes:";
diag_Log _text;
diag_log _allNodes;
diag_log _notext;

_text = "After Loop Connections:";
diag_Log _text;
diag_log _allConnections;
diag_log _notext;
// DEBUG

// 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]
};

// DEBUG
_notext = " ";
_text = "Rearranged Nodes:";
diag_Log _text;
diag_log _allNodes;
diag_log _notext;
// DEBUG

_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;

// DEBUG
_notext = " ";
_text = "Solution array:";
diag_Log _text;
diag_log _solution;
diag_log _notext;
// DEBUG

// reverse it to get start point first and end point last
reverse _solution;

// DEBUG
_notext = " ";
_text = "reversed Solution:";
diag_Log _text;
diag_log _solution;
diag_log _notext;
// DEBUG

_allNodes resize (count _solution);

// DEBUG
_notext = " ";
_text = "Nodes resized:";
diag_Log _text;
diag_log _allNodes;
diag_log _notext;
// DEBUG

{
 _allNodes set [_forEachIndex, _x];
} forEach _solution;

// DEBUG
_notext = " ";
_text = "Solution Nodes:";
diag_Log _text;
diag_log _allNodes;
diag_log _notext;
// DEBUG

 

 

[johnnyboy 3801]

2 minutes ago, sarogahtyp said:

Okay, I ll just write it as I think and u ll deliver what needed on runtime...

Sounds great.  I appreciate it!

[sarogahtyp 1109]

i thought bout best way to clear a house:

1. use traveling salesman algorithm to get best way through all rooms

this should be done with all specific building positions like doors, windows, stairs etc.

 

2. use shortest path to get from a door to the next door or from stairs start point to stairs end point.

this time all possible positions of the specific room or all points of the stairway should be provided.

 

with this you can first get the way through the house and then avoid all obstacles of each room...

[johnnyboy 3801]

6 hours ago, sarogahtyp said:

i thought bout best way to clear a house:

1. use traveling salesman algorithm to get best way through all rooms

this should be done with all specific building positions like doors, windows, stairs etc.

 

2. use shortest path to get from a door to the next door or from stairs start point to stairs end point.

this time all possible positions of the specific room or all points of the stairway should be provided.

 

with this you can first get the way through the house and then avoid all obstacles of each room...

Sounds good.  Due to limitations of AI control, I'm thinking the starting set of nodes is trimmed to bare minimum of doors/passages, room centers, base of stairs, stair landings, top of stairs, bottom of ladder, top of ladder.  "center of room" should be a point that has visibility to entire room.  If distances between linked bare minimum nodes are > 3 meters, I may insert additional intermediate node, because AI can't fight while moving with my script, but they can fight at each node (if enemy perceived, they stop and fight).  All linked positions/nodes, must have unobstructed line of sight between the nodes for AI to move from point to point without ghosting thru walls.  All these calculated points would be based on a bare room.  I don't plan to support maneuvering around placed furniture in any early release.   If we keep paths toward room centers it shouldn't be too much of a problem.  For example, Phronk's furniture script considers AI paths, and purposely places furniture to not block AI.  If a mission designer barricades stairs with furniture, then AI path is f***ed.  That's just a limitation.  I'm not even 100% sure I can get a team to navigate an empty room and look good while doing it, much less navigate around furniture.  Baby steps my friend!

 

[pierremgi 4940]

4 hours ago, johnnyboy said:

Ok.  Dijkstra's algorithm doesn't need that extra information.

 

To be honest, I don't understand why distances between all node combinations would be relevant in our case.  If you start at a first floor door, and the end point is a window on 3rd Floor, how could the distance between those 2 points be relevant?   We can only reach the 3rd floor by traveling between a series of linked nodes.  So the distance from 1st Floor door to 3rd Floor window would not be relevant (plus it might be misleading as the 3D distance between those points might be short if window is directly 2 floors above door).

 

Dijkstra's algorithm doesn't seem to be ok for blind (no issue) paths. I took some time on it. In your case (visiting a house), you need to cope with some blind paths, so "return tickets" and, even without these specifics nodes, a "simple" 10 nodes case can take several seconds to be treated (exponential). Roughly, for n nodes, it's difficult to avoid n^3 cases (not square but cube).

 

It's a very good thing to truncate a building in floors. But x^3 nodes * y floors * z houses... At what time do you calculate that?

[johnnyboy 3801]

52 minutes ago, pierremgi said:

Dijkstra's algorithm doesn't seem to be ok for blind (no issue) paths. I took some time on it. In your case (visiting a house), you need to cope with some blind paths, so "return tickets" and, even without these specifics nodes, a "simple" 10 nodes case can take several seconds to be treated (exponential). Roughly, for n nodes, it's difficult to avoid n^3 cases (not square but cube).

 

It's a very good thing to truncate a building in floors. But x^3 nodes * y floors * z houses... At what time do you calculate that?

Thanks Pierre.  Full disclosure:  I don't know d*** about calculating paths, and am terrible at math in general.  So I trust you guys' input on this.  Once we have nodes defined for buildings, we will try realtime path calculation for building paths.  If that is too slow, then we will have to run the path calculations per building and store them in an array library to include with the script set/mod (so at game run-time, all building search paths have been pre-calculated).