Improve Route Finder to Consider Territory Effects

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:

If you try to move directly from Gazaca to Hatra, the route finder fails (try to go through
Ninive).
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?

redrum

@cernel Actually I think I have a much simpler example of your first point (which is way more common than the contested territories as very few maps allow that).

Skip to Parthia
Edit out units in Seleucia and Hatra
Try moving Horse Archer in Ctesiphon to Amida

It should favor going Ctesiphon -> Seleucia -> Hatra -> Amida as that is a legal move that you can make using waypoints. But it tries to move through Ninive because that is shorter even though there are units blocking.

Cernel

@redrum Right, and what I understand is that, now, if Ninive would have a territory effect impeding access to horsearchers, the router finder would work fine, instead. So now the routerfinder behaves differently (better) for territory effects than for the rest, and I think this is not really good. Either the router finder for the territory effects should be dumbed down to behave like the rest or the rest should be made to behave like it, is my suggestion.

Cernel

Another unsupported item is canals. For example, open World At War and edit a German battleship in 116 Sea Zone and try to move to 109 Sea Zone: it will try to go there directly, getting blocked by the canal, while it should select the path through 104 Sea Zone (if we edited a submarine in, also going through 115 Sea Zone would be valid, but I think 104 Sea Zone should be preferred anyways, as friendly).

redrum

@cernel correct as right now impassible, restricted, and terrain are treated as more hard stops then reduce number of moves then enemy units, AA, etc. I'm guessing this was designed primarily for 1-2 move units not 3+.