Print

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

[LuuBluum]

The data structure doesn't matter here. The point is that it's checking every unit against every other unit to work out whether or not they can see each other. This is, fundamentally, O(n^2). The problem isn't actually evaluating the line of sight. The problem is having to, per  unit, check against literally every other unit on the map, is slow in principle. Limiting it to a rectangle would trade-off O(n^2) for O(Pn) where P is the number of tiles in this rectangle. Depending on the size of P, this might not scale as well as you'd hope; it only becomes more efficient once you have more units than P. Meaning if you're checking, say, a 10x10 rectangle around every unit, that this only becomes more optimal at 100 units on the map or more.

I think a more immediate optimization is clearing out dead units from the vector. Yes, removing from the middle of a vector isn't optimal, but that doesn't matter because this is a one-time event any time a unit dies/leaves. Just make it a periodic check when iterating through the table that if any of the pointers refer to dead units, to delete them from the vector before continuing.

[anewaname]

How do items fit into this modelling of the Observation code? A dwarf sees a severed limb on the ground and knows if it belongs to a dead or living unit.

[Putnam]

Guys, the ideal data structure would be a hash table, e.g. std::unordered_set, no? O(1) insertion, deletion, iteration, at least in theory. At most there could be some data locality issues with jumping between different buckets.

EDIT: Also there is probably something clever you might do for line-of-sight checks. Creatures can only see so far, right? Assign each creature to a set of rectangular blocks which they might potentially be able to see in, then only check line-of-sight in those blocks.

Iteration on unordered_map is likely to be worst than iteration over a vector, and iteration's the one thing you'll be doing most here. Iteration can't be faster than O(n). If you have a quantum computer, linear search is O(sqrt(n)), but that's not terribly relevant.

That second bit is quadtrees etc., which could work but has overhead unto itself.

Every unit must check every other unit to see if they're in line-of-sight; this is actually basically unavoidable. It's not the line-of-sight checks that are the problem, it's the checking for line-of-sight. Skipping over units that literally cannot be seen by anyone even in principle takes up more CPU time than pathing.

thanks for the clarification. this truly is something us players cannot avoid.

I love the idea that you drop this info less than a month away from the new release - after years and years of (what ultimately appears to be) superstitious rituals in the name of saving FPS.

Yeah, sorry, I got into profiling in earnest after I learned how easy it was working on Cataclysm DDA and auxmos, started doing it to see if I can find any funnies, eventually figured out what pathfinding was by getting a real bad FPS death fort with tightly-closed doors and seeing the big problem there... it took me a while for a few reasons.

How do items fit into this modelling of the Observation code? A dwarf sees a severed limb on the ground and knows if it belongs to a dead or living unit.

It honestly probably just goes through the corpses vector, which is only in-play, active corpses. Not nearly as much worry.

[CyberianK]

Very interesting, thanks for posting this. Do above ground fort areas, big rooms with lots of workshops inside and big dormatory/dining room/tavern make massive difference in these calculations?

Reason why I ask is because I have pop 80, 2x2 forts that follow all FPS advice I studied in dozens of hours and experimented 100s of hours with but I still get FPS issues after 5-10+ years.
I always use big rooms like that instead of lots of small rooms so maybe that's bad too because theres more exponential interaction between creatures in the same room/line of sight?

[Putnam]

Very interesting, thanks for posting this. Do above ground fort areas, big rooms with lots of workshops inside and big dormatory/dining room/tavern make massive difference in these calculations?

Reason why I ask is because I have pop 80, 2x2 forts that follow all FPS advice I studied in dozens of hours and experimented 100s of hours with but I still get FPS issues after 5-10+ years.
I always use big rooms like that instead of lots of small rooms so maybe that's bad too because theres more exponential interaction between creatures in the same room/line of sight?

Recent testing suggests "not really". Been running a 6x6 fort with 70-80 citizens entirely above-ground at 30 FPS for 6 (8? I forgot to note down the year the fort started lol) in-game years now.

The problem isn't the interactions, the problem is checking for interactions. Every creature must check every other creature no matter what, essentially. There's optimizations to be made there with sectors etc. but the overhead might not be worth it.

[mightymushroom]

Limiting it to a rectangle would trade-off O(n^2) for O(Pn) where P is the number of tiles in this rectangle. Depending on the size of P, this might not scale as well as you'd hope; it only becomes more efficient once you have more units than P. Meaning if you're checking, say, a 10x10 rectangle around every unit, that this only becomes more optimal at 100 units on the map or more.

