Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Road vehicle pathing cache does not always pick up changes in road network #7670

Closed
SamuXarick opened this issue Jul 27, 2019 · 12 comments · Fixed by #8568
Closed

Road vehicle pathing cache does not always pick up changes in road network #7670

SamuXarick opened this issue Jul 27, 2019 · 12 comments · Fixed by #8568
Assignees

Comments

@SamuXarick
Copy link
Contributor

SamuXarick commented Jul 27, 2019

Version of OpenTTD

Custom one based on 20190722, https://github.com/SamuXarick/OpenTTD/tree/SamuPatchPackRebase

Expected result

YAPF should have a lower average ms than NPF

Actual result

YAPF has a higher average ms time than NPF

Steps to reproduce

Load savegame and open framerate window, then switch to NPF and notice the difference.

road vehicle ticks.zip

YAPF: ~135 ms
NPF: ~35 ms

This system has windows 7, 4GB RAM, Celeron E1400, 2 cores @ 2.00 GHz

@SamuXarick
Copy link
Contributor Author

[18:52] looks like the company affected is that of Terron
[18:52] Company 4 killed and ms went all the way down to 16 ms

@LordAro
Copy link
Member

LordAro commented Jul 27, 2019

First off, do not submit issues relating to custom versions of OTTD, they are unsupported, especially when they contain a savegame bump and the provided save cannot be loaded in unmodified OTTD

Second, while 35ms vs 135ms is a big change, "YAPF is slower than NPF" is not an issue in itself - YAPF is designed to be "better" than NPF, but that does not necessarily mean "faster".

I'll give you... let's say a day to submit an actual reproducing savegame that I can actually load in master.

@James103
Copy link
Contributor

James103 commented Jul 27, 2019

Here are my tests for Wentbourne savegame. The test was ran in 20190723-master-g2e686ad5d5-windows-win32 using an Intel(R) Core(TM)2 Duo CPU T5800 @ 2.00GHz and 3 GB of RAM. Times are in milliseconds per tick (mspt).

Category YAPF time NPF time
Trains 250±10 ms 265±10 ms
Road vehs 70±5 ms 140±10 ms
Ships 19±1 ms 600±50 ms

Edit: added link to save game

@MingweiSamuel
Copy link
Contributor

MingweiSamuel commented Jul 28, 2019

Category YAPF time NPF time
Road vehs 70±5 ms 140±10 ms

Looks like YAPF is better than NPF on vanilla? So this may be an issue with your patch pack.

If thats a typo then you should provide the .sav as well to see if others can reproduce.

@SamuXarick
Copy link
Contributor Author

SamuXarick commented Jul 28, 2019

from irc: https://webster.openttdcoop.org/index.php?channel=openttd&date=1564185600#1564261315

The problem seems to be very specific to unconnected roads that I assume were connected at first. AI detected road vehicles crash there, and so it removed the roads, probably attempting to build a bridge over it.

I really doubt my custom build has any influence in that, with like 99.9% certainty. It's a build that reworks AI GUI windows and AI max ops. It doesn't touch anything related to YAPF or NPF nor any commands. of that nature.
Hercules, 1982-11-10

@SamuXarick
Copy link
Contributor Author

Before connecting the roads, ~160 ms:
screenshot#1

After connecting the roads, ~17 ms:
Hercules, 1982-06-22

@SamuXarick
Copy link
Contributor Author

SamuXarick commented Jul 28, 2019

I stopped all vehicles in the game (~about 5000 road vehicles), except one, and found where the problem occurs.
I let vehicle 368 to move around that area, until it reached that exact location, moving at 0 km/s. It has at least 2 or more vehicles ahead of it, (36 and 115) stopped, blocking access to the presumably last tile it can walk to before turning back.
Hercules, 1983-03-22

