Units may fail to find a long-path when one should exist if they end up on a region unconnected to others in the hierarchical pathfinder

[wraitii]

I stumbled upon an as-of-yet not formally described issue in the long-range pathfinder yesterday: units may fail to find a long-range path because the hierarchical-pathfinder/long-range pathfinder does not have one, even if the short-range pathfinder shows path everywhere.

In general this is a fairly rare problem since it can remain fairly "hidden". For example if you put two houses just far apart enough, the short-range pathfinder will have units go through, but the long-range pathfinder won't. However, this can also happen fairly quickly when units get in forests: suddenly they might be surrounded by trees far apart enough to be in an unconnected region, but largely passable in the short-range pathfinder. Then the unit will just idle. This is why regularly we end up with units stuck in the tree line (look for it).

I can't see a very easy fix for this, sadly :/ . Maybe forbid the short-range pathfinder to go at any point that's not reachable in the hierarchical pathfinder (i.e. don't cross in a region the long-range pathfinder can't access). But that might end up being quite slow, will have to test.

I'll attach a test map to highlight the issue: the units can get inside the sparser forest meshes if you use the short-range pathfinder, but not the long-range pathfinder. So if you get a unit inside, until it walks on one of the inner regions (use hierarchical pathfinder overlay to see them) it won't be able to get out.

[wraitii]

Test map, in demo scenarios.

[wraitii]

You can see how the problem arises in gameplay if you 'gift from the gods' a dropsite in the lower-left forest and use about 20 units to gather. Deactivate "gift from the gods" and let units to their own thing: a few will get stuck and become idle.

[wraitii]

Opened a github branch where I've fixed the problem in the test cases I could find: ​https://github.com/wraitii/0ad/tree/Fix_4327 Unified diff attached (warnings: maps may fail).

There's basically a few new tricks to the pathfinder that largely improve behavior: -first I fix "ShouldCOnsiderOurselvesAtDestination" to actually do what we should when we're at destination. I haven't check, but this might fix other weird "stuck" bugs. -secondly if when we're out of waypoints we are not at our destination (typically, this happens if the long-range pathfinder moved the goal much closer to us, for example if you try to gather from a tree in the middle of a semi-dense forest), we'll try a short path. This short-path may take us closer to our actual target. -However, if that short path fails, we either MoveSucceeded or MoveFailed depending on our situation. This means units won't retry tons of times.

You can test a few edge cases: units should now be able to navigate sparse forests in a neater way, and no longer stop at the "border" as often. Units will try to gather near them if you ask them to gather from a tree on another island (after moving towards the edge), which is currently not the case. Siege units should not get stuck or not find a path nearly as often. In general it just behaves better and should be more consistent.

It also should remove some cases of units getting stuck.

[elexis]

Moving to the new WIP milestone.

[wraitii]

Rebased on the github branch, attached a unified diff (without the map changes).

[wraitii]

Following discussion with Itms: instead we should probably prevent entities from ever going somewhere the long-range pathfinder doesn't want them to go.

This means a number of things: -Adapt the short-range pathfinder to work with rasterized obstructions somehow/dump it out -adapt distance-checks to use the grid -adapt unit motion to detect running into non-authorized zones.

[wraitii]

Change flags.

[elexis]

Backlogging due to lack of progress

[Imarok]

Move tickets to Simulation as UI & Simulation got some sub components.