1830 route tracing failure

[slapphappyjazz]

We encountered a bug playing 1830 on rails2.1beta1, in which the route tracing algorithm failed to trace a route through two separate paths across an number 43 tile. See hex D8 in the final position on the attached screenshot.

The Erie should be able to trace a route from its home city, around the tight curve on D8, up to B16 and back around the top, through the straight on D8 to E7 and beyond. Rails failed to find this and all the track placed beyond that point was done by map correction (and entering the income for the Erie by hand).
I attach the game file from the end of the game (which doesn't load properly, possibly because we engaged correction mode).
1830_20200516_1727_EndOfGameRound_.zip

[neutronc]

My first guess is that tile #43 has a bug in its tile definition.

[neutronc]

Found the problem but dont know why it happening:
NetworkIterator is crawling over the vertexes in the vertex list the Verex exists but the iterator refuses to follow it. NetworkIterator.next() line 114 in NetworkIterator.java if you load and set a breakpoint there it should bring you in debug mode to that function with all vertices for the provided save game.
Load the game in Debug Mode let it run, use the game history to go back to the previous turn, set the breakpoint in the NetworkIterator or in NetworkGraph.Java at line 373 thats where the iterator is starting. If you have a look at the Graph before you will find the edge vertice D8.SW->E7.NE thats where the route calculation fails...
My Brain is now fuzzed for tonight maybe someone else has more luck.

[jklap]

If you delete action 747 and then 779 the file will load cleanly

[jklap]

It also looks like there are two routes that could be taken with the same end revenue..

• ... E9 -> D8 -> D10 -> ... B16 ... B10 -> C9 -> D8 -> E7 ...
• ... E9 -> D8 -> C9 -> B10 ... B16 .. D10 -> D8 -> E7 ...

Pretty sure this is the root of the issue.

When the path is built coming in via D8.SE, we add both D8.NE and D8.E and continue to trace D8.E which eventually leads us back to D8.NE. But when we look at the path from D8.NE to D8.SW we ignore it as D8.NE is marked as greedy and D8.SW is not. So this logic then fails to add D8.SW in addUnseenChildrenOf:

if (!greedy || edge.isGreedy()) {
    NetworkVertex oppositeV = Graphs.getOppositeVertex(graph, edge, vertex);
    log.debug("Iterator: Neighbor is {}", oppositeV);
    encounterVertex(oppositeV, edge);
}

[neutronc]

ok and how can we fix that ? :)
I do understand that the revenue path is correct but the route path used to allow laying tiles should show the alternative path as possible as well

[jklap]

Haven't spent any time looking at the code except for the hour or so last night so I don't have the full context of how it's currently implemented and am (very) likely missing detail.

But I wonder if it can only be fixed by separating the list of possible paths and tracking them only from the location they are accessible from. As the routes from an edge are determined they are added to a "global" list. The "global" list right now is what I think is causing the issue. I've never worked on network graphs before so caveat ;)

I highly suspect resolving this issue is not going to be a minor effort as it seems it is an issue with the overall fundamental logic?

I don't think the revenue path is correct -- at the end of the game it's only showing a run terminating at A11 when in fact it should run through to F2

Current code:

My testing (but not usable code hack):

[erik-vos]

Maybe off-topic here, but I have started to look at 18Scan, and today I have already seen at least two cases where route tracing goes astray. I wonder what has happened with that code in the past years that I haven't participated, because once these things worked fine.
(I have never worked with the routing code, so I can't help at this time).
BTW I have checked tile 43 and it looks OK.

[jklap]

@erik-vos can you provide the specifics for those two cases? Whether or not it is the same issue we should look into it also.

[erik-vos]

Sure. Perhaps I can best open a new issue for that?

[jklap]

Sure

[erik-vos]

This is #229.

[jklap]

Testing a fix-- impact is an increase search time (due to revisiting some nodes). Need to verify (somehow) it doesn't have an never-ending search scenario.

FYI @slapphappyjazz I hate to be the bearer of bad news but I'm pretty sure your Erie revenue is not $540.....

Pretty sure it's $560 ;)

[neutronc]

Hi @jklap,
whats the status on the fix ? :) would love to push out a new release.

[jklap]

The change I've been testing seems to work, certainly addresses the problem BUT there are a couple of maps I've tested with with lots of circular paths and it can take a very long time (30 seconds+) to resolve. Been looking at how I can prune the search paths but am still working on understanding the code too

[jklap]

FYI, if someone would like to additional test, it's a single line change- remove the following line from NetworkIterator.encounterVertex():

if (stack.contains(v)) return;

[erik-vos]

Done, but I see no difference with your saved file, trimmed after action 747.

[erik-vos]

Looked again, to check if my work on issue #547 (reworking vertex/train specs to eliminate the ignoreMinors stuff) had any effect here. Not so, but I discovered that the problem is fixed by placing an extra token on any city north of Erie, except D10 south.

About greed, see also #478.