search

tobymao / 18xx

A platform for playing 18xx games online!
https://18xx.games
Other
285 stars 186 forks source link

Autorouter taking too long to time out #11252

Open ollybh opened 3 weeks ago

ollybh commented 3 weeks ago

Issue #11239 was a report of being unable to select a route. This was probably caused by the autorouter being started and locking up the interface.

This occurred at action 792 of game 177538. This game exhibits horrendously bad autorouter performance: it is a game of 1858 which has Lawson track and a lot of tiles have been laid with many open cities. This means that the autorouter is going to struggle, but the problem here is that it is not timing out correctly: with the default setting of 30 seconds for path timeout, it took more than 10 hours to timeout on my desktop computer (which is far from being new or high-spec, but 😱).

D, [2024-09-30T22:26:36.021000] DEBUG -- : Rendering game view...
D, [2024-09-30T22:26:36.231000] DEBUG -- : Done rendering game view
D, [2024-09-30T22:26:39.094000] DEBUG -- : Path search: 0 / 57 - paths starting from L13
D, [2024-10-01T08:44:27.660000] DEBUG -- : Path timeout reached
D, [2024-10-01T08:44:27.661000] DEBUG -- : Evaluated 3791 paths, found 232 unique hexsides, and found valid routes 7E:3054 in: 37068.567
D, [2024-10-01T08:44:27.666000] DEBUG -- : Finding route combos of best 7E:3054 routes with depth 3054
D, [2024-10-01T08:44:27.892000] DEBUG -- : Found 741 possible combos (5 best) and rejected 0 conflicting combos in: 0.225
D, [2024-10-01T08:44:27.899000] DEBUG -- : Rendering game view...
D, [2024-10-01T08:44:50.770000] DEBUG -- : Done rendering game view
D, [2024-10-01T08:44:51.202000] DEBUG -- : Rendering game view...
D, [2024-10-01T08:45:14.141000] DEBUG -- : Done rendering game view

The path timeout is checked once in the autorouter's outer loop, iterating over the corporation's reachable nodes and looking at the potential routes from each. In this case it took multiple hours to check the nodes from the first node, and then only timed out when moving onto the second node.

Moving the timeout check into an inner loop won't fix the performance of the autorouter, but will at least means it times out much more quickly.

ollybh commented 3 weeks ago

Gist containing the game data for game 177538, up to action 792.

scottredracecar commented 3 weeks ago

Yeah, agree. I think the intent of the timeout options is to stop looking for routes after the timeout has expired, so should never be allowed to go for a long time like 10 hours.

The timeout worked correctly for me when I was testing it when it was first implemented, even on games like 1822 with similar open network routing issues.

On Thu, Oct 3, 2024 at 12:46 PM Oliver Burnett-Hall < @.***> wrote:

Gist https://gist.github.com/ollybh/795692af552ddd782bf1e3cd5e0a0135#file-1858-game-177538-json containing the game data for game 177538, up to action 792.

— Reply to this email directly, view it on GitHub https://github.com/tobymao/18xx/issues/11252#issuecomment-2392201933, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG6CEXHHJS4DKDDRKWS2A63ZZWNKPAVCNFSM6AAAAABPKPA7GCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGOJSGIYDCOJTGM . You are receiving this because you are subscribed to this thread.Message ID: @.***>