Print

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

[10ebbor10]

Couldn't you work with asynchronous systems. Ie, the to be collapsed tiles are dropped into a queue and then checked while the games goes. This will use a more RAM, but allow the game to maintain a steady FPS. Besides, an unsecured roof doesn't always collapse immediatly, so maybe a chance based timer for every tile the game deems insecure. And once one tile fals it triggers all weak tiles near it.

You would need to have a seperate systems for floating blocks though, or it would get strange as a block hangs there for a month or two while the systems resolves all possible collapses.

[GreatWyrmGold]

So, every tick, a tile is checked or something? Less bad, at least.

[Jeoshua]

I would say that any cave in system added would have to somehow take account of the material properties of the actual materials which are being worked on at the time.  As it stands, EVERY object type has some kind of information in the raws.

Spoiler (click to show/hide)

[MATERIAL_TEMPLATE:STONE_TEMPLATE]
   These are the state names, adjectives and colors for the material.
   [STATE_COLOR:ALL_SOLID:GRAY]
   [STATE_NAME:ALL_SOLID:stone]
   [STATE_ADJ:ALL_SOLID:stone]
   [STATE_COLOR:LIQUID:ORANGE]
   [STATE_NAME:LIQUID:magma]
   [STATE_ADJ:LIQUID:magma]
   [STATE_COLOR:GAS:ORANGE]
   [STATE_NAME:GAS:boiling magma]
   [STATE_ADJ:GAS:boiling magma]
   [DISPLAY_COLOR:7:0:0]
   The modifier used to all values involving the material.
   [MATERIAL_VALUE:1]
   Temperature information.
   [SPEC_HEAT:800]
   [IGNITE_POINT:NONE]
   [MELTING_POINT:11500]
   [BOILING_POINT:14000]
   [HEATDAM_POINT:NONE]
   [COLDDAM_POINT:NONE]
   [MAT_FIXED_TEMP:NONE]
   Density information.  Not used for very much, but it comes up in inventory weight and fighting.
   [SOLID_DENSITY:2670]
   [LIQUID_DENSITY:3300]
   Not used.
   [MOLAR_MASS:36000]
   Used for blunt-force combat, measured in KPa.  Data scattered around the net (used compressive strength).  All very spotty.
   [IMPACT_YIELD:120000] used marble
   [IMPACT_FRACTURE:120000]
   [IMPACT_STRAIN_AT_YIELD:100]
   Not used.
   [COMPRESSIVE_YIELD:120000]
   [COMPRESSIVE_FRACTURE:120000]
   [COMPRESSIVE_STRAIN_AT_YIELD:100]
   [TENSILE_YIELD:15000]
   [TENSILE_FRACTURE:15000]
   [TENSILE_STRAIN_AT_YIELD:100]
   [TORSION_YIELD:15000]
   [TORSION_FRACTURE:15000]
   [TORSION_STRAIN_AT_YIELD:100]
   Used for cutting calculations in combat, measured in KPa.  Data scattered around the net (used tensile strength).  All very spotty.
   [SHEAR_YIELD:25000] used marble
   [SHEAR_FRACTURE:15000]
   [SHEAR_STRAIN_AT_YIELD:100]
   Not used.
   [BENDING_YIELD:15000]
   [BENDING_FRACTURE:15000]
   [BENDING_STRAIN_AT_YIELD:100]
   A unitless measure for how sharp the edge is for combat purposes.
   [MAX_EDGE:1000]
   Used for pressing oil into jugs -- anything greater than zero needs to be glazed first.
   [ABSORPTION:0]
   Determines what sorts of objects can be built with the item.
   [ITEMS_HARD]
   [ITEMS_QUERN]
   [REACTION_CLASS:CAN_GLAZE]

There is also Wood, Soil, and other things in the material definitions that, given consideration, would lead to certain types of materials being better to dig in and build constructions out of.

Also, a simple "cascade" of forces would seem to work well for making cave-ins realistic and at the same time allowing for things such as buttresses and really nice architecture.

All blocks, be they constructed or natural, could support a weight proportional to their COMPRESSIVE_YIELD (maybe another variable would be more appropriate, but bear with me, here).  When a square is disturbed by it's environment being changed (digging around near it) or something being placed on top of it (like another rock or a dwarf or a minecart), the weight of the square (plus whatever's on top of it) is calculated.  Then, the squares below it and adjacent to it are checked.  The weight is divided amongst the squares present, and transfered to them.

