Improve Route Finder to Consider Territory Effects

[alkexr]

Version 10597. Example: in LME, try to move from Isengard to the Gap of Rohan.

The route finder finds the route with mountains territory effect along the way, which most units can't enter. It can't find the valid route through Nan Curunír. In fact, the route finder almost invariably chooses the route through the mountains in different parts of the map too (regardless of the order in which territories and connections are listed in the xml). While this is at most a minor annoyance for humans, I have the suspicion that this affects the AI as well.

PR: https://github.com/triplea-game/triplea/pull/3664

[Frostion]

Reminds me of how the engine in Iron War, when a human wants to move an air unit over sea territories, selects a route over AA ships instead of another totally empty and available sea territory.

[Hepps]

Yeah in LME there is a lot of CNTRL clicking. Adds to the fun!

[Cernel]

@alkexr Yeah, the engine is very limited in selecting path. I think it works only for regular impassable and only for movement 2. It would be nice and proper if ctrl is never mandatory, but the engine can always select a path, if there is one (of course, one of the shortest ones).

This is a usability limit both for territory effects and for canals.

[redrum]

Yeah, the route finding algorithm doesn't take into account territory effects or ship AA. Definitely could be enhanced. This should probably be a feature request?

I'm actually not sure if this impacts the AI, I'd need to test to see. We don't have a lot of maps with territory effects so haven't really done much AI testing with them.

[Cernel]

@redrum Shouldn't usability stay in GitHub?

[redrum]

@cernel I still don't consider that a separate category. IMO, you have bugs or features/enhancements. IMO, this would be an enhancement to the route finding algorithm to take into account more parameters. Just like I think having the tooltip conversation here on the forum as a feature request is better than on github.

[Cernel]

Yeah, if you don't use the forum for usability, for what? Still I'd keep it separate from actual rules changes / additions, but I guess would need 1 more subforum.

[Hepps]

Now I will preface this statement by saying that I have no idea how this works and have no idea of how this suggestion would impact work on any other part of the game including the AI.

But would it be beneficial to have the units move on a route that is primarily determined by where the player is moving his cursor? Using @alkexr example say I clicked on a variety of units in Isengard and then proceeded to move my cursor down through Nan Curunir and into the Gap of Rohan. Then where I moved the cursor would be the default path or route for the units. Kind of like an invisible/automated version of the Cntrl Click method.

Just a thought.

[beelee]

@redrum yea i know the paratrooper thing doesn't alway's take a legal route. As alkexr alluded to, it's not hard to edit and do the move thing

[prastle]

@beelee control click

[Frostion]

@redrum @Cernel We could just rewrite the current description of the Bugs category to say "Report bugs and usability issues related to the game engine, maps and mods here"? Remember that casual players might never drop by Github. We are lucky if they drop by here

[Cernel]

@frostion This is up to the developers ( @redrum @LaFayette @RoiEX @ssoloff ) to decide, but I think usability should be divided into usability feature requests and usability bugs too, and I would consider this a bug. I think the engine should always successfully select one of the shortest possible routes, or at least never preferring an impossible one over a possible one, like here, without using Ctrl being mandatory.

[redrum]

@alkexr PR to have route finding check for territory effects: https://github.com/triplea-game/triplea/pull/3664

[Cernel]

@redrum Cool. I see/assume this works for infinite movement. Also, I seem to recall the existent regular route finder (normal impassable or hostile units blocking etc.) works only for movement 2 units, but it is not necessarily correct for movement 3 or more, but I'm not sure if this is the case?

[redrum]

@cernel Feel free to test it out: https://github.com/triplea-game/triplea/releases/tag/1.9.0.0.10898

Generally, it treats the territory effect not allowed to enter as if that territory is impassible for any units in that list for route finding purposes. Route finder takes a bunch of different things into account such as impassible, restricted, territory effects, neutrals, enemy, and AA. I doubt its perfect and if you have some simple examples where it does poorly then I'm glad to make additional improvements.

[Cernel]

@redrum Ah so you reworked the entire router finder, not just expanded it for the territory effects only?

For now, I tested on 1.9.0.0.10874 with the horsearchers of 270BC and I can confirm that the old router finder would try impossibly to move 2 through a blocker when it could move 3 to the target territory.

[Cernel]

@redrum Using 1.9.0.0.10898 do this:

Skip all until Parthia.

Edit 1 horsearcher in Gazaca.

Edit out all units in Seleucia.

I see there are 2 issues:

1. If you try to move directly from Gazaca to Hatra, the route finder fails (try to go through
   Ninive).

2. If you ctrl your path from Gazaca through Ctesiphon, Seleucia, Hatra, the move is given as invalid as "Cannot blitz out of a battle further into enemy territory", since you would be starting from hostile, but I believe this move should be allowed, as you are first stepping into a friendly territory (Ctesiphon), and you can actually do it if you first move to Cteshipon, then do the rest of the movement, manually in two steps (on the same phase). I'm not actually sure if when starting movement in a hostile territory you are supposed to be unable to enter an enemy owned territory for all the movement or only for the territory you immediately move out, so being possible by stepping through a friendly territory in between but, one way of the other, this should work the same if you do it with ctrl or manually in multiple steps (I think this movement should be legal, but not entirely sure).

If, additionally to the edits above, you also edit out all existent units in Gazaca and make the territory owned by Parthia, then issue number 2 is not present anymore, but the number 1 is still there.

[Cernel]

@redrum What I'm saying is that I believe, in the case you pictured at that pull, that if there would be no territories effects in the map, but East Methedras would be just impassable or blocked by enemy units, then that movement would not have been handled correctly, as well, as the old routefinde would try to go through East Methedras in any case.

I'm not sure, but what I recall is that, even in the supported cases (blockers etc.), the old routefinder would find the right route only if it is one amongst the shortest paths.

So, for example, the case posted at the first post, of going from Isengard to Gap of Rohan was already supported for blockers etc., but the case you posted of of going from Isengard to Westfold, avoiding the shortest route, was not supported generally, also for the supported items, not just relatively to the totally not supported territory effects. Practically, only movement 2 units were fully supported, not 3 or more.

So, what I'm thinking is that this change rather than expanding the route finder support to territory effects, now it handles such things differently and better than how more common items (regular impassable, blockers...) are currently supported.

[Cernel]

@Panther Since I see you around right now, question:

I know that it is not possible to go from A to B if A is hostile and B is enemy owned (the case of contested territories in Axis & Allies 1914).

But is it possible to go from A to C through B (A->B->C) if A is hostile, C is enemy owned and B is friendly?

Currently, the engine allows you to do so in two steps, but disallows you to do so in a single step, using Ctrl, and I'm wondering about the intended behaviour, reinterpreting the rules for multiple movement units.

EDIT: What I meant is if you have a unit that can move 2 during Combat Move, would such a unit starting in a hostile land territory be able to move 2 spaces first into a friendly land territory and then into an enemy owned land territory? Or is this just a case not covered by any rulesets?