Any way to speed up pathfinding?

Hex grid, need to find paths in every direction from a hex for 3 steps. I have it so every viable path is highlighted by switching on an area of effect highlight, and switching on a dynamic property to avoid repeat toggles.

To do this, it seems you a need GKC1 with range 1, triggering every viable hex in range, repeat with a GKC2, trigger 2, then repeat with a GKC3, trigger 3.

First thing I did was to have each trigger render the triggered hex non-viable for that GKC only, using a dynamic property, to cut out multiple paths to the same destination.

Second thing I did for a small speed increase was to first set the source hex as “not viable”, to cut down on backtracking paths.

Third thing I did was for the trigger 2 to not affect the highlighting, as trigger 3 is guaranteed to cover all relevant hexes*.

This cut the time taken for the pathfinding down from 40-something seconds to 15 to 25-ish seconds, but I’m trying to make more speed gains.

It seems that Vassal resolves all trigger 3s from one path first, and there’s no way I have figured out to have all trigger 1s resolve, then 2s, etc., which might be faster.

Any suggestions? Is this something I should just give up on without a custom class (that I have no ability to make)?

  • Writing this makes me realise I should probably have the triggers make the hexes non-viable for the next GKC too, and turn trigger 2 highlighting back on.

Well I doubt you’re ever going to be able to make it “lickety split”, but in terms of your immediate issues, instead of having the recipients of GKC1 immediately send e.g. GKC2, etc, what about:

(1) Send and resolve all the GKC1’s. Instead of firing GKC2’s, they build a central list (e.g. perhaps a string value in a Global Property) of all the GKC2 targets (meaning you can also clip out duplicates).
(2) Then, from that list, send out all our GKC2’s. Again, build a central list of GKC3 targets, removing any duplicates.
(3) Finally, send GKC3’s to your final list of targets.

I do things like have a string of “Berlin London Copenhagen Paris” and then do something like (GetProperty(“CapitalsList”).contains(GetProperty(“LocationName”)) == true) in a filter to see if something is on the list. I realize your locations may be more grid-name-ish, but I imagine there’s some sort of approach like that.

That could at least minimize the total number of GKC’s you send you – since you’d really just be sending 3 GKC’s – GKC1 all at once to every one of your range 1 targets, GKC2 all at once to the next set, etc. The total number of times you fire a GKC is the biggest predictor of performance lag.

Brian

Thanks. Just to see if I got this right, your “resolve all GKC1s” means a list of hexes at range 1? Then send GKC2s to all the hexes in the list at range 1, to trigger… what, exactly? range 1 GKCs?

I think I’m not understanding how the “central list” can be compiled without executing the range 1 GKCs as I am currently doing.

Further complication is that this process may have to be run simultaneously for a dozen path sources.

EDIT: Oh, I think I get it now. You are saying send the GKC2s, which are range 1, to every hex on the list. So, it’s not all that different, but you are resolving the triggers in range 1, range 2, range 3 order, which I have been unable to do.

I think the multiple sources issue is going to make this hard to pull off.

Have the “brains” of the operation be the piece/hex/whatever that’s at range 0?

Yeah, it’s not the problem I thought it was - as long as Vassal resolves the entire sequence for one source before moving on to another, which I think it will, by default.

This does sound like a programming challenge that might be beyond me though. My concern is that I’ll struggle to get it working for far too long, only to find a couple of seconds shaved off, if that.

Still, you have put me on track towards a probable improvement. Thank you!

I hate to say this, but I think you are doomed to fail to get this working using this approach in any way acceptable to the average impatient user. You are hitting hard against several of the inherent design flaws in Vassal. GKC’s in particular are extremely inefficient and their execution time is proportional to the number of pieces on the map (including invisible pieces, command relayers, do not stack pieces etc.). I see in your test example that you the map is otherwise empty apart from your test pieces. Wait until the board is littered with actual play pieces in a game in progress.

I implemented exactly what you are doing in AVL using a load of custom code. I never for a moment considered trying to do it with GKC’s. And I believe in your game the Map segments rotate as well? I’m not sure I would have attempted that, even using custom code.

I’m not meaning shoot you down in flames, and you have made a noble effort, but you are asking for advice as to whether to continue down this path.

Regards.

Just a thought though. Is this something that only happens once at the start of a game? In that case, you may get away with it.

No, the pathing for zone of control visibility is a toggle players can switch on and off at will, at any time in the game.

Aside from the speed issue it is working, and the map segments rotated on setup and terrain-specific (and terrain-changing!) commands all work perfectly.

I do appreciate the advice, and I think I will take it, rather than go further down the programming rabbit hole to shave seconds off a function that will never be fast enough.

I will probably just depreciate visibility of the function on the toolbar, making them sub-menus, in addition to the tooltip warning. Leave the function in for screen-shots and the like, but not worry any further about the speed for real-time games.