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

[sarogahtyp 1105]

On 4/13/2022 at 5:37 AM, madrussian said:

I found your bug!  (99.9% sure now)

 

yes you found a bug but compared with the "squared distances bug" it was a minor issue. But I fixed this as well, thank you for your findings.

 

On 4/13/2022 at 5:37 AM, madrussian said:

I tried to fix yours up, but got confused,

huh, my code is confusing me all the time I try to read it. I just try to not give up^^

 

On 4/13/2022 at 5:37 AM, madrussian said:

So apparently the destination node doesn't technically have to become the current node to declare a solution, provided the other checks are completed.  Which is maybe how you were trying to implement?

Yeah I tried it that way but I did'nt read the description carefully enough. Now I think doing the nesseccary checks would consume more runtime than just calculating till the end node is reached.

 

On 4/13/2022 at 5:37 AM, madrussian said:

Regardless, hats off to you Sarogahtyp and many thanks for taking on this pathfinding stuff!  Your work is incredibly inspiring, and quite integral to much of what I'm working on lately. 🙏

That's too much credit for me. I'm just an old fool trying to sort out the gibberish in my head and write it into code.

 

40 minutes ago, johnnyboy said:

Its an honor to be associated with you super smart guys!

That's too much credit for me. I'm just an old fool trying to sort out the gibberish in my head and write it into code.

 

On 4/13/2022 at 5:37 AM, madrussian said:

what I'm working on lately

what are you working on? depending on the problem the A* algorithm could be much faster than dijkstra. In my latest tests using the version where the bugs are fixed I had A* always finding the same solution as dijkstra. In most cases A* is much faster. There are some cases when using multiple floors/layers where A* is much slower but although is finding the same solution as dijkstra...

[sarogahtyp 1105]

On 7/7/2021 at 5:03 PM, gc8 said:

The only thing I noticed was that fn_shortPathDijkstra.sqf takes the nodes list but it modifies the original array.

 

Edit: Another thing I noticed is that if the end node is not connected and the dijkstra  therefore fails to find the path then the return value of the function is not empty array but true (boolean)

 

 

ty for this script 🙂

 

Original array gets modified:

yeah this is true the original nodes array gets modified and will contain the solution. this is thought for spawning the script because if you spawn it then there is no return value.

 

true value if no solution is possible:

this is true as well and it is the way the script works.

true means no solution possible.

false means input data is not valid

 

I tried to descibe all of that in the header of my scripts but maybe that desciption was a little short.

 

[sarogahtyp 1105]

On 3/31/2021 at 2:13 AM, pierremgi said:

Interesting topic,... with this persistent question on my side:
 How can we use this tool?  I mean, in what manner that can change something in AIs behavior? Is this a project for some FSMs replacing Vanilla ones?

 

As I started this shortest paths thing there was no command like calculatePath and if you wanted to realize something like a navigation system then you needed a path finding algorithm. this is one use case but with the implementation of calculatePath it is obsolete because the engine solution is much faster.

Now it is only good for gimmicks that have nothing to do with the usual vehicle or unit routing.

 

 

On 3/31/2021 at 2:13 AM, pierremgi said:

About AI paths, I never released an advanced waypoint I made for visiting the houses within a radius. I failed on 2 big problems:

- the path between 2 positions (of a same house) can be inexistent, so the move fails;

- this kind of waypoint is supposed to work in combat mode, and the result is just... boring! For example, when AIs visit a military cargo tower (land_cargo_Tower_V1... and others), they often suicide jumping from top to ground, skipping stairs... One detail among myriad of others. I gave up.

This is a question for @madrussian and @johnnyboy because they worked on a solution for AIs behavior in buildings. but idk what they got in the end.

 

 

 

On 3/31/2021 at 2:13 AM, pierremgi said:

Here is a little video, for basic and starting conversation about paths.

- in open field, waypoints are calculated and calculatePath + EH "pathCaculated" show the result, along with the behavior, the type of vehicle... the roads... Nothing surprising when we read the BIKI page about waypoints and AI behaviors. The problems arise when scripters are not aware of what an obstacle can be for an AI.

A rock is a rock. A house is a house... But a fence, a destroyed fence, a wall, a destroyed wall... that's too much subtle, unfortunately.

 

inside houses, the ordered moves can be on existing positions only. Unfortunately here, the paths between these positions are not guaranteed. And if a path exists between 2 points in a same room!, there is no guarantee that way is the shortest (see video). No matter the behavior here, stealth or combat, you AI will follow the existing path (something to take into account if you plan to add some furniture in a room!)

 

I really hope your approach will issue one day an improvement for all of that.

my scripts are not thought for specific use cases or to improve AI-behavior. Its just pathfinding not more not less.

but as I told above @madrussian and @johnnyboy were working on something like that...

[madrussian 347]

On 4/14/2022 at 9:28 AM, johnnyboy said:

Thanks much to you and @madrussian for the great work!  Its an honor to be associated with you super smart guys!

 

The feeling is mutual. 😉  You've inspired me (and hit my funny bone) more than you can know.  Churning out brilliant useful scripts like that.

 

On 4/14/2022 at 10:07 AM, sarogahtyp said:

yes you found a bug but compared with the "squared distances bug" it was a minor issue. But I fixed this as well, thank you for your findings.

 

