Print

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

[Burmalay]

This is the image of how it can works.

Calculation of "cave-in" starts from lower to higher z-levels.
It compares each 2 z-levels from down to top.

At the image:
green - just forget about them =)
gray - blocks which are allowed to stay at its placed (not to cave-in)
red - the calculation point of cave-in
yellow - falling tiles (cave-in)

For example: each third-end tile from upper level will fall if it hasn't a support on the lower level. So -

The blue tile will fall (cave-in)

The thing is: this system will automatically form pregenerated territory to prepare it to play & will remove cave-ins at start of the embark.
& will check every new changed tile to calculate cave-in.

Something like this. Will it cause lags? =/
I'm trying to understand what to do next but it's really hard for me =)

I'm thinking about: how to imagine (because I'm not a programmer, so...) an algorithm which will perform local calculation of cave-ins to make it not so laggy. To not to force all-tiles-calculation when state of one tile has been changed. & not to make it buggy with flying objects in global...

[Burmalay]

We can simplify calculation with checkers sequence of tiles (just skip some of them until -). And when some tile does meet the "cave-in" condition it additionally calculate related tiles.

[King Mir]

That works is someone is building trees out of stone, but doesn't answer how to handle any other structure.

Most of the time, players aren't carving trees, but rooms.

[Burmalay]

The same way. You just need to build supports or dome-shaped structures. Like people did it IRL.

[NW_Kohaku]

The problems with any realistic cave-in mechanic is that it requires modeling the stresses of all the z-levels above any random point in a fortress on a per-wall basis become immensely difficult to calculate. 

If you want to do this realistically, every time you mine out a wall at a portion of the fort near the magma sea, you will have to calculate whether or not all the tiles for a hundred z-levels above will have support after that tile has been removed by doing a "cascade" model of checking if every individual tile of wall is not being overloaded by stress. 

This is the sort of thing that would be very difficult to do in real-time.

[King Mir]

The problems with any realistic cave-in mechanic is that it requires modeling the stresses of all the z-levels above any random point in a fortress on a per-wall basis become immensely difficult to calculate. 

If you want to do this realistically, every time you mine out a wall at a portion of the fort near the magma sea, you will have to calculate whether or not all the tiles for a hundred z-levels above will have support after that tile has been removed by doing a "cascade" model of checking if every individual tile of wall is not being overloaded by stress. 

This is the sort of thing that would be very difficult to do in real-time.

But it's not done in real time, it's done only during mining or construction. That's a lot less often than path finding.

[NW_Kohaku]

But it's not done in real time, it's done only during mining or construction. That's a lot less often than path finding.

Yes, but pathfinding is already a pretty major blow to FPS.  "Not as bad as the worst thing slowing down FPS" isn't quite a ringing endorsement. 


Anyway, to try to explain this a little better...

Consider those cathedrals with flying buttresses - they need to have this giant fancy buttresses because a stone wall will collapse if it is built higher than two or three stories high without them.  Even then, they only get up around 10 or so stories high. (Not counting thin spires that tapir upward.) 

If you think of this in terms of z-levels, the top z-level of wall doesn't carry any weight.  The next-to-top level of wall carries the weight of the wall above it.  The next z-level down piece of wall down carries the weight of two z-levels of walls.  Because it has to carry twice as much weight, you'll need to make it twice as thick to support that weight.  The next z-level down carries 3 z-levels of wall on it, and that third z-level is twice as thick, so you're carrying 4 times as much weight.  You'll need to make it four times as thick.  The next z-level down carries 3 z-levels with 7 times as much weight on it.  You need to make it 7 times as thick to carry that weight.  etc. etc. etc.

The reason that the great pyramids are shaped like big mounds is because stone is very heavy and can be crushed easily without making stone masonry construction shaped like a pyramid, where it gets thicker as it goes down to bear the weight of the walls above. 

[Burmalay]

But how does it works now? If you will dig out a cube it will fall down, so now we have a "non flying objects" algorithm. I think it may works like: When tile are excavated the algorithm checks connected "air" tiles (It draw a map by marking air tiles to understand is there a hole in it (soil tiles)) & if it can build a sphere of air tiles the algorithm creates a cave-in.
Some kind of such algorithm we have now. & we can have something like I suggest, to make building more real. Its not so difficult for CPU. We don't need to calculate stress or something really REAL. Just check connected tiles & how far they are without a support.

ADDED: This algorithm can check tiles in some area around the modified tile to reduce lags. It don't need to check whole map. Only before the embark.

[NW_Kohaku]