Now, if the amount of weight that it's calculated a specific tile EXCEEDS the COMPRESSIVE_YIELD for that square, it will fail, structurally.  If it's a constructed item, it will be spontaneously deconstructed.  If it's a natural stone wall, it will be converted into an empty square with a stone in it.  This will change the local environment, and and cause other squares to be recalculated as well.

In this system, it is very possible through good planning to have large, wide, open roofs that do not cave in... one must merely make them out of the right materials like Adamantine or Steel.  It is also just about IMpossible to dig out large soil or sand "caverns" without providing some kind of supports.  Entire fortresses would no longer be able to be balanced on a single soap block, since it would squish under the weight.

Which brings me to the Caverns.  It would be easy enough, during cavern generation, to find the weakest points most prone to cave-in and simply make a column of rock to support them.  This would actually mimic the real behavior of column formation in real life caverns.

[Jeoshua]

And yes, checking a crapton of tiles every time someone mines something WILL kill FPS faster than the HFS. Even if it only takes mybe a tenth of a second per tile, that's still several seconds of lag once you get deep enough. Several seconds of lag, per tile. That's a ton of lag if you've got multiple miners.

Depends on what you're checking.  As it is, a crapton of tiles are already being checked every time someone mines things, to see if they have support.  Ideally the difference would be negligible from what we experience now.  Checking a few variables, even moving a few variables around, is incredibly fast on modern hardware.  The only real bottleneck to speed right now is pathfinding, and that's because it's using a search algorithm that checks every valid path for the quickest one out of the lot.  A cave-in algorithm, done right, only has to search down and laterally.

Additionally, one doesn't even have to manipulate tiles that far away from the original tile one was checking.  A precariously placed walkway may fail, or it may hold on to it's position precariously until someone or something changes it's local environment.  This would not only help the calculation speed, but allow some pieces of dangerous terrain to exist, more or less lying in wait for unsuspecting passers by.

[NW_Kohaku]

Couldn't you work with asynchronous systems. Ie, the to be collapsed tiles are dropped into a queue and then checked while the games goes. This will use a more RAM, but allow the game to maintain a steady FPS. Besides, an unsecured roof doesn't always collapse immediatly, so maybe a chance based timer for every tile the game deems insecure. And once one tile fals it triggers all weak tiles near it.

You would need to have a seperate systems for floating blocks though, or it would get strange as a block hangs there for a month or two while the systems resolves all possible collapses.

Well, that's turning it into "Toady's First Multi-Thread support".  (Presuming Baughn did all the limited multi-threading on the display type stuff.)

Considering as pathfinding itself is extremely easy to split off into multiple threads (a dwarf trying to figure out the path from where they are to the nearest pig tail sock doesn't need to know the position of any of the other pathfinders), but is, to the best of my knowledge not multi-threaded, I doubt Toady will be pushed to start multi-threading for this when he hasn't done it for anything else. 

And no, the old method of cave-in didn't collapse immediately, and in fact, gave you warning that it was going to collapse a little while before it happened with a "rumbling" message.

Beyond that, it doesn't solve the problem that Toady wants to have that realistic system (which means that you can't put the weight of a mountain going through just one tile, even if it is in a single column straight above the tile in question) where we can show the information to the player in a meaningful way. 

Doing so would take one of those color-coded transparent overlays of information I've been arguing for for a while now, because we will need to display to the player in a reasonably simple manner (without looking at specific menus) the damage/stress levels of a wall.

Depends on what you're checking.  As it is, a crapton of tiles are already being checked every time someone mines things, to see if they have support.  Ideally the difference would be negligible from what we experience now.  Checking a few variables, even moving a few variables around, is incredibly fast on modern hardware.  The only real bottleneck to speed right now is pathfinding, and that's because it's using a search algorithm that checks every valid path for the quickest one out of the lot.  A cave-in algorithm, done right, only has to search down and laterally.

Additionally, one doesn't even have to manipulate tiles that far away from the original tile one was checking.  A precariously placed walkway may fail, or it may hold on to it's position precariously until someone or something changes it's local environment.  This would not only help the calculation speed, but allow some pieces of dangerous terrain to exist, more or less lying in wait for unsuspecting passers by.

