Print

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

[Razzim]

Spoiler: NOT A PROMISED FEATURE JUST A PIPE DREAM DO NOT HOLD ME TO THIS (click to show/hide)

My dream of an "FPS manager script" for DF could become far more extreme now that I have source access, come to think, turn on the "experimental FPS maximizer" that automatically detects what the slowest parts of the code are and moves things around for you, with the caveat that certain bugs are likely to be ignored, or whatever. And obviously every parameter that could be changed by this would be in the settings somewhere.

Like, what I've got in mind is "below the minimum FPS? First speed up actions and world ticks to match desired FPS, and if that's not sufficient smoothly turn down the Z-level LoS short-circuit, then turn off temperature, then turn down X/Y short-circuiting to a minimum of 10, then..." sort of thing. PID it, why not.

Sounds very cool if by short-circuit you mean the los skip. But if its really just one variable I'd reduce it to, lets say, 10 and do a test first. We might be hyping over it and who know, maybe it won't change all that much because reasons.

And regarding the impact of pathing through a completely dug-out z-level, well fps gets considerably lower when I dig out everything, but nothing too crazy. Still much better than 1x1.

[Putnam]

If you'll believe it, that "pathing nightmare" there is significantly better for pathing performance than just mining out the whole Z could ever hope to be.

Incidentally, why's that? One would logically think that in the absence of obstacles A* should just find something pretty close to a straight line and be done with a minimum of CPU cycles. Is it because of the "high traffic" tile designations creating the possibility that there could be a less direct "high traffic" route forcing A* to look further?

edit: now I think about it, I can see how if there are multiple z-levels involved (pathing from one z-level to another) A* might have to hunt around a lot to find passes between the z-levels, if such passages are infrequent. Open areas would increase the search space. I'm still curious if the existence of high traffic designations makes all pathfinding more expensive, or if it's implemented using some hack.

A* is not a maximally greedy depth-first search, it's a breadth-first search with a bit of hinting. It'll still search a large chunk of the room with A*.

Traffic designations are implemented such that your dwarves have more expensive pathfinding than other creatures, but not significantly more expensive.

[Razzim]

Fun new data found recently:

32x1 embark is considerably better for handling both 500 dorfs (160fps vs 140fps) and 1000 dorfs (~50fps vs 64fps) than 16x1

50x1 embark is worse than 32x1 and comparable to 16x1 at 500 dorfs (135fps), but its still better than 16x1 at 1000 dorfs (58fps).

63x1 embark did not work at all, unfortunately. Crash on embark.

Edit: Nope, the performance advantage drops after a year or so, presumably because activity in the caverns.

[CyberianK]

This is really interesting. For me the question is if some of the costly calculations could just be delayed to happen only every X frames and maybe even staggered by number of Dwarfs and dynamically less regular as FPS worsens or if the game breaks down completely if that happens.

Like putnam specified LOS checks and family interactions took most of the CPU time in one of his tests. How often do those currently happen and it is crucial that they happen all the time or would the game break down if they happen half as much and could there be some failsafe to account for any frozen state that could occur because of it?

[Razzim]

This is really interesting. For me the question is if some of the costly calculations could just be delayed to happen only every X frames and maybe even staggered by number of Dwarfs and dynamically less regular as FPS worsens or if the game breaks down completely if that happens.

Like putnam specified LOS checks and family interactions took most of the CPU time in one of his tests. How often do those currently happen and it is crucial that they happen all the time or would the game break down if they happen half as much and could there be some failsafe to account for any frozen state that could occur because of it?

I think it might create more problems than solutions, but who knows.

And I need to correct myself - los skips do appear to work on z-levels. They are tricky though, as the additional pathing often counterweights the gain from los skip. And one has to keep in mind that when dorf is going down the stairway, then whole level can still calculate him for that 26 z-levels. Horizontal spread is better, z-levels work when you isolate the groups completely.

Also, there is a pretty easy way to make everyone in the fortress blind and then return them back to normal with a dfhack script. Ill post a script here on how its done after work, and Ill try to make it into a plugin for a dfhack release - it might be very helpful in times when you encounter an fps death, to get that additional fps needed.

Edit: something like that worked for me, its a full lua script

Code: [Select]

local utils = require('utils')

function blindify()
    local unit = {}

    for i, unit in pairs( df.global.world.units.all ) do
        if dfhack.units.isCitizen(unit) then
            unit.flags2.vision_missing = true
            unit.flags2.vision_good = false
        end
    end   
end

blindify()

To restore the vision, just change the variables and run the script again.