You are quite welcome.  Curious on your distance problem (great catch btw), can you just use vectorDistance?  I imagine as a game command it's super optimized.

 

On 4/14/2022 at 10:07 AM, sarogahtyp said:

huh, my code is confusing me all the time I try to read it. I just try to not give up^^

 

Haha, my own code confuses me too & sometimes after I just wrote it.

 

On 4/14/2022 at 10:07 AM, sarogahtyp said:

what are you working on? depending on the problem the A* algorithm could be much faster than dijkstra. In my latest tests using the version where the bugs are fixed I had A* always finding the same solution as dijkstra. In most cases A* is much faster. There are some cases when using multiple floors/layers where A* is much slower but although is finding the same solution as dijkstra...

 

On 4/14/2022 at 10:53 AM, sarogahtyp said:

This is a question for @madrussian and @johnnyboy because they worked on a solution for AIs behavior in buildings. but idk what they got in the end.

 

Basically, I'm sending units through buildings using forced movement (like with playAction).  With point selection based on "rooms", etc (in far more dynamic way than using buildingPos positions).  It's pretty fun and looks great when working properly.  Hopefully I can show something off sooner or later.  When it stumbles or messes up, it reminds me of when pierremgi called forced movement though buildings a Rube Goldberg machine. 

 

Btw - Johnnyboy helped me get my AI force moving, and inspired me big time to get them moving through buildings.  As far as I know, he's the forefather of these forced movement techniques.  Also, Leopard has helped me big-time getting Intercept up and running.  Which can (theoretically) perform path-finding much faster than SQF.  One day you guys are going to be pretty shocked by how well AIs are able to fully use buildings, once unleashed using forced movement and pathfinding.  It'll come sooner or later.  Anyhow, mine's still a good ways off.  Long story short I got pretty far, but ultimately may end up being just for personal use... if it can't be made to perform well enough, etc.

 

If any devs are reading this, will you please find a way to enable the "flex" pivot bipod poses for AIs (where AI's gun pivots on a point and AI's feet stretch down to the surface below, like player can do), so AI can make far better use of windows & low walls?  I (along with Leopard & no doubt others) will take that capability and run like crazy with it!

 

[madrussian 347]

On 4/14/2022 at 10:53 AM, sarogahtyp said:

As I started this shortest paths thing there was no command like calculatePath and if you wanted to realize something like a navigation system then you needed a path finding algorithm. this is one use case but with the implementation of calculatePath it is obsolete because the engine solution is much faster.

Now it is only good for gimmicks that have nothing to do with the usual vehicle or unit routing.

 

Very interesting, didn't realize you started this prior to calculatePath.  So glad you followed through and created this.  It's quite integral to cases where engine paths won't work, for one reason or another (like inside buildings).

 

In my own experience (perhaps ironically), it is the game engine's calculatePath that could be argued as obsolete.  Especially considering the potential for Intercept powered path-finding as it performs so lightning fast, plus ability to provide alternatives to engine path (which can be quite problematic, as anyone who has ever tried to load up squad AIs into own vehic can attest).

 

Another dev request while we're at it:  A "CalculatingPath" event, which fires just prior to the path calculation beginning.  (May sound counter-intuitive but trust me, this would be a huge gamechanger for calculating engine paths faster, at least in my AI.)

 

^ Not to be confused with the existing "PathCalculated" event, which fires after the path calculates.

[sarogahtyp 1105]

 

 

 

Update

 

Changelog 

v 2.1 (Download: Mission)

Advise: You should modify initServer.sqf to test both algorithms with various problems and with different modes!

 

Dijkstra

- fixed some major bugs - now it will deliver best possible solution  always

 

A-Star

- fixed a similar bug as in dijkstra

- added 2 new mode switches. You can now choose between:

1. multilayer on: algorithm will find a good solution ( 0%-20%  longer than best) and runtime is mostly much faster than dijkstra but a few times a little slower.
2. multilayer off: algorithm finds nearly always the best solution on a plane and is alsways much faster than dijkstra
3. fast'n dirty on(/off): will use squared distances and will find a good solution (0-30% longer than dijkstra) - this mode uses warp drive 😉 ) usually 10 times faster than dijkstra

 

[sarogahtyp 1105]

On 3/30/2021 at 11:10 PM, mrcurry said:

'm sure this has crossed your mind but for A* handling 3D floors I'd say it's all about the right heuristic.

You should be able to use this psuedo heuristic to bring the algorithm to the right floor fairly quickly:

(_target distance2DSqr _x)*(1+_target heightDiff _x)

 

@mrcurry many many many thanks to you for this glorius advise! I used a very similar heuristic now and it works like charm with multiple layers. Thanks again. 🙂

fyi, I use this now:

 

h-distance = (posi distance2D endpos) * (1 + heightDiff)²

 

I guess Ill test your other advice as well sometimes.

[_foley 192]

Quote

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.

The ability to provide distances (known as weights in standard notation) is pretty useful. Imagine that you have a short path through unfavourable terrain vs a slightly longer path but through much better terrain. If you're able to provide explicit weights between the nodes then you can make it so that vehicles would prefer a longer path on a highway instead of cutting through a dense forest. For infantry this would be reversed - they would be happy to take a longer path along a treeline as opposed to the shortest path through the open field.