Print

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

[Jeoshua]

Alright, let's ignore the fact that calculating stuff based on tensile strength or what-have-you would probably inflate the time taken and assume 5 nanoseconds.

No, let's assume a more realistic value then.

Now at modern processor speeds, each clock cycle takes 0.0000003814697265625 seconds, at 2.5 megahertz.  That translates to .38 ns per clock cycle.  In each clock cycle the processor is capable of adding two 32-bit numbers together, at the very least.

So allowing for memory access wait times and all that.  What do you think is fair?  10 clock cycles? 20?  Let's say 20 clock cycles per tile calculated, with all manner of crazy calculations and mathematical trickery.  Squares and cosines and all that jazz.  That brings the total to 5ns + (0.38 ns * 20) = 12.6 ns.

Okay.  So we have 13 ns per tile, with WAY more calculations that we've actually set forth to be calculated in any model suggested or considered.  Now let's calculate every tile which is touched in an area both above and below the tile.

Each embark tile is 64x64 tiles, or 4096 individual tiles, multiplied by whatever depth.  We'll assume a 64x64x64 block.  Now, over half of these tiles are not directly connected to the tile in a diagonal above or below fashion, actually exactly half now that I think about it.  So that's 131072 individual tiles that would need to be calculated.

So we're at 1,651,507.2 ns per embark tile that would need to be calculated in an absolute worst-case scenario that has absolutely no optimizations, all with an algorithm way more advanced than the one being considered.  And that comes to 1.65 seconds.  Total.  For almost an entire map's worth of tiles.

Keep in mind that at a certain point, that tile isn't really affecting the tiles below it since the amount of weight bring distrubuted would have been spread out so much that it wouldn't be adding any significant weight to the tiles below it.  So there are optimizations that could be put into effect to lessen the amount that needed to be calculated.  And this whole thing is only happening when a tile is being actively checked for it's support.  So a realistic value of time is much lower than this figure, probably at least a tenth of that.


Did the math scare everyone away?

TL;DR - Even if you assume worst case scenario, the lag issue is overblown.  Math above.

[King Mir]

Finding an exact number for typical memory access time isn't trivial. A processor has several stages of caches, The cost of a cache miss is about 10 times longer for each one, with access to memory being the longest. However, memory is fetched in batches, so successive accesses after the first byte are much faster. The data rate for memory is the bottle neck in for the successive calls. Then you have to estimate the cache miss rate.

Top of the line RAM has peak access time of 0.23 ns per Word. Finding an number for cache miss time is harder, as it's not so readily advertised.

[NW_Kohaku]

Yes there are cases where small lag adds up, but this isn't one of them.

You're missing the point - I'm saying that all causes of lag add up.  Weather adds lag, temperature adds lag, fluid checks add lag, connectivity checks add lag, status checks add lag, contaminant spread checks add lag, etc. etc. etc.

You can't pretend only the single largest cause of lag matters.

This is especially true when you consider that pathfinding is only usually the largest cause of lag - the whole point of the Operation FPS Bomb tests were to prove how much item counts alone can add lag to your game.  1,000,000 boulders in the game will crash FPS down to .1 FPS before ever having to pathfind anything. 

Causes of lag add up in all cases, because every algorithm is handled sequentially (there is no parallel processing in DF), so everything is a bottleneck. 

Why would it take a tenth of a second per tile? that'd be extremely slow. Memory access is on the order of nanoseconds, not hundred milliseconds. And with tiles in an array, there is a certain amount of pre-fetching and other CPU optimization that makes it so that accessing a lot of tiles is faster per tile than accessing one tile.

It's still only happening only when a tile is mined.

And hundreds of tiles at 5ns a tile is not a significant portion of a second.

You're still ignoring that "just memory fetching a tile" is the exact reason Pathfinding is so slow. 

I'm not kidding when I say "cascade" testing support stresses from all the items at the top of the map downward is basically the exact same formula as pathfinding from every tile on the map.  (Except that it would be an inverse formula - pathfinding increases in complexity exponentially the more open space you dig, while support stresses would increase in complexity the more walls you have.)

