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: Kdtree for AirportGetNearestTown #7424

Merged
merged 2 commits into from Dec 24, 2019

Conversation

SamuXarick
Copy link
Contributor

@SamuXarick SamuXarick commented Mar 27, 2019

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.

src/station_cmd.cpp Outdated Show resolved Hide resolved
src/station_cmd.cpp Outdated Show resolved Hide resolved
src/station_cmd.cpp Outdated Show resolved Hide resolved
@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

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

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

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

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

@SamuXarick SamuXarick force-pushed the kdtree-for-AirportGetNearestTown branch from 8c5b13d to 278d25b Compare March 31, 2019 22:56
@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
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?

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
For increased performance, it only iterates over airport perimeter tiles (assuming rectangular shape layout).
src/station_cmd.cpp Outdated Show resolved Hide resolved
@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
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