Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[ayy1337]

Yeah, unfortunately, that "most" happens to not include dwarves, who can see further underground than most, and also doesn't include goblins, who can be seen further underground than most.

I still don't see the problem, since dwarves looking at dwarves will have the same stats, which is going to be the most common comparison by far. Even if the two units have different sight characteristics, if you are lucky (50% of the time) you'll get the unit with shorter sight of the pair first and not have to check LoS the other way.

Maybe there should be a data structure that stores information about the location of things in the map then?

The way the game is structured is already a nightmare for the cache, which is the actual largest cause of performance issues; just improving cache locality on units a little improved performance by 60%, yet more big ol' structures isn't going to help; moving unit positions out into their own array is likely to be the biggest gain, funnily enough

Storing information about which units are nearby is fundamentally going to be faster than figuring it out every frame by doing a nested loop over all the units, regardless of whether the current structure of the game sucks.

[Putnam]

"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.

[ayy1337]

"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.

It's not storing the information though is it, because every frame the information about which units can see each other is dropped and has to be regenerated from scratch; every calculation about every pair of units has to be done again, in both directions.
Also while the game map isn't fixed like an RTS game, lots of the map does actually change very rarely; my dining hall once constructed is likely to remain as it is for a very long time, measured in frames. These rooms are also ones which the player can define themselves, and are where most dwarves spend the most time, and are most likely to congregate in a high density.

[LuuBluum]

Sure, but the map is changing all the time. Trees are growing. Water and magma can mix. Doors open and close. The map is changing all the time in ways both subtle and not, and a good deal have nothing to do with player intervention. This happens on a frame-by-frame basis, completely throwing out anything that may happen from the last frame. Whether or not one unit can see another is what can determine whether or not someone notices someone steal an artifact, and the frame that a door closes can decide whether or not that was seen. No amount of caching the last vision check can fix that without re-running that vision check every frame. The best you can realistically hope for is cache locality by shoving all the position data into the same contiguous region of memory (which is what Putnam already did as per the above).

It's not storing the information because that information becomes useless the next frame.

[ayy1337]

It's not storing the information because that information becomes useless the next frame.

The information isn't always useless in the next frame though is it. If you have two units in a room and no visibility changes happened to the tiles in the room since last frame, until someone moves you don't have to re-check LoS. If the room is small enough that every unit can see every other unit, you don't need to check for LoS changes even if they move around. This would make the LoS cost basically zero for that whole room, regardless of how many units are in it.

[LuuBluum]

Yes, but there lies the rub. How do you know? The only way to know, is to check. You're quantifying things like "room" and "visibility change", but that's not how the game is structured. If I had to guess, it's just one big ol' array of tiles, and a big ol' vector of units. And now, evidently, an array of unit positions (or vector? But what is a vector but a fancy array?). There's no notion of a "room" outside of something like a defined room, which has no real attachment to any of this code at all (and would make no sense at all to try and make work that way because rooms occupy so little of the actual map and don't apply to things like adventure mode at all). How do you know what doors opening/closing impact what units' line of sight?

Like... the only time that you can make the assumption that the LoS code doesn't need to be run a second time, is if two units occupy the same/adjacent tiles. Checks that are already trivial to do.

[ayy1337]

There's no point suggesting improvements evidently so I won't waste my time anymore, have fun.

[Bumber]

If I had to guess, it's just one big ol' array of tiles

Structs representing 16*16*1 tiles. There are multiple 16*16 arrays in the struct for various attributes. There's also a struct representing 48*48*z_max tiles, which stores stuff relating to the embark tile.

See: https://github.com/DFHack/df-structures/blob/master/df.map.xml