Jeoshua's calculations aren't quite correct.  For starters, it's 48x48 tiles per embark tile, but standard maps will have something like 192x192 tiles plus at least 100 z-levels, adding up to around 4 million tiles.

5 nanoseconds is also an underestimation of memory fetch times in most cases - CAS latencies will usually be more in the range of 7-15 ns per fetch request.  And that's only for the first word read. 

You will have to sequentially access data from essentially every tile on the map, which takes almost a million of memory fetches on larger maps, and a million of memory fetches at "just a few nanoseconds per tile" of 10 nanoseconds adds up to 10 seconds.  Per tile you mine. 

PLUS you haven't even started pathfinding or doing fluid motion checks or anything else that adds all the lag we have in the game already.

Finding an exact number for typical memory access time isn't trivial. A processor has several stages of caches, The cost of a cache miss is about 10 times longer for each one, with access to memory being the longest. However, memory is fetched in batches, so successive accesses after the first byte are much faster. The data rate for memory is the bottle neck in for the successive calls. Then you have to estimate the cache miss rate.

Top of the line RAM has peak access time of 0.23 ns per Word. Finding an number for cache miss time is harder, as it's not so readily advertised.

Caches don't matter.  Not when you're loading several megs of data, you're not going to cache that - you have to load from RAM, because the computer is not going to be able to properly anticipate where the next RAM load is, and you're going to have to wait on a full RAM fetch.  That's why pathfinding takes so long, because it's the exact same thing.

[Jeoshua]

Your definition of "lag" seems to be "processor execution" NW.  If everything on that list causes "lag", then the game itself causes "lag", windows causes "lag", and computers only ever "lag".

Yes.  This would take some execution to run.  But if the number doesn't go up exponentially as the fortress gets older, it would not contribute to FPS death.  So there's a mechanic that should be avoided.

Therefore:

Abstraction/Optimization 1:

• Support can extend laterally or vertically
• [COMPRESSIVE_FRACTURE:x] used to determine amount of weight coming in before the support breaks
• [COMPRESSIVE_YIELD:x] used to REDUCE the amount of weight the support transfers to the next tile
• If (Weight Transfered) + (Weight of Tile Itself) / Number of potential supports < COMPRESSIVE_YIELD, tile is considered "fully supported" and calculations end.
• Any change to local environment (Fracture breaks) flags it's neighbor to be checked NEXT Tick.
• Limitation on the amount of checks done per turn.  Suggestion: 65x65 = 4225 tiles, or a one-embark-tile-sized z-level

With objects featuring the STONE_TEMPLATE values, a rock will take the burden of an entire other rock and not transfer any extra weight, save it's own.  It does flag any rocks checked to be checked for support next round, however.

A STONE_TEMPLATE object would break from having to hold up twice it's own weight on it's own.  That is transfered weight, not intrinsic weight, so and number of z-levels of STONE_TEMPLATE will easily hold each other up.  Water would not fit this calculation and would fall if modeled as a particulate solid.  Metal would hold up more weight as its yield and fracture are higher.  Wood would do a fairly poorer job and would require, therefore, more closely spaced supports.

Upside down pyramid shapes would likely crush the bottom support and multi-tile columns that start wide but become thin would be more prone to fracturing under their own weight.

SOIL_TEMPLATE itself would need to be updated to allow for more realistic values.  Right now it's just a copy of stone and would exhibit no different behavior than STONE_TEMPLATE, but ideally it should require more support, possibly as bad as 1 every other tile for sand.

The flagging of calculations for next tick both spreads the calculations out over time but also simulates inertia very nicely.  The end result of this would be a set of support calculations "flowing" through the map for short distances, rather than everything calculating at once.
... It also gives a dwarf a chance, however slim, to outrun a cave-in.

[NW_Kohaku]

Your definition of "lag" seems to be "processor execution" NW.  If everything on that list causes "lag", then the game itself causes "lag", windows causes "lag", and computers only ever "lag".

That is what "lag" is - the period of time it takes to process. 

Yes.  This would take some execution to run.  But if the number doesn't go up exponentially as the fortress gets older, it would not contribute to FPS death.  So there's a mechanic that should be avoided.

It doesn't lead to FPS death because it starts out slow enough to make nobody want to play. 

