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

Change: Add path cache for ships #7072

Merged
merged 3 commits into from Jan 19, 2019
Merged

Conversation

PeterN
Copy link
Member

@PeterN PeterN commented Jan 18, 2019

This is an attempt to improve performance of YAPF by caching the path found for a number of steps, removing the need to call the pathfinder every time the ship enters a new tile.

Significant performance improvements have been observed, in one save reducing the average ship ticks from ~ 60ms down to 17ms, allowing the game to run in realtime: http://fuzzle.org/~petern/ottd/shipcache2.png

As the path cache is required to be synchronized, changes to the save/load system have been implemented to include std::deque functionality.

michicc
michicc previously approved these changes Jan 18, 2019
@PeterN
Copy link
Member Author

PeterN commented Jan 19, 2019

Fixed doxygen comments for the std::deque functions and helper.

@andythenorth
Copy link
Contributor

I tried to break this, by e.g.

  • raising land in front of ships on open water
  • sending ship into complex canal network then bulldozing canal tiles

Everything I tried was handled as expected.

  • I only had a few ships running, can't comment on the fps
  • 'forbid 90 degree turns' was 'off' for me

michicc
michicc previously approved these changes Jan 19, 2019
src/ship_cmd.cpp Outdated Show resolved Hide resolved
@J0anJosep
Copy link
Contributor

Great PR! I hope it gets approved soon.

@PeterN
Copy link
Member Author

PeterN commented Jan 19, 2019

Updated to not call HandlePathfindingResult() as commented.

src/ship.h Outdated
/**
* All ships have this type.
*/
struct Ship FINAL : public SpecializedVehicle<Ship, VEH_SHIP> {
TrackBitsByte state; ///< The "track" the ship is following.
ShipPathCache path; ///< Cached path.
TileIndex path_dest; ///< Cached path destination.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It would be great if path_dest could be removed, although I don't know whether it is possible. Maybe clearing the cached path when orders change and when path becomes invalid (and other cases, if any) would be much better.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The problem is v->dest_tile is touched in so many places, in non-ship-specific code too, it would be pretty invasive to do so.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I tried it on the last commit of this branch. I think I covered all cases where a path may become invalid because of orders.
Don't know which approach is better, but I wouldn't keep a TileIndex just for marking whether a path is still valid or not.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hmm, what about virtual methods? This commit implements this.

Copy link
Contributor

@J0anJosep J0anJosep Jan 19, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

👏 If this works, fantastic.

EDIT: On a second thought and as I am not expert with virtual methods, if we have:
Vehicle *v;
v->CallToVirtualMethod();
and Ship is derived from Vehicle, will it call to the virtual function of Ship, isn't it?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, it will call the virtual function on Ship as expected. There is a small performance penalty for this but I don't think that's relevant here.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Just to be sure...
If I call UpdateOrderDest(Vehicle *v, const Order *order, int conditional_depth,...
and inside UpdateOrderDest(...) there is a call to:
v->SetDest()
It will call the virtual method Ship::SetDest and not Vehicle::SetDest ?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yup.

Copy link
Contributor

@J0anJosep J0anJosep Jan 19, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Then, after all this hassle, it is up to you to decide whether it is best to use path_dest or clearing cache when dest_tile changes.
I haven't reviewed the code for load/saving dequeues, but the other part of the code looks great.
This is a great improvement and I hope you have it soon approved.

@PeterN
Copy link
Member Author

PeterN commented Jan 19, 2019

Updated version to remove clumsy path_dest member and clear the path cache directly, using virtual methods.

@PeterN PeterN merged commit 4daaec1 into OpenTTD:master Jan 19, 2019
@PeterN PeterN deleted the ship-path-cache branch January 19, 2019 23:11
Copy link
Contributor

@J0anJosep J0anJosep left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Too late for this?

/* Cached path is invalid so continue with pathfinder. */
}

v->path.clear();
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can this line (v->path.clear()) be inside the "if(not empty path)"?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Er... yes :/ Oops!

@J0anJosep
Copy link
Contributor

J0anJosep commented Jan 20, 2019

If you are interested in extending this to NPF, these two commits may come useful for a starting point. Note that these commits should be adapted:

  • For reserving, but most of the changes won't be needed. Just pick what is needed and add the max length of a cached path.
  • Don't know if oil rigs will be troublesome in case of just caching the path. Of course, the hack can be implemented in a better way if needed. EDIT: Just check if last tile of the found path is an industry or a station. Do not cache that node.

If not interested in taking on this, let me know and I will try to do it.

@PeterN
Copy link
Member Author

PeterN commented Jan 20, 2019

If you want to give it a go, please do open a PR. I don't intend to spend much time on it myself but if you can see what needs to be done, that's great!

@J0anJosep
Copy link
Contributor

Next weekend I will check this and create a PR if it works.

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

4 participants