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

https://imgur.com/a/GZ1W0dV

Most relevant gains only seen past around 3000 towns :(

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?

Looping over perimeter tiles:

Previously:

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");

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.

AirportGetNearestTown stutterfest.zip