That's not really true - math on data is blazingly fast, yes, but the reason pathfinding is such a problem is because of memory fetching - the game is randomly accessing tremendous numbers of items out of a giant array-of-an-array-of-an-array, which itself mostly consist of sets of references that have to be fetched into data, as well. 

A "cascade" support check would essentially require a similar sort of check to pathfinding, except that the "breadth" of a single given "pathfind" for support will be narrower and more focused.

[King Mir]

The worst bottleneck on FPS is exactly the metric that performance should be measured against. If it isn't on the same scale, it's not worth optimizing.

That's a slightly too-simplistic view. 

Every cause of lag will add up.  A hundred things that take a tenth of a second to calculate are just as much a problem as one thing that takes ten seconds to calculate.

Besides, if we're talking about what to optimize first, there's the matter of "low-hanging fruit" - rewriting container types in order to make the lag from huge item counts less noticeable may be much easier and clear up more lag than potentially marginal gains in incremental changes in pathfinding optimization.

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

And Toady's last stated reason for not reintroducing cave-ins is not performance, but the question of how to have a system that's easy enough to communicate to the player.

If that's the only problem, then Burmalay's idea, or one very much like it, is the obvious solution - a cut-and-dried "No more than X number of tiles of unsupported overhang, or cave-ins happen" formula wouldn't be much different from the old "No more than 6 tiles without a wall or support" formula of 2d. If you set that "X" to 3 tiles to reach a supporting tile below, you have basically the exact same mechanics as the old 2d.

Of course, you could still build a entire tower resting on a single bar of soap support in that sortThe game already checks  of mechanic, it would just require an upside-down pyramid type of shape for the bottom part of the tower.

I highly doubt that thought has not occurred to Toady, however.  The only reason I can think of that he wouldn't have gone ahead with that idea is that he does want a more complex system, one where walls can fail under having to support too much weight, even if there is a load-bearing wall, and the problem is that it's too difficult to set up that sort of system.

Well the real reason that Toady hasn't gone back to fix the cave in system is because he's doing cooler things like the caravan arc. Toady specifically rejected 3-tile-out-rules because "you can have a really twisty curvy structure like an abstract modern art statue that curls around itself and so on and that needs to be addressed because the player can create that shape" (DF talk 7). He also said, regarding cave-ins: "I'm not sure that's the type of problem that people need to be thinking about until we get a lot of other groundwork put in."

Here's the biggest issues I see: Toady wants a realistic system which is easy to communicate with the player, and a realistic system that doesn't kill FPS.

And yes, checking a crapton of tiles every time someone mines something WILL kill FPS faster than the HFS. Even if it only takes mybe a tenth of a second per tile, that's still several seconds of lag once you get deep enough. Several seconds of lag, per tile. That's a ton of lag if you've got multiple miners.

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.

[GreatWyrmGold]

The worst bottleneck on FPS is exactly the metric that performance should be measured against. If it isn't on the same scale, it's not worth optimizing.

That's a slightly too-simplistic view. 

Every cause of lag will add up.  A hundred things that take a tenth of a second to calculate are just as much a problem as one thing that takes ten seconds to calculate.

Besides, if we're talking about what to optimize first, there's the matter of "low-hanging fruit" - rewriting container types in order to make the lag from huge item counts less noticeable may be much easier and clear up more lag than potentially marginal gains in incremental changes in pathfinding optimization.

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

Why not? It's still computing.

Here's the biggest issues I see: Toady wants a realistic system which is easy to communicate with the player, and a realistic system that doesn't kill FPS.

And yes, checking a crapton of tiles every time someone mines something WILL kill FPS faster than the HFS. Even if it only takes mybe a tenth of a second per tile, that's still several seconds of lag once you get deep enough. Several seconds of lag, per tile. That's a ton of lag if you've got multiple miners.

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.

I made up a number. Even so, do the math. Each tile mined, assuming for a moment that it's the only non-solid tile in the world, has nine tiles above it that would need to be checked, 25 above those, 49 above those, 81 above those, 121 above those, etc. A mere 10 z-levels underground, you'd be checking hundreds of tiles. That's a significant portion of a second, every time a tile's mined. And that's assuming tiles below and to the sides of the ones mined aren't being checked. So...another half-second of lag, every time a miner mines a tile around the top of the first cavern layer and even more when deeper? Sounds significant.

[Jeoshua]

