bidir A* has a problem with shortcuts with same start & end node

[nilsnolde]

I've discovered this during the possibly only test that properly tests shortcuts end to end in test/astar.cc. with this map where ABCDE is faster than AXYE, we still take AXYE:

           X-----------Y
          /             \
    1----A               E---2
          \             /
           B--C--------D

I created a failing test which is currently disabled:

valhalla/test/astar.cc

Line 1684 in 34a7054

TEST(BiDiAstar, DISABLED_test_recost_path_failing) {

.

it seems very similar to the issue with trivial routes and our bidir algorithms.

[nilsnolde]

This should really be a sufficiently rare problem. I’d rather do the low effort thing and log out if that happens. If we see many of those in a planet build, we can prioritize maybe.

[nilsnolde]

see #4632 (comment).

it's not rare at all!

[radekvermirovsky]

@nilsnolde Hello Nils, do you have any estimates on how this could impact performance? Could you provide an estimation of how much the current presence of same start-end shortcuts might degrade performance? Its only in bidir A* or costmatrix bidir dijsktra can be also affected?

[nilsnolde]

there's no impact on performance at all @radekvermirovsky .

costmatrix might be affected, I didn't look at that.