The question is, why would only the blue tile (or yellow tiles) fall?  Wouldn't the ceiling collapsing come about due to structural failures elsewhere in the ceiling?  Wouldn't most of the ceiling come down with it, not just that one specific tile? 

Also, I don't understand the significance of there being two z-levels of height in your diagram.  Would this not happen if the opening were only 1 z-level tall? 

And for the record, 2d DF did have cave-ins based upon carving out chambers too wide.  It was caused whenever any tile was not connected by three tiles (instead of 2) to the nearest wall.  See this Wiki page.

Toady has put off reintroducing proper cave-ins in the game until he can come up with a way of doing so without killing most computers.  (Which means not until he optimizes much of the rest of the code, which means not for a very, very long time...)

Current cave-ins work based off whether tiles can find connection to other non-diagonal tiles that, in turn, need to find a path to tiles that always are considered supported, like semi-molten rock.

For a simple method, an "empty pyramid" system like you are proposing is closest to what Toady used to have, but isn't going to implement, because he wants a "proper" system, and he generally refuses to do things in half-measures.

[Burmalay]

The question is, why would only the blue tile (or yellow tiles) fall?  Wouldn't the ceiling collapsing come about due to structural failures elsewhere in the ceiling?  Wouldn't most of the ceiling come down with it, not just that one specific tile? 

The blue & yellow tiles are falls because they are third tiles with no support from below. (I suggest this: "every third tile without support will fall" just for example). & when this tile falls it cause a sequence of falling tiles if they are haven't supports too. So if you build something & remove some of tiles from your construction it may collapse almost all. It will not drop everything at once. It has drop every tile consequentially because of its local calculation of cave-in.

Also, I don't understand the significance of there being two z-levels of height in your diagram.  Would this not happen if the opening were only 1 z-level tall? 

Don't worry about this. It's about supports & tiles which are not connected. Some kind of example of "how this algorithm can works" (cave-in rules). I suggest a way to do it in my previous post by "ADDED: This algorithm can check tiles in some area around the modified tile to reduce lags. It don't need to check whole map. Only before the embark."

[NW_Kohaku]

Also, I don't understand the significance of there being two z-levels of height in your diagram.  Would this not happen if the opening were only 1 z-level tall? 

Don't worry about this. It's about supports & tiles which are not connected. Some kind of example of "how this algorithm can works" (cave-in rules). I suggest a way to do it in my previous post by "ADDED: This algorithm can check tiles in some area around the modified tile to reduce lags. It don't need to check whole map. Only before the embark."

The game probably shouldn't need to check before embark - no natural formations should be triggering cave-ins the instant you walk onto an embark, anyway. 

The question is, why would only the blue tile (or yellow tiles) fall?  Wouldn't the ceiling collapsing come about due to structural failures elsewhere in the ceiling?  Wouldn't most of the ceiling come down with it, not just that one specific tile? 

The blue & yellow tiles are falls because they are third tiles with no support from below. (I suggest this: "every third tile without support will fall" just for example). & when this tile falls it cause a sequence of falling tiles if they are haven't supports too. So if you build something & remove some of tiles from your construction it may collapse almost all. It will not drop everything at once. It has drop every tile consequentially because of its local calculation of cave-in.

That's not my point - those blocks are supposedly solidly connected. 

In this image:


If the blue tile is considered unsupported, and will collapse, why will only the blue tile collapse?  If that tile is part of a continuous stone slab, and parts of the cave/ceiling are falling in, why would only one block fall down, why wouldn't the whole ceiling collapse from the structural damage the cave-in would have caused? 

You don't see buildings in real life where only square tiles of the ceiling fall in while everything else remains perfectly fine, when structural failure happens, it knocks over half of a building at a time.

[Burmalay]

I just noticed it will not work because of this -

This algorithm will collapse everything which are hasn't a support so finally we would have only upward constructions which are not so cool =)

[King Mir]

But it's not done in real time, it's done only during mining or construction. That's a lot less often than path finding.

Yes, but pathfinding is already a pretty major blow to FPS.  "Not as bad as the worst thing slowing down FPS" isn't quite a ringing endorsement. 

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.


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.

Flying buttresses are cool, but beyond what I expect from DF. You can make castles with thick walls, and several floors fairly well. Or buildings like the Colosseum.

I just noticed it will not work because of this -

This algorithm will collapse everything which are hasn't a support so finally we would have only upward constructions which are not so cool =)

Yep we want to be able to build overhands, balconies, and crazy crazy-horse like shapes in a realistic manner. Also, caverns can have wide ceilings, and you want them not to fall down either.

[NW_Kohaku]

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.

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

[GreatWyrmGold]

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.