How much data would be checked on each one of those tiles, tho?  One, maybe two variables (weight and strength).  And that's it really.  No real heavy math needs to be done, no crosschecked lookups.  No recursive algorithms recalculating things over and over.

Just Addition and Comparison.

And that's exceedingly fast.

[King Mir]

I would say that any cave in system added would have to somehow take account of the material properties of the actual materials which are being worked on at the time.  As it stands, EVERY object type has some kind of information in the raws.

Spoiler (click to show/hide)

[MATERIAL_TEMPLATE:STONE_TEMPLATE]
   These are the state names, adjectives and colors for the material.
   [STATE_COLOR:ALL_SOLID:GRAY]
   [STATE_NAME:ALL_SOLID:stone]
   [STATE_ADJ:ALL_SOLID:stone]
   [STATE_COLOR:LIQUID:ORANGE]
   [STATE_NAME:LIQUID:magma]
   [STATE_ADJ:LIQUID:magma]
   [STATE_COLOR:GAS:ORANGE]
   [STATE_NAME:GAS:boiling magma]
   [STATE_ADJ:GAS:boiling magma]
   [DISPLAY_COLOR:7:0:0]
   The modifier used to all values involving the material.
   [MATERIAL_VALUE:1]
   Temperature information.
   [SPEC_HEAT:800]
   [IGNITE_POINT:NONE]
   [MELTING_POINT:11500]
   [BOILING_POINT:14000]
   [HEATDAM_POINT:NONE]
   [COLDDAM_POINT:NONE]
   [MAT_FIXED_TEMP:NONE]
   Density information.  Not used for very much, but it comes up in inventory weight and fighting.
   [SOLID_DENSITY:2670]
   [LIQUID_DENSITY:3300]
   Not used.
   [MOLAR_MASS:36000]
   Used for blunt-force combat, measured in KPa.  Data scattered around the net (used compressive strength).  All very spotty.
   [IMPACT_YIELD:120000] used marble
   [IMPACT_FRACTURE:120000]
   [IMPACT_STRAIN_AT_YIELD:100]
   Not used.
   [COMPRESSIVE_YIELD:120000]
   [COMPRESSIVE_FRACTURE:120000]
   [COMPRESSIVE_STRAIN_AT_YIELD:100]
   [TENSILE_YIELD:15000]
   [TENSILE_FRACTURE:15000]
   [TENSILE_STRAIN_AT_YIELD:100]
   [TORSION_YIELD:15000]
   [TORSION_FRACTURE:15000]
   [TORSION_STRAIN_AT_YIELD:100]
   Used for cutting calculations in combat, measured in KPa.  Data scattered around the net (used tensile strength).  All very spotty.
   [SHEAR_YIELD:25000] used marble
   [SHEAR_FRACTURE:15000]
   [SHEAR_STRAIN_AT_YIELD:100]
   Not used.
   [BENDING_YIELD:15000]
   [BENDING_FRACTURE:15000]
   [BENDING_STRAIN_AT_YIELD:100]
   A unitless measure for how sharp the edge is for combat purposes.
   [MAX_EDGE:1000]
   Used for pressing oil into jugs -- anything greater than zero needs to be glazed first.
   [ABSORPTION:0]
   Determines what sorts of objects can be built with the item.
   [ITEMS_HARD]
   [ITEMS_QUERN]
   [REACTION_CLASS:CAN_GLAZE]

There is also Wood, Soil, and other things in the material definitions that, given consideration, would lead to certain types of materials being better to dig in and build constructions out of.

Also, a simple "cascade" of forces would seem to work well for making cave-ins realistic and at the same time allowing for things such as buttresses and really nice architecture.

All blocks, be they constructed or natural, could support a weight proportional to their COMPRESSIVE_YIELD (maybe another variable would be more appropriate, but bear with me, here).  When a square is disturbed by it's environment being changed (digging around near it) or something being placed on top of it (like another rock or a dwarf or a minecart), the weight of the square (plus whatever's on top of it) is calculated.  Then, the squares below it and adjacent to it are checked.  The weight is divided amongst the squares present, and transfered to them.

Now, if the amount of weight that it's calculated a specific tile EXCEEDS the COMPRESSIVE_YIELD for that square, it will fail, structurally.  If it's a constructed item, it will be spontaneously deconstructed.  If it's a natural stone wall, it will be converted into an empty square with a stone in it.  This will change the local environment, and and cause other squares to be recalculated as well.

