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

Add: Road vehicle path cache. #7261

Merged
merged 2 commits into from Mar 8, 2019
Merged

Add: Road vehicle path cache. #7261

merged 2 commits into from Mar 8, 2019

Conversation

PeterN
Copy link
Member

@PeterN PeterN commented Feb 22, 2019

Modeled on the ship path cache, so not many surprises. The maximum length is in path-finder segments (effectively number of junctions) rather than tiles due to how YAPF works for RVs.

On my system with the Wentbourne save, road vehicle time dropped from 62.5ms/t to 19.75ms/t, which is pretty significant. Performance gains for a more normal number of road vehicles would of course be less.

rvpathcache

src/saveload/vehicle_sl.cpp Outdated Show resolved Hide resolved
src/pathfinder/yapf/yapf_road.cpp Outdated Show resolved Hide resolved
@PeterN
Copy link
Member Author

PeterN commented Feb 24, 2019

Hmm, I need to test behaviour around multiple stops.

@PeterN
Copy link
Member Author

PeterN commented Feb 24, 2019

Looks to be working fine, all stops being used.

@PeterN PeterN requested review from nielsmh and LordAro Mar 1, 2019
nielsmh
nielsmh previously requested changes Mar 1, 2019
Copy link
Contributor

@nielsmh nielsmh left a comment

Triggered an infinite loop

It looks like there is some problem with potential infinite loops if the road ahead of a vehicle is destroyed. Performing the same action without this patch causes the vehicle to immediately take the long way about.
Olot Transport, 9th Jun 1970.zip

src/saveload/vehicle_sl.cpp Outdated Show resolved Hide resolved
@nielsmh
Copy link
Contributor

nielsmh commented Mar 1, 2019

Oddly, if I change the layout to this, I can't trigger the loop.
image

@PeterN
Copy link
Member Author

PeterN commented Mar 1, 2019

Only remaining issue is that because the pathfinder works on segments instead of tiles, it's possible to lead vehicles down completely wrong paths by adding or removing trackbits. This can be solved by also storing the tile of each path choice.

@PeterN
Copy link
Member Author

PeterN commented Mar 2, 2019

This remaining issue is resolved by storing the tiles associated with each trackdir choice, which can then used to invalidate the path when necessary.

@PeterN PeterN requested a review from nielsmh Mar 2, 2019
@PeterN PeterN dismissed nielsmh’s stale review Mar 3, 2019

Resolved

@PeterN PeterN force-pushed the rv-path-cache branch 3 times, most recently from c9fd850 to 7b254d7 Compare Mar 4, 2019
nielsmh
nielsmh approved these changes Mar 8, 2019
Copy link
Contributor

@nielsmh nielsmh left a comment

I can't think of any more ways to break this.

@PeterN PeterN merged commit 6c6971f into OpenTTD:master Mar 8, 2019
8 checks passed
@PeterN PeterN deleted the rv-path-cache branch Mar 8, 2019
nielsmh pushed a commit to nielsmh/OpenTTD that referenced this issue Mar 11, 2019
douiwby pushed a commit to douiwby/OpenTTD that referenced this issue Apr 16, 2020
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 this pull request may close these issues.

None yet

3 participants