CleverRaven
Should city distance be cached?
Is your feature request related to a problem? Please describe.
I'm trying to figure out why (failing) to find a closest special takes such a huge amount of time. A performance measurement of such a failure seems to indicate about half of the time is spent in overmap::distance_to_city.
That gives rise to the question of whether this information can be cached such that it's saved the first time it's generated and that info is then looked up on subsequent attempts. Another question is whether the method to calculate it is optimal.
Solution you would like.
A simple solution would be to have each overmap have a matrix over all OMTs with their cached values. When a distance is wanted, check if it's cached and return that, or calculate it otherwise. Obviously, that would require the storage of 180x180 ints.
A complication is that the distance will not be known with certainty unless all OMs within the distance have been generated, as a town might be generated in a neighboring OM just over the border.
I would suggest either of two methods to determine whether a calculated distance is certain, and thus worthy of being cached:
- If the distance to the neighboring OMs is shorter than the calculated distance, check if those OMs are generated.
- While examining points, keep track of whether any have not been generated, and don't cache if that's the case.
Describe alternatives you have considered.
No response
Additional context
It can be noted that when failing to find and generate specials, the same search is performed twice, first trying to find an existing instance, and then to try to generate it. I believe that city distance calculations are performed on both passes (if city distance is a criterion, which I think it is in most cases).
I think there's been some discussion about the impact of city distance calculations recently, but I don't have more knowledge about that than this.
I agree that distance_to_city() seems to be pretty bad. From one of my other attempts to profile overmap generation I found that distance_to_city() was taking up ~12% of the CPU time, which is absurd.
I think #77668 does a similar cache optimization, so I would recommend starting there.
Another question is whether the method to calculate it is optimal.
Just based on the amount of time it takes I would believe it's not. The search pattern is closest_points_first and then comparing each and every tile iterated to a list of city_tiles. Instead of blindly circling outwards we probably want to grab a list of all cities on that overmap+adjacent overmaps, compare the city_center's x/y position + city_size of that city with our search point, and then only search in the direction of the closest cities. (If it's a toss-up then we can go back to searching outwards in a circle, comparing distance between a dozen city centers and the search point is only a few dozen operations and should be a humongous time-savings if it lets us completely ignore certain search directions)
Note that I am ignoring some difficulties of this approach, like making sure we are always perfectly accurate. That we don't accidentally look exclude some search directions when we shouldn't. I am just trying to give you a broad overview which I hope you might find useful.
It's also worth revisiting what those distances are even used for. If it's just a general placement metric where we want specials a kind of hand-wavy distance away from a city border, it's not necessarily the case that we should even be scanning for city tiles but instead using some kind of approximation like distance-to-city-center - city-size
(180^2 + 180^2)^(1/2) ~= 255.5 so we could use uint8_t at the very least if we did cache it? (unless casting that isn't free?) It could probably be cleared after gen tho so you'd only have one matrix in memory at any time I think? closest_points_first is defo overkill given it's only getting a set distance ring (so it doesn't form a vector of the entire OM when max_dist_to_check is unspecified) each time even without any smarter logic like Renech's suggesting I just weren't aware this was going to be a performance issue. It also can't check between oms rn bc it would gen new oms during om gen recursively (the old method only cared about cities within the om too, we do now have oms without cities at high forestosity but that also breaks other stuff)
You could only use an unsigned 8 bit value if 255 means "at least 255 tiles away", as you won't find any "cities" out on the ocean (and it also has to work in mods that have no "cities", such as Innawoods). That's probably good enough, though. We may even want to lower the threshold for "far away from all cities" to something like 100, to cut down on processing (would need to check against existing JSON limits. I just know the Exodii warehouse has an outer range of 90).
A cache would be useless if it was dumped right after being generated. For it to be useful, it would have to be persistent and cleared only when invalidated.
The closest_points_first logic doesn't care about OMs, and the logic for checking points returns "no match" for locations that aren't generated (at the bottom of the call chain there's an operation that takes a position and returns a struct of an OM pointer and a relative position within the OM. The OM pointer is then evaluated, and a no match is returned if it isn't valid). However, I have to admit I haven't looked at the city distance calculation in detail (the above was about matching OMTs against matching OMT ids).
I also think there's merit in @kevingranade's suggestion. We may want to have a (relatively) quick distance logic for bulk use and only use a precise calculation for targeted checks (e.g. "how far away is the PC from a city?"), if we even have any such cases (I don't know if we do).
However, we could also see what it costs to create caches on OM generation (in which case generation of an OM would update distances within nearby OMs).
I don't understand what the #74191 testing would measure when it comes to city distances. I assume it would calculate the cost of calculating which tiles belong to cities, which is fine, but I don't see how that would exercise the city distance calculation logic apart from the placement of a limited number of specials). As far as I can see, one way to exercise the city distance logic is to search for matching locations with city range restrictions, preferably ones with a lot of tile matches (so only the distance calculations determine if there's a match or not) for a "random" match (so the search covers the whole area). That should be dominated by the cost of city distance calculations. You could also try to repeat the case prompting the writing of this issue, but that requires a suitable setup and an old version of master (as a PR has worked around the problem for that case).
I don't understand what the https://github.com/CleverRaven/Cataclysm-DDA/pull/74191 testing would measure when it comes to city distances
Aren't the bulk of city distance checks during special placement? I thought generating overmaps like that would place all the specials and why I'm suggesting the cache could potentially be limited to overmap gen if it's expensive to maintain, if it was 12% of overmap gen time when I tested it I feel like I would've noticed
You could only use an unsigned 8 bit value if 255 means "at least 255 tiles away", as you won't find any "cities" out on the ocean (and it also has to work in mods that have no "cities", such as Innawoods). That's probably good enough, though. We may even want to lower the threshold for "far away from all cities" to something like 100, to cut down on processing (would need to check against existing JSON limits. I just know the Exodii warehouse has an outer range of 90).
I'd forgotten or weren't aware closest_points_first was scopeless as such and could go into other OMs but the distance check is only checking within the overmap so I thought 255 would be the max and then could've been prefaced with a cities.empty() check
I'll try writing a get_points_rectangle_around( coord_point_ob, distance) and see if that helps to begin with bc I don't think that'd need to use an extra vector and initialise the points twice at least? (closest_points_first could potentially be rewritten so it doesn't do that either?) If anyone has an ideal test/situation to perf that'd be convenient
Where the bulk of the usage ends up depends on the distribution of the usage... EOC usage has exploded, but I have no idea to what extent it makes use of city distances, and there are mission target searches that take far too much time. Whether those constitute the bulk or just temporary (but long) bumps is something I can't evaluate.
closest_points_first is typeless at the core. Once the untyped points have been generated they're copied into a typed vector of the desired type (as you mentioned). It's then up to the user of this to determine how to use these points. In the case of distance_to_city, the code checks whether the tripoint_om_omt coordinate is in the city_tiles unordered set, which it obviously won't be if it's outside of the OM bounds, as the set is an OM element. As a result (and as mentioned) this also means shorter distances to cities in neighboring OMs are not considered, which probably has consequences occasionally.
An alternative to checking tiles at increasingly distance from a source location for membership within the city_tiles set could be to check the tiles within the city_tiles set for distance from the source location and keep the smallest distance. This would be more efficient than trying to find every tile within a large radius for membership in the set when the set is small. However, it might not be trivial to determine where the cutoff is.
- Search city_tiles and calculate distance for each tile (and keep the smallest) vs,
- Search each tile within a growing radius X for membership within the city_tiles set and stop when a match is found. Obviously, both suffer from the inability to account for closer cities in neighboring OMs.
Where the bulk of the usage ends up depends on the distribution of the usage... EOC usage has exploded, but I have no idea to what extent it makes use of city distances, and there are mission target searches that take far too much time. Whether those constitute the bulk or just temporary (but long) bumps is something I can't evaluate.
Mission target searches gen new overmaps, they shouldn't be calculating distance to city outside of that? EOCs shouldn't be (and aren't) doing hundreds of distance checks in 0 in game time unlike genning overmaps.
No. Mission target searches start with a pass to find existing targets only, doing hundreds of distance searches, and only get to a second pass where targets are allowed to be generated if the first pass fails.
What's actually calling the city distance check when searching for existing targets then?
That is a very good question!
The answer appears to be that it's during an attempt to place specials in already generated OMs. Thus, find only does actually try creation...
I had to try things again to find out, and it looks like a mess...
The first pass in find_or_create_om_terrain (in mission_util.cpp) sets "existing_only" to true, causing overmap_buffer.find_closest() to only search. However, immediately after that it checks params.create_if_necessary and calls overmap_buffer.place_special (which does a lot of city distance stuff), and if that was successful it calls overmap_buffer.find_closest again (which then should succeed, as the special had been placed somewhere unspecified, but it's rather wasteful to search for it again rather than keeping track of where it was placed...).
If that wasn't successful, however, the second pass is performed, where existing_only is set to false. This calls overmap_buffer.find_closest() again (as well as a second pass to create the special in existing OMs if creation failed). I guess this is where new overmap areas are actually created.
The call chain: overmap::distance_to_city() //Where my breakpoint is overmap::place_special_attempt() // checck if special.can_belong_to_city() overmap::place_specials_pass() overmap_buffer::place_special() find_or_create_om_terrain() // first pass within it
The answer appears to be that it's during an attempt to place specials in already generated OMs.
Oh right I forgot we do forced placements by default now, I hate it.
The way it's setup rn running an additional special pass on an already genned map is extra dumb imo, there's too much crap in the way for our dumb special placement that's splitting the map up into sectors that it's assuming are natural terrain bc it's not made to be ran multiple times. If I'm reading it right it basically does an entire normal gens worth of placement until successful except trying that singular special in all the sectors so yes that does explain why it's doing so many distance_to_city calls during the existing oms esp if the special itself is small but fussy. (eg motels that expect road so will fail often but are small enough that the sector size would result in alot of sectors)
I agree that it's unintentional it's trying to force placement before genning new oms in range.
As you say, placement in retrospect is very dubious, as it violates the assumed overmap generation order and the logic based on that. I can see a desire for specific cases (e.g. a UFO just landed, in some UFO mod), but if it's supported (somewhat poorly), it should be an explicit entry, rather than the hard coded only behavior. Also, if you want to change a generated map, you ought to be able to change viewed parts as well (with new support for a state of "this is what was, but needs to be updated to what is now" when it comes into view). Changing generated OMTs should probably be avoided though, since you can screw up so much with that (such as wiping out the PC's base, vehicles, and stashed stuff).
nb. just closest_points_first by itself is like 30% of the cpu taken when kicking off a fresh sky islands run. I can cut that in half with some more templates and inlining but that's still absurd.
Very likely that comment was accurate when it was written, and then the flood fill was added >_<
There seem to be several things that are conflated here:
- Distance to city as used for placing specials seems to be driving a lot of the overhead, and should not be doing any kind of flood-fill logic because the degree of precision needed is negligible. This should just go back to something like "distance to city center - city radius".
- map_in_city accuracy as reported in #74177 This wants higher precision, but I'm struggling to understand what the definition of that method even is.
I think a slightly different defintion of "map_in_city" that only requires a tiny amount of lookup would be fine for our purposes. For example if you look at the structure of a city, it's a network of roads winding through blocks of city buildings, right? What if "in city" is simply "within 3 tiles of a city-type building"? Then we do a TINY flood-fill on each invocation instead of flood-filling a whole city.
An alternative to get map_in_city working as currently implemented is to have overmap::place_cities() write an overmap-sized bitmap of "this OMT is city" booleans. That's 180x180 bits, i.e. 4KB, so it's sizeable, and depending on encoding gets enlarged a lot more when written to saves. An alternative is to have the flood-fill that currently happens run once on overmap load or generation and cache it with the overmap, but don't write it to saves. Either way that's not a negligible amount of memory to dedicate to something that is really a very minor feature. You could get much, much better efficiency with something like a quadtree instead of a bitmap since there's very high contiguity to the data, but we don't have a quadtree and that's getting a bit far afield.
The flood fill logic isn't being computed every time it's done once per overmap and that's it, the results are stored as a std::unordered_set<point_om_omt> which isn't particularly condusive with quick distance checks which is the issue, I originally wanted to use a bit matrix that would've probably been better suited for it unless that just falls down a coordinate manipulation pitfall but I were having problems implementing an efficient floodfill part with that, I think my horrible attempt is floating around discord history, the one time floodfill was insanely slow but that was probably just me sucking (Edit: Ew it was worse than I remember https://discord.com/channels/598523535169945603/598529174302490644/1204924908115861564)
That's my point, special placement doesn't NEED a precise check at all. The problem isn't that you're doing the initial flood fill (which I WAS misunderstanding, thanks for correcting me, also duh yea you can use a sparse coordinate map, that part's fine too), but that you overrode distance_to_city to do it's own flood fill (closest_points_first is also a flood fill!).
Basically just use something like distance_to_city_center - city_size for the check inside overmap_special::can_belong_to_city() i.e. revert that part of the change and remove overmap::distance_to_city() because it's dangerously expensive.
Alternately, was there ever an indication that the special placement code needed better precision? I don't see one.
Then maybe note the other findings about redundant mapgen work in a new issue.
As an aside, I had some ideas for speeding up nearest_points_first, which I'll go ahead and crack out while y'all hash out the algorithmic fixes.
Yeah nevermind there's no helping it. Replacing that hot loop with the non allocating version find_point_closest_first makes us spend maybe 20% less time in distance_to_city. So instead of being 60some% of the time taken it's like 50%. Fixing the heuristic is the only right call here.
The special placement check is back on its old logic, so the remaining questions are do we really need to be persisting this map of "tiles that belong to a city" and this very precise but expensive scan for "find shortest distance to a city tile". It's not currently causing problems but I predict if it stays implemented as it is now we'll see it again.
The map is something we can currently afford as it's very sparse, but it will very definitely blow up if we ever add whole-overmap cities, at which point that unordered map of tripoints is going to cost in the neighborhood of 650kB in memory and about 512kB disk space per overmap (before compression).
I'm not really clear that there is a use case at all for "scan in all directions until you find a city tile", it's very expensive and definitely not something we want triggered by something innocuous sounding like "distance_to_city()"
My strong recommendation is: Revert #81476 Revert #74191 Reimplement in_city() as "check distance_to_city() with a more generous bound check and then double check by searching a -3 OMT radius for a "city coded" OMT. Add a stub to save loading to ignore "city_tiles"
I added it bc Standing Storm wanted to be able to accurately tell if you were in a city or not with EOCs and I needed it for overpasses over big cities, notably both just only needing is x omt a city tile not how far away is a city tile from x. I can look at trying to change it to a bitset matrix instead to trim the memory right down, as I said that was my original intent I just couldn't get the flood fill to work efficiently but it was a long while ago so I might be able to manage it now
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not bump or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
I'm not sure why you're looping back to the bitset, why won't this work?
My strong recommendation is:
Revert https://github.com/CleverRaven/Cataclysm-DDA/pull/81476
Revert https://github.com/CleverRaven/Cataclysm-DDA/pull/74191
Reimplement in_city() as "check distance_to_city() with a more generous bound check and then double check by searching a -3 OMT radius for a "city coded" OMT.
Add a stub to save loading to ignore "city_tiles"
This is super trivial and should do the right thing as far as I can tell.
Like, if you're "inside the city radius", but there are no buildings within X OMTs, are you really in the city? What fails this kind of thing? Central park? Across a river from a city? Likewise, does it risk false positives?
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not bump or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.