challenge Calculate Shortest Path between 2 Nodes

[sarogahtyp 1104]

2 algorithms 2 problems...AFAI understand:

Dijkstra - calculates a shortest path solution for all nodes until the end node shortest path is calculated. very time consuming but I ll do an implementation of it

 

A* - does it much better for 1 floor but if you have more floors then you ll probably get wrong (much longer) shortest path solutions. I think about to implement a stair detection in it and calculate shortest paths floorwise only.  but idk if I get that work.

 

@johnnyboy if u have some sample data of nodes (including positions as ASL format) and connections lists in future then it would be nice for me to have it 😉

 

EDIT: this is the data structur I ll need

Spoiler

	Arguments:
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)
			   nodes may provided unsorted cause they get sorted for IDs 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

 

 

[pierremgi 4737]

37 minutes ago, johnnyboy said:

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).

 

Sure, but so far, you're trying to  find the shortest way to go from ptA to ptB (algorithm),

But what about visiting a house? From entry A to entry A?, or B?.. or C?, visiting  all rooms, balconies...

 

I guess you need 1 (or n paths for n entries) from Entry_i to Entry_i (so a loop), to keep it simple.

 

Then, is there something to calculate (in this case, which parameters?) or just an array of points to follow?

I can imagine you can build library, spending time (but sparing it in fact) to travel with a player in houses. Then, two or three triggers:

radio A: add the player's relative position to building's center to an array for this house

radio B: start a new array (for floors), optional

radio C : new building, new center.

On the other hand, any unit will follow the same path (you can randomize 2 or 3 paths by recorded arrays).

If you remark that's more or less, the idea with unit capture/play functions.

[johnnyboy 3741]

14 minutes ago, pierremgi said:

Sure, but so far, you're trying to  find the shortest way to go from ptA to ptB (algorithm),

But what about visiting a house? From entry A to entry A?, or B?.. or C?, visiting  all rooms, balconies...

 

 I'd like to start with 2 functions:

• Shortest path between 2 nodes
• Traveling Salesman that visits all nodes

We don't have to pass in all building nodes when using these functions.  It  could be all, or could be just nodes for one floor.  We would now have building blocks to support various ai paths:

• Want group to just pass through building?  Then pass it Starting Entry Point, and a second Entry Point (for the Exit), and calculate the shortest path.  Now group passes through building, without going to second floor.
• Want to search floor by floor?  Call Traveling Salesman calculator passing in Floor 1 points only, then call it again passing it stairs and floor 2 points.
• In and out:   Pass in a start and end point to shortest path.  When group reaches end point, it follows the reverse path to exit building.
• Search all rooms, then use shortest path to exit:  Call Traveling Salesman.  When group visits last node in Traveling Salesman path, we then call Shortest path from this node to an Entry point to give AI shortest path to exit building.

31 minutes ago, pierremgi said:

If you remark that's more or less, the idea with unit capture/play functions. 

I will also support Mission Designer recorded paths for any building, or anywhere on map (the path AI followed in my 2 videos was using my custom paths).  Please note that I am NOT using unitCapture/UnitPlay.  Units cannot react to environment when using UnitPlay.  I use my own script to execute a move from point to point, and allow AI to fight at each point if they perceive an enemy.

[pierremgi 4737]

Just saying your calculations will issue (at the best!) the array you could simply define just by picking some points (and you already did it, I know). Your algorithm can be replaced by the way you'd picked  them visually in 3den to make paths... I'll not add any more comment about that. Let's go for your calculations.

[sarogahtyp 1104]

Dijkstra is done already:

A* (much faster) will follow and travelling salesman is planned as well 🙂

[sarogahtyp 1104]

On 4/24/2019 at 8:56 PM, pierremgi said:

... a "simple" 10 nodes case can take several seconds to be treated (exponential)...

 

hmm ... currently with 150 nodes and 350 connections I get runtimes around 10 seconds ... 

If I test less nodes and connections then it falls rapidly. I think it's much faster as you need for calculating the shortest path for some POI's in a house on runtime.

50 nodes with 165 connections take around 0.3 seconds.

[pierremgi 4737]

1 hour ago, sarogahtyp said:

 

hmm ... currently with 150 nodes and 350 connections I get runtimes around 10 seconds ... 

If I test less nodes and connections then it falls rapidly. I think it's much faster as you need for calculating the shortest path for some POI's in a house on runtime.

50 nodes with 165 connections take around 0.3 seconds.

Probably. I'm still interesting in how you will use that!

Imho, the shortest path & the quickest defined, for some POI's in house, stays... the array you decide.