The problem with that is, what if you have a steal column, reinforced (surrounded) by mud? A naive calculation of the forces on the mud would destroy the mud, but leave the steal. But that's not what should happen.

[Jeoshua]

Okay but, in that example of a steel column surrounded by mud, why would the mud necessarilly be destroyed.  You do, after all, have a column of steel that will absorb quite a bit of the force.  And if you have a column of steel planted into a substrate of mud, realism says that isn't good enough and the column would sink in if there is enough weight bearing down upon it.

[King Mir]

The worst bottleneck on FPS is exactly the metric that performance should be measured against. If it isn't on the same scale, it's not worth optimizing.

That's a slightly too-simplistic view. 

Every cause of lag will add up.  A hundred things that take a tenth of a second to calculate are just as much a problem as one thing that takes ten seconds to calculate.

Besides, if we're talking about what to optimize first, there's the matter of "low-hanging fruit" - rewriting container types in order to make the lag from huge item counts less noticeable may be much easier and clear up more lag than potentially marginal gains in incremental changes in pathfinding optimization.

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

Why not? It's still computing.

Here's the biggest issues I see: Toady wants a realistic system which is easy to communicate with the player, and a realistic system that doesn't kill FPS.

And yes, checking a crapton of tiles every time someone mines something WILL kill FPS faster than the HFS. Even if it only takes mybe a tenth of a second per tile, that's still several seconds of lag once you get deep enough. Several seconds of lag, per tile. That's a ton of lag if you've got multiple miners.

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.

I made up a number. Even so, do the math. Each tile mined, assuming for a moment that it's the only non-solid tile in the world, has nine tiles above it that would need to be checked, 25 above those, 49 above those, 81 above those, 121 above those, etc. A mere 10 z-levels underground, you'd be checking hundreds of tiles. That's a significant portion of a second, every time a tile's mined. And that's assuming tiles below and to the sides of the ones mined aren't being checked. So...another half-second of lag, every time a miner mines a tile around the top of the first cavern layer and even more when deeper? Sounds significant.

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.

[King Mir]

Okay but, in that example of a steel column surrounded by mud, why would the mud necessarilly be destroyed.  You do, after all, have a column of steel that will absorb quite a bit of the force.  And if you have a column of steel planted into a substrate of mud, realism says that isn't good enough and the column would sink in if there is enough weight bearing down upon it.

If you model it correctly, then yes it would match real life. But I was pointing out an issue with the model you described. The steal may halve the force on an adjacent tile of mud, but that probably wouldn't be enough to make the mud able to handle the force on it. The steal won't collapse because it can handle all of the force, but the mud can't handle even a fraction.

[Jeoshua]

I see what you mean now.

Following the logic I had originally set forward a few more steps beyond the mud breaking down, the ceiling above the steel column would no longer be supported, or have anywhere for the force to go.  That leads to it being unsupported entirely, and the entire ceiling that column would have been supporting collapsing under it's own weight into rubble.

Moral of the model: Dig down into bedrock with your supports, or don't try building a cavern in mud.

[GreatWyrmGold]

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

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. Once I get into he later stages of a fort, my master or legendary miners can mine a tile or two a second. I'm probably down by the second or third cavern layer by then, so that's quite possibly over a thousand tiles checked per tile mined--I'd have to do the math, but it might not mean much meaningful due to the whole "caverns and fort in the way" thing. I have at least two or three miners by that point (let's go with two, the number I start with). So...let's say 3 tiles per IRL second, an even thousand tiles checked per tile mined, and 5 nanoseconds per tile checked. That's...15,000 nanoseconds per second. Hm, that's not much, is it? But wait! what about constructions? I usually build big buildings aboveground to tie up my idlers, and usually perform some other task as well, and that would add to the weight of tiles underneath. Hm, wouldn't mining also alter stuff for tiles underneath it?
Alright, so...from mining, if we check in all directions, it probably adds up to a 0.05% increase or so in time taken, and maybe that much from constructions. So, bot too bad...assuming that calculations do, in fact, take a mere 5 nanoseconds per tile. Somehow, that seems low.

Can anyone back up Mir's estimate?

[King Mir]

I used 5ns because that's a typical CAS latency, which is one of the important timings for memory that's specified by the RAM manufacturer. It's a ballpark figure.