During the time it is "moving" at 0 km/s, the pathfinder is being constantly called every tick:
dbg: [yapf] [YAPFr]! 368- 37672 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 34459 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 42715 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 33536 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 39387 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 34812 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 35434 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 35560 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 34105 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 46388 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 33735 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --
dbg: [yapf] [YAPFr]! 368- 38073 us - 10001 rounds - 63 open - 10000 closed - CHR
0.0% - C -1 D -1 - c0(sc0, ts0, o0) --

After a few days, vehicle 368 finally moves on to the tile ahead, walking through the two vehicles ahead. When it does this, no more pathfinder calls are done, until it reaches the end of the entered tile, calling it again, but only once, then walking back and away towards the northwest of the road, until it eventually comes back again to this same situation.

The reason the spike is so noticeable is due to the road network the vehicle is in being so large, a congregation of multiple AIs connected roads, augmented by the constant calls to the pathfinder every tick.

@LordAro LordAro changed the title Road vehicle ticks is higher in YAPF than in NPF Road vehicle pathing cache does not always pick up changes in road network Jul 28, 2019
@SamuXarick
Copy link
Contributor Author

new savegame, reproduced the scenario.
OpenTTD 20190723-g2e686ad5d5
Henfingburg Transport, 1951-03-15.zip

@nielsmh nielsmh added this to the 1.10.0 milestone Sep 1, 2019
@SamuXarick
Copy link
Contributor Author

SamuXarick commented Nov 2, 2019

a better savegame, based on the previous one, but only requiring 2 vehicles to trigger the issue, with a giant road network.

2 vehicles only.zip

@SamuXarick
Copy link
Contributor Author

SamuXarick commented Nov 2, 2019

The problem is the combination of line 1381 and 1398 in roadveh_cmd.cpp. At 1381 it calls the pathfinder, and at 1398 the vehicle finds itself blocked, so there's no update to the vehicle position on the current tick.
Next tick it repeats again, constantly doing this until front->blocked_ctr times out.

dir = RoadFindPathToDest(v, v->tile, (DiagDirection)(rd.x & 3));

if (v->IsFrontEngine() && RoadVehFindCloseTo(v, x, y, new_dir) != nullptr) return false;

The issue is also happening with NPF, not just YAPF. NPF is just less cpu intensive about it, but still noticeable.

SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Nov 3, 2019
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Dec 31, 2019
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jan 3, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jan 8, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jan 11, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jan 11, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jan 12, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jan 19, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 6, 2020
… the road pathfinder when a vehicle is blocked by another
@nielsmh
Copy link
Contributor

nielsmh commented Feb 9, 2020

Fixing this (at least as suggested in #7822) requires bumping the savegame version, will that prevent it from being fixed in 1.10 now that it has branched?

SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 9, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 23, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 24, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Feb 29, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Mar 13, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Mar 30, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Apr 1, 2020
… the road pathfinder when a vehicle is blocked by another
@LordAro LordAro modified the milestones: 1.10.0, 1.10.1 Apr 3, 2020
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue May 12, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jul 12, 2020
… the road pathfinder when a vehicle is blocked by another
@TrueBrain TrueBrain modified the milestones: 1.10.1, 1.11.0 Dec 14, 2020
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Dec 18, 2020
… the road pathfinder when a vehicle is blocked by another
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Dec 22, 2020
… the road pathfinder when a vehicle is blocked by another
@TrueBrain TrueBrain removed this from the 1.11.0 milestone Jan 5, 2021
SamuXarick added a commit to SamuXarick/OpenTTD that referenced this issue Jan 8, 2021
… the road pathfinder when a vehicle is blocked by another
@JGRennison
Copy link
Contributor

Looking at the attached savegame (road vehicle ticks.zip), all the pf settings have totally incorrect values.
In the past, some users cargoculted the idea that the settings should all be set to the extreme range of their settings to improve pathfinding. However this creates many strange pathfinding bugs and doesn't actually improve anything.
Probably the pathfinder penalty settings should be removed entirely.

See also: JGRennison/OpenTTD-patches@bb36369

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

8 participants