#4181 Princess doesn't know how to use VTOLs

[Magnus Kerensky]

Princess doesn't seem to know how to use VTOLs as of 37.11. She can move them like other ground units, but won't move up or down to negotiate hills, forests and buildings.
Last time I tested (which was admittedly, many versions ago) this behavior applied to aerospace fighters as well, and it made more of a difference since ASFs lose altitude every time the strafe something.

I'm sure the processing overhead involved in calculating paths at different elevations would be a nightmare.

[Deric Page]

This is a known issue that I'm hoping to be able to correct as I work on Princess.

[saginatio]

If you haven't started working on this issue, I might be able to produce something that can help you:

Currently there are 3(4) shortest path algorithms used in MM, and only one is without flaws. I was planing to use the best one (it's an implementation of A*) and make him a bit more robust so that he can be reused in all the places that need a shortest paths algorithm. (i.e. precognition, movement envelope, testbot, GUI). That would have two benefits (among others):
1)its easier to test the pathfinders for bot (they would be almost the same as in GUI)
2)There would be a functional interface with getNextMoves() method. You could use it to override the standard method to make VTOLS look only for paths that preserve current relative elevation. That would make any other changes to princess unnecessary.

[Deric Page]

I have not started working on this yet. However, I understand that the A* implementation currently in place only computes the shortest path to a given hex and no others. Princess's current pathing function will compute multiple paths to a hex and pick the "best" one based on a variety of criteria. One of those includes how much damage she might take, which is influenced by the target move modifier. This means that the shortest path is not always the best.

[saginatio]

I assume that potential moves logic for princess is enclosed in PathEnumerator.recalculateMovesFor(...). As far as I see it calculates, more or less, shortest paths between src and surrounding hexes. Later it this set is evaluated by pathRanker. If there's another class for calculating potential moves, please point me to it.

1) A* with estimate function h(x):=0 is behaving identically to dijkstra algorithm, so it can be used as shortest path between start and all nodes (with modifications to stop condition). It might be better to make two distinct classes one with astar for paths between two points and dijkstra for "1 to all".

2) You could define graph with restricted edges (e.g. no psr>7). It is not as powerful as considering all paths and ranking them later, but it is much faster.

3) You could define graph with more nodes. For example: consider (Hex) x (facing) x (hexes traversed since last forward/backward change) graph. It would allow us to find paths that give +2 modifier, for moving at least 5 hexes, that use the least mp. Dunno how long it would take to compute it but it's worth a try. Another example of larger graph is one defined by PathEnumerator.hashPath(...).

It is my second attempt to rewrite pathfinding to make the code clearer and more reuse friendly. The bad side is that I'm giving myself a ~25% chance of success. Still it is a nice problem to fight with:)

[Deric Page]

The meat of the code is in getNextMoves. There it takes the unit's current location and determines which adjacent hexes it can move to. It also looks at in-place facing changes without moving to another hex. As a result, it's possible for multiple paths to the same hex to be generated. For example, if you have hex A surrounded by hexes B-G (B being north and G being NW), the unit could step straight to A, step to B and then turn and step to A, step to G then turn and step to A, and so forth. If you set Princess's log level to Debug, she'll print out the paths she's considering and you'll see several routs to the same place calculated.

Now, I'm far from any sort of expert on AI path mapping. I'm entirely self-taught and picked up this project from whomever coded it originally. I'm sure that the current process isn't the best (I certainly doubt it's the most efficient). So, if you've got a better method for producing similar results to what is currently in place, by all means post a patch.

I do think we've drifted a little off-topic for this bug ticket, though. Feel free to PM me (Netzilla) on either the MegaMek or official BattleTech forums, however.