-
-
Notifications
You must be signed in to change notification settings - Fork 957
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
Add: Kdtree for AirportGetNearestTown #7424
Conversation
Hmm, looking through this, there are further simplification/optimizations to be made. |
dca2aa5
to
1180ac2
Compare
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? |
4f48e56
to
6a58290
Compare
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:
|
6a58290
to
8c5b13d
Compare
The results of my researchs so far regarding this and other tests I went through:
Maybe pointless to report this, but just so that the already known information is in one place. |
8c5b13d
to
278d25b
Compare
14cb269
to
3cefb24
Compare
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; |
There was a problem hiding this comment.
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 |
There was a problem hiding this comment.
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)
There was a problem hiding this comment.
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.
3cefb24
to
d90481f
Compare
d90481f
to
88d843a
Compare
For increased performance, it only iterates over airport perimeter tiles (assuming rectangular shape layout).
88d843a
to
a7f5631
Compare
Add: Kdtree for AirportGetNearestTown …
For increased performance, it only iterates over airport perimeter tiles (assuming rectangular shape layout).
REQUIRES #7429 or else it fails.