Nobody's going to play DF when mining causes the game to hang for a couple seconds every time a new tile is mined.

Therefore:

Abstraction/Optimization 1:

• [COMPRESSIVE_FRACTURE:x] used to determine amount of weight comming in from above before the support breaks
• [COMPRESSIVE_YIELD:x] used to REDUCE the amount of weight the support transfers from a tile above to one below
• Any chance to local environment flags it's neighbor to be checked NEXT Tick.
• Limitation on the amount of checks done per turn.  Suggestion: 65x65 = 4225 tiles, or a one-embark-tile-sized z-level

With objects featuring the STONE_TEMPLATE values, a rock will take the burden of an entire other rock and not transfer any extra weight, save it's own.  It does flag any rocks checked to be checked for support next round, however.

A STONE_TEMPLATE object would break from having to hold up twice it's own weight on it's own.  That is transfered weight, not intrinsic weight, so and number of z-levels of STONE_TEMPLATE will easily hold each other up.  Water would not fit this calculation and would fall if modeled as a particulate solid.  Metal would hold up more weight as its yield and fracture are higher.  Wood would do a fairly poorer job and would require, therefore, more closely spaced supports.

Upside down pyramid shapes would likely crush the bottom support and multi-tile columns that start wide but become thin would be more prone to fracturing under their own weight.

SOIL_TEMPLATE itself would need to be updated to allow for more realistic values.  Right now it's just a copy of stone and would exhibit no different behavior than STONE_TEMPLATE, but ideally it should require more support, possibly as bad as 1 every other tile for sand.

The flagging of calculations for next tick both spreads the calculations out over time but also simulates inertia very nicely.  The end result of this would be a set of support calculations "flowing" through the map for short distances, rather than everything calculating at once.

I doubt we're going to find a way to institute "proper" stress "cascade" support.  Even if we throw aside the fact that we'd be asking for a full architecture-worthy stress modeling program to run at the same time as the rest of the game, there's the fact that it's going to be almost impossible for a player to actually read the meaningful data.

How are you going to look at any arbitrary limestone wall 6 z-levels down, and tell whether or not the amount of stuff you've excavated overhead is putting a significant load upon a limestone tile?  Are you going to have to keep in mind the relative densities of the sand versus those shale tiles versus other materials?    What if you were carving through gneiss instead? 

You'd have to convey to a player trying to build a tower which materials had the highest tensile strength or compressive fracture points compared to their density if they wanted to have something to build at the ground level versus top floor of their towers.  The game doesn't tell you anything about these data points, you have to open up the raws to know. 

Upside down pyramids are pretty much going to have to be a problem we live with in this game.  The "no more than X tiles of overlay" is far from an ideal solution, but it's also a significant step up from what we have now...

[King Mir]

The discussion of whether a detailed cave-in system would be a notable performance penalty is getting tiring. I don't think it would be, mainly because it only triggers on mining. I don't care to do a more detailed calculation to guess the actual penalty. I described how to do it in my last post if anyone wants to though. Cache does matter, because it facilitates pre-fetching, though it doesn't matter nearly as much as other applications where the entire array fits within the cache. It also matters because the penalty for a cache miss is a CPU feature, and not entirely calculable from memory latencies.


On a different note, with regards to display:
I think the way to have a complex cave-in system and display it to the player is to have a separate view similar to Depot access mode that displays the stresses on each tile. In most cases, a few rules of thumb, like don't have rooms that are too wide without support would be sufficient for the player to know. But anyone building or digging a weird structure could look at the fort in force mode to figure out what will work, and what needs more support.

Temperature could benefit from a similar view.

[Jeoshua]

I don't really prefer to discuss reasons for things not to go in past "already exists" or "too hard to use".  But in this case I had to make a breakdown of a worst case scenario then overcome it with simple logic.  The system I outlined took like 30 minutes to think up and would have nearly no hit on performance.

The ultimate moral is: If you make it right it won't have a performance penalty.  If you brute force it it could.  And people who want it will find ways to make it work, people who are convinced it won't will find ways it can break.  If both sides hear each other out there are ways around every concern, and none of the potential concerns are stupid... unless of course they're just misinformed (but I haven't seen anyone like that yet in this thread).