Just to say, the example of P=100 could make it sound as if there might be a reasonable inflection point where the savings is worth it in the case of large, populous fortresses. Alas, this discussion – http://www.bay12forums.com/smf/index.php?topic=180525.msg8425293#msg8425293 – declares that legendary Observers have a vision radius of 25 tiles. Extended in all possible directions, I think(?) that's a "theoretical" detection volume in the neighborhood of P=125000 tiles as the game currently stands. Edit: no, messed that up in my head. Nearer to P≈25000?

[bloop_bleep]

The data structure doesn't matter here. The point is that it's checking every unit against every other unit to work out whether or not they can see each other. This is, fundamentally, O(n^2). The problem isn't actually evaluating the line of sight. The problem is having to, per  unit, check against literally every other unit on the map, is slow in principle. Limiting it to a rectangle would trade-off O(n^2) for O(Pn) where P is the number of tiles in this rectangle. Depending on the size of P, this might not scale as well as you'd hope; it only becomes more efficient once you have more units than P. Meaning if you're checking, say, a 10x10 rectangle around every unit, that this only becomes more optimal at 100 units on the map or more.

The data structure was about storing units in such a way that there is fast deletion and iteration. By O(1) iteration I meant O(1) from one unit to the next. The data structure is not for speeding up individual 1-on-1 sight checks.

I've realized that the fastest solution is very simple. When deleting a unit, swap the unit in the vector with the last unit, then remove from the back. Remember, order doesn't matter.

The second rectangular blocks part was about eliding unnecessary sight checks. Also, your 100n estimation for the blocks approach is off. You don't check every unit against every tile in the block, you check every unit against every other unit in the block. If there were 5 units in each occupied 10x10 block, then there would be 4n sight checks.

In general the time complexity is O(mn) where the parameter n is the number of units and the parameter m is the quadratic mean average number of units in each occupied block. Asymptotically there are far fewer units in each occupied block than there are units on the map. Thus this gives almost linear performance
 as long as the units are decently spread out.

[Putnam]

You also have to check every unit in the surrounding blocks, mind, else you get weird behavior on block edges.

[bloop_bleep]

You also have to check every unit in the surrounding blocks, mind, else you get weird behavior on block edges.

You're right. You could check every block that intersects the unit's view rectangle. Should be at most 4.

[Inarius]

Very interesting, indeed

[LuuBluum]

Don't forget that you're operating in 3 dimensions, here, though that won't add much overhead.

But yeah, chunking out the map into a series of 24x24x24 blocks isn't unreasonable. Then you'd have a (constant-sized) vector of... unordered maps (iteration is as cheap as any other and inserting/erasing should be constant on average). On each unit update, add a check for x/y/z divided by 24 before and after their move to work out what box they were in and what box they should move to. Depending on whether DF uses C++17, you can even do fancy things like extract the nodes so there's not even a memory overhead of moving the entries around. Then instead of checking against every unit in the game, you check against every unit in 27 24x24x24 boxes.

I think you'd still end up checking against a whole lot of units this way, though.

[PHLP_Neo]

So I guess I need to sell that cage in my fortress with 300+ chicken inside?

Do you think I need to wall off all the cave entrance, or maybe even extinct the local fauna? Sometimes there are more wild crundle in my map than my dwarves, which according to your study is a pretty bad thing.

[Salmeuk]

So I guess I need to sell that cage in my fortress with 300+ chicken inside?

Do you think I need to wall off all the cave entrance, or maybe even extinct the local fauna? Sometimes there are more wild crundle in my map than my dwarves, which according to your study is a pretty bad thing.

actually, this is a good question: do creatures inside cages perform this "unnecessary sight-check", or are they exempt? AFAIK creatures cannot spot intruders from within cages..

[A_Curious_Cat]

So I guess I need to sell that cage in my fortress with 300+ chicken inside?

Do you think I need to wall off all the cave entrance, or maybe even extinct the local fauna? Sometimes there are more wild crundle in my map than my dwarves, which according to your study is a pretty bad thing.

actually, this is a good question: do creatures inside cages perform this "unnecessary sight-check", or are they exempt? AFAIK creatures cannot spot intruders from within cages..

<snip>

A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost;

<snip>

(emphasis added)

[Salmeuk]

thanks. I am a lazy bastard