Bay 12 Games Forum

"Storing information about which units are nearby" is fundamentally equivalent to figuring it out by doing a nested loop. This is collision detection, and a lot of the optimizations requires various assumptions that we simply do not have the ability to consume. In fact, we're already doing one of the biggest optimizations, an axis-aligned bounding box, checking if the other object is within a 53x53x53 AABB with its center at the dwarf. This is a known problem, it's not like I haven't done research into all this.

You'll find that the vast majority of the optimizations there contain such phrases as "Where most of the objects involved are fixed" or "that approach is well suited to handling walls and fixed obstacles in games". Dwarf Fortress doesn't have those, so a lot of the optimizations would be costly to implement in the first place. You can't "pre-bake" stuff into a map that changes all the time.

Creatures keep track of their own positions, there's no concept of "checking tiles in the vicinity" except checking every unit to see if they're nearby, these are synonymous with the way the game is structured

Quote from: ayy1337 on April 17, 2023, 06:31:45 pm

Edit: Possibly in the current way you could reduce some of the work by saying if dwarf A has line of sight to B on this tick, assume B has line of sight to A unless he has different sight distance. Yay still waking up. I think this would reduce the number of checks you have to do by about half, assuming most units have the same sight distance.
Also, maybe you could defer LoS checks for pairs of nearby creatures that you just checked - If I had LoS to you last tick, and we're still more or less in the same room, don't check LoS again.

Can't, low-light vision and glowtiles means that A sees B does not imply B sees A

I think the "stand there while a dragon is breathing fire at them" example wasn't an issue with not checking the tile they're standing on frequently enough for environmental hazards, but identifying that there's even a dragon there in the first place that they should be concerned about. Checking for "tiles currently the target of a hostile action" doesn't solve the issue of fleeing from the dragon in the first place, which was the main point.

As for breaking up the whole thing into a grid, that doesn't work nearly as well as it sounds due to the joys of the million-odd edge and corner (literally) cases. That and maintaining such a large structure and having to shuffle around which units are in which box, more often than not, will be more expensive than just checking against every other unit on the map, doing a quick "is it 26 units away?" distance check, and if not, then doing a line-of-sight check.

The game is, from a technical standpoint, sparse. Very large map, very few units. There are times where there are a lot of units (sieges, namely), but we're still talking a drop in the bucket compared to the size of a map (tile-wise a map is about 100 levels tall and hundreds of tiles across). Subdividing the search space only makes sense from an optimization standpoint for dense, not sparse, situations, usually (caveats always apply of course).

The game already splits accessibility into subregions, that's kinda the problem. Having more subregion maps for pets, flying units etc. would be a performance disaster, nevermind everything else.

Quote from: ayy1337 on January 31, 2023, 06:39:54 pm

You can do O(1) existence lookups, like say a hash table of creatures in the fort

Sure, why don't you get right on that.

I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.

The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.

The slowest individual thing in the fort was checking family relationships. This was mostly, so far as I could tell, called in the context of watching performances, probably to tell if they should be feeling love at their family members or whatever. This was 9% of CPU time. 15.537 in the function.

Next is getting glowtiles. This is required for line-of-sight tests, naturally. Glowtile'd creatures are visible from farther in the dark. 5.7%. This is the slowest part of line-of-sight checks, at least as far as stuff that's actually done. 11.749s.