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.

Sign up for GitHub

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

Jump to bottom

Add: Kdtree for AirportGetNearestTown #7424

Merged
merged 2 commits into from
Dec 24, 2019
Merged

Add: Kdtree for AirportGetNearestTown #7424

merged 2 commits into from
Dec 24, 2019
+18 −24

Conversation

SamuXarick
Copy link
Contributor

@SamuXarick SamuXarick commented Mar 27, 2019 •
edited
Loading

Add: Kdtree for AirportGetNearestTown …
For increased performance, it only iterates over airport perimeter tiles (assuming rectangular shape layout).

REQUIRES #7429 or else it fails.

@PeterN
Copy link
Member

PeterN commented Mar 27, 2019

Hmm, looking through this, there are further simplification/optimizations to be made.

PeterN
PeterN requested changes Mar 27, 2019
View reviewed changes
@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch 2 times, most recently from dca2aa5 to 1180ac2 Compare March 27, 2019 15:28
@SamuXarick
Copy link
Contributor Author

SamuXarick commented Mar 27, 2019 •
edited
Loading

https://imgur.com/a/GZ1W0dV

Most relevant gains only seen past around 3000 towns :(

@nielsmh
Copy link
Contributor

nielsmh commented Mar 27, 2019

I wonder if the algorithm for this even needs to be that complicated at all. Couldn't you just calculate the middle tile of the airport and use the town nearest to that tile?

@SamuXarick
Copy link
Contributor Author

SamuXarick commented Mar 27, 2019 •
edited
Loading

Looping over perimeter tiles:
Unnamed, 2051-01-21

Previously:
XxHWxXC

@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch from 4f48e56 to 6a58290 Compare March 28, 2019 14:42
@SamuXarick
Copy link
Contributor Author

SamuXarick commented Mar 29, 2019 •
edited
Loading

Just finished testing all (vanilla) airport types on all tiles of a 4096x4096 map (~12k-13k towns), combined with #7429.

Test consisted of comparing the results of the old code to the new code, via an assert(forall == kdtree && kdtree == kdtper);

Ran this code in an AI:

//		local alltiles = AIMap.GetMapSize();
//		for (local type = 0; type <= 8; type++) {
//			AILog.Info("type: " + WrightAI.GetAirportTypeName(type));
//			local percent = -1;
//			for (local tile = 0; tile < alltiles; tile++) {
//				AIAirport.GetNearestTown(tile, type);
//				local newpercent = (tile + 1) * 100 / alltiles;
//				if (percent != newpercent) AILog.Info(newpercent + "%");
//				percent = newpercent;
//			}
//		}
//		AIController.Break("Iterated all types and tiles");

@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch from 6a58290 to 8c5b13d Compare March 29, 2019 19:07
@SamuXarick
Copy link
Contributor Author

SamuXarick commented Mar 31, 2019 •
edited
Loading

I wonder if the algorithm for this even needs to be that complicated at all. Couldn't you just calculate the middle tile of the airport and use the town nearest to that tile?

The results of my researchs so far regarding this and other tests I went through:

  • 4 corners of the outer rectangle (via as->size_x/y): asserts vs original code
  • 1 center tile, computed via as->size_x/y sizes: asserts vs original code
  • 1, 2 or 4 center tiles, computed via as->size_x/y sizes: asserts vs original code
  • all it layout tiles: successful vs original code
  • the perimeter (computed via as-size_x/y) it layout tiles (this PR): successful vs original code

Maybe pointless to report this, but just so that the already known information is in one place.

@SamuXarick
Copy link
Contributor Author

AirportGetNearestTown stutterfest.zip

@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch from 8c5b13d to 278d25b Compare March 31, 2019 22:56
@SamuXarick SamuXarick mentioned this pull request Apr 1, 2019
Closed
@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch 2 times, most recently from 14cb269 to 3cefb24 Compare April 13, 2019 22:27
PeterN
PeterN previously requested changes Apr 29, 2019
View reviewed changes
src/station_cmd.cpp Outdated
uint it_x = TileX(it);
uint it_y = TileY(it);
uint max_it_x = it_x + as->size_x - 1;
uint max_it_y = it_y + as->size_y - 1;
Copy link
Member

Choose a reason for hiding this comment

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

Don't like this naming. perimeter_min_x etc, maybe?

src/station_cmd.cpp
uint max_it_x = it_x + as->size_x - 1;
uint max_it_y = it_y + as->size_y - 1;

mindist = UINT_MAX - 1; // prevent overflow
Copy link
Member

Choose a reason for hiding this comment

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

Again, comment why you need the you need this. (If two airports are the same distance, you want the one with the lowest index)

Copy link
Contributor Author

Choose a reason for hiding this comment

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

It is in the description.

@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch from 3cefb24 to d90481f Compare May 7, 2019 19:25
@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch from d90481f to 88d843a Compare July 18, 2019 21:51
@LordAro LordAro requested a review from PeterN November 23, 2019 09:13
LordAro
LordAro previously approved these changes Nov 23, 2019
View reviewed changes
@SamuXarick
Add: Kdtree for AirportGetNearestTown

Verified

This commit was signed with the committer’s verified signature.
bendevnull bendevnull
GPG key ID: F4FCBEA35BA28E6B
Verified
Learn about vigilant mode
a7f5631 
For increased performance, it only iterates over airport perimeter tiles (assuming rectangular shape layout).
@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch from 88d843a to a7f5631 Compare December 22, 2019 13:43
nielsmh
nielsmh reviewed Dec 23, 2019
View reviewed changes
@LordAro LordAro merged commit 40605ef into OpenTTD:master Dec 24, 2019
@SamuXarick SamuXarick deleted the kdtree-for-AirportGetNearestTown branch December 28, 2019 18:06
douiwby pushed a commit to douiwby/OpenTTD that referenced this pull request Apr 16, 2020
@SamuXarick @douiwby
Codechange: Use KDTree for AirportGetNearestTown (OpenTTD#7424)
be38cf8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@nielsmh nielsmh

@LordAro LordAro

@PeterN PeterN

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
4 participants
@SamuXarick @PeterN @nielsmh @LordAro