In regards to display, I'd say that while it would be nice to have one, it's not absolutely necessary.  If a cave-in system is created and implemented that is logical enough, it should be good enough to look at a wall and tell that there isn't enough support.  You wouldn't be able to know exactly how many tiles you'd need to go out for it to collapse, but that could be determined through trial, error, and a bit of common sense.

We don't have a system that shows temperatures. We don't have a system that shows the spread of vampirism.  We don't have light meters that show where darkness is.  We don't have a lot of readouts of things we have already.  All of these could benefit from some kind of display, but the mechanics behind them still occur.  Why does a cave-in map have to be any different?  Why should the mechanical stress applied on rocks be displayed in any way?  Does the current system of output show you which pieces of lava and water are under pressure?  Does it really differentiate visually between aquifer and non-aquifer?

Basically, there are those that deffinitely WANT mechanical stresses (and temperature and water pressure and what-not) to be displayed on-screen.  But it's not really a "NEED".

[GreatWyrmGold]

Why does a cave-in system need some way of warning you? Well, first off, dwarves should be able to tell how much more they can mine before bringing the fortress in on itself.

More importantly is a reason for which I was considering rejecting the whole "improed cave-in system" idea, period. You don't want to be making a great dining hall only to discover that you made the ceiling too thin, causing your workshops and part of the dormitory/bedroom complex to collapse, ripping a huge hole through your dining hall into the caverns and releasing a few flying FBs. Of course, that's a worst-case scenario, but each part is possible. One wrong tile mined, and your fort will collapse unless you figure it out in time? No thanks. Hence, a system of cave-ins must be simple enough to describe in one, short sentence without the word "realistic," unless you have some way to inform players that removing this tile of rock will cause a cave-in.

[King Mir]

If a player is doing typical stuff, then I agree that simple rules are necessary. But if a player is making modern art, trying to push the limits of what what rock can hold, then I don't think it's bad to require the player to learn more complicated rules, provided that either those rules are still readily known, or there is an indicator of some sort when there is a danger of a cave in.

Also, a good cave in system could stand to benefit from a good system for earthquakes!

[GreatWyrmGold]

If you want a system more complicated than the 0.23 one, you'll need some kind of display for showing how much stress the rock is under, and maybe one for how much stress it will be under once you mine out these rocks/build these constructions.

The cave-in system would help that.

[therahedwig]

How about a half-half solution: Limited information system?
Instead of saying 'this'll collapse', 'this won't', the player gets a marker of 'this is dangerous' 'this isn't'. The difference being that dangerous means that the construction is fragile, isn't supported enough. It would be indicated while designating by making the designation squares red.

This way, people who just want to build a stockpile room or a dining room only have to avoid red squares, while people who want to create a intricate statue or whatever will need to learn the finer rules of dwarf fortress engineering.

[GreatWyrmGold]

It's a possibility.

[NW_Kohaku]

The problem is, again, what about people who want to plan out a large castle or tower, or are in the middle of excavating a huge dining hall. 

If you just start designating without paying attention to it, you could collapse your whole fort in on itself. 

If you start building a tower, you have no in-game clue as to how strong or how heavy any given building material is. 

Before you can demand that players start having "realistic" thicker foundations and use lighter building materials at the tops of their towers, you have to actually tell players which materials are stronger, somehow.

Otherwise, how am I supposed to know if dolomite is a better wall material than limestone or granite?

[GreatWyrmGold]

Trial and error.

Not a good answer, mind you, just an obvious one.

[therahedwig]

It be historically accurate...

An art historian once told me that during the middle ages, when the cities were growing more prosperous and everyone wanted one of those fancy Gothic cathedrals, their understanding of engineering was actually much poorer than the final product would suggest. she told me there's a lot of records of these buildings being almost done before the construction cracked and everything collapsed. Those buttresses you mentioned were designed out of trial and error.

Another interesting thing she told me was that because everyone wanted these buildings to be made, there were these traveling bands of masons and architects going around and offering their services. And my brain is relating this to bauhaus somehow, I think it's because bauhaus took their teaching system from these bands?

Maybe having a good architect in your fort would show estimates of the qualities of the stone as you select it for construction.