[brewer bob]

Also, there is a pretty easy way to make everyone in the fortress blind and then return them back to normal

I do not envy the life of a dwarf.

[Putnam]

This is really interesting. For me the question is if some of the costly calculations could just be delayed to happen only every X frames and maybe even staggered by number of Dwarfs and dynamically less regular as FPS worsens or if the game breaks down completely if that happens.

Like putnam specified LOS checks and family interactions took most of the CPU time in one of his tests. How often do those currently happen and it is crucial that they happen all the time or would the game break down if they happen half as much and could there be some failsafe to account for any frozen state that could occur because of it?

They happen every time dwarves are able to act and they need to happen every time dwarves are able to act, otherwise they will not react properly to their environment and will just stand there while a dragon is breathing fire at them et cetera.

[ayy1337]

They happen every time dwarves are able to act and they need to happen every time dwarves are able to act, otherwise they will not react properly to their environment and will just stand there while a dragon is breathing fire at them et cetera.

Might it be cheaper to check the immediate tiles in your vicinity for danger rather than looping through every unit in the game to see if they're nearby?

Could just manually search every nearby tile, which could be very slow, or breaking down the high level regions into subregions (9*9*Y tiles or 16*16*Y) and tracking which region a dwarf/object/dragon is in.
Also if your dwarf doesn't notice a dragon 26 tiles away for 2 ticks is it really a problem?

Edit: Say if you keep a list of all tiles currently the target of a hostile action, like dragon breathing fire, and its source, check the zone around that for creatures that need to respond. Dragon attacks occur much much less frequently than every tick so that would be much cheaper than checking every creature every tick.

[LuuBluum]

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

[ayy1337]

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

With the dragon, you could still know a dragon is around reasonably well if you check LoS every say, 2, 3, or even 5 ticks. And by combining that with the check i mentioned where you have a hostile action even if some really fast creature manages to gap close too fast, you can respond to the attack itself.

Also, there's not _that_ many units, but if you're doing nested loops over a couple hundred or a thousand units every tick evidently it can get pretty slow - in the OP he says going from 1000 units to 2100 decreased the FPS from ~50 to about 16, about 3 times worse for a doubling of units which sounds like something is scaling nearly quadratically with unit count.

[LuuBluum]

Well we know it's scaling quadratically because it's an O(n^2) check— every unit against every other unit.

There's also just the fundamental issue that, more often than not, if you're in a situation where there are a lot of units (say, a siege), they're also probably clustered together closely enough that they're gonna be triggering the LoS check code no matter what you do.

[ayy1337]

Another issue I just thought of.. If you do have that cluster of units, which is going to happen not just in sieges but in all your meeting halls, dining areas, dormitories, inns, temples, etc..
Each dwarf is going to do a detailed LoS check for every other unit in its vicinity, checking the tiles around it repeatedly, which sounds like the more-expensive part of the calculation than checking if their distance is <27
If you have to do a scan of the tiles around the dwarf for LoS to 20 units you're potentially scanning the same tiles 20 times , although that would be the worst case where they are all standing in roughly the same direction from you (edit: actually, isn't the worst case that you don't have real LoS to them, so you exhaustively check every tile you do have LoS to? not really sure how that works); might be quicker to exhaustively check all the tiles around the dwarf once if he's in a densely populated area, and this would at least scale only linearly with number of dwarves.

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.

[Putnam]

They happen every time dwarves are able to act and they need to happen every time dwarves are able to act, otherwise they will not react properly to their environment and will just stand there while a dragon is breathing fire at them et cetera.

Might it be cheaper to check the immediate tiles in your vicinity for danger rather than looping through every unit in the game to see if they're nearby?

Could just manually search every nearby tile, which could be very slow, or breaking down the high level regions into subregions (9*9*Y tiles or 16*16*Y) and tracking which region a dwarf/object/dragon is in.
Also if your dwarf doesn't notice a dragon 26 tiles away for 2 ticks is it really a problem?

Edit: Say if you keep a list of all tiles currently the target of a hostile action, like dragon breathing fire, and its source, check the zone around that for creatures that need to respond. Dragon attacks occur much much less frequently than every tick so that would be much cheaper than checking every creature every tick.

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

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

[ayy1337]

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

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

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

Idk how either of those works in detail, can you explain? I was thinking that you can just check if the two creatures have the same sight characteristics, and because most will, you'll still get the benefit of not having to check line of sight twice in most cases, even if you have to check both ways for pairs that have different characteristics.

[Putnam]

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.

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