While I don't think this problem is trivial, I also don't think it's quite as difficult as some people make out. Part of the problem is that there are several tangled issues going on at once; separating them out should make things clearer. Of course, perhaps someone has already done this, but I didn't see anything in a brief search.
Here are the problems as I see them, in order of severity:
1) Dwarves cause floods by digging into water or magma. (don't object to this just yet!)
2) Dwarves injure themselves and others by causing cave-ins
3) Dwarves trap themselves by digging themselves "into a corner". (to coin a phrase)
4) Dwarves often walk much further in order to dig out a tile than is necessary.
5) Dwarves often dig out a room incompletely because of their somewhat random approach.
Obviously the first, most severe problem has already been fixed. It's the most severe because it's the hardest to undo when it happens, requiring you to wall off portions of your fort very quickly in order to prevent the flood from spreading. It's been solved by simply aborting the dig just before it causes an accident; the dwarves have been given just enough common sense that they won't dig into warm or wet ground unless given explicit orders. This is a great solution (although it causes some repetitive user interactions).
The second problem happens simply because dwarves can't tell when they're about to cause a cave-in. It can be solved in exactly the same manner as the former problem. Any time digging out a single tile would cause a collapse, the tile (and perhaps the ones that would collapse) are marked as unstable and the job is canceled. This is not quite the ideal solution, as there is often a way to execute the dig orders in such a way that no collapse need happen, but it will do for a start. I'll discuss the more complex solution in a moment.
At first glance, the third problem looks to be as easy to solve as the first two. A little thought, however, and you will be able to think of scenarios where it's not quite so easy for the dwarf to figure out. The problem lies in how you figure out if you are trapped. If you can't figure out if you're trapped, you can't figure out whether you will be trapped in the future (once you've completed the job you're about to start). A good start would be to defined 'trapped' as being unable to reach some other location. Perhaps you are trapped if you can't reach the mayor's office, or if you can't reach your bedroom, or if you can't reach food and water. Of the possibilities I've considered, I like using the mayor's office best, but none of them are really very satisfactory, because what if you want to dig a defensive position in the middle of your fort? It might cut you off from your bedroom but not the mayor's office, or from food but not from your bedroom; you might find that some dwarves decline the job while others don't. On the other hand, in many cases it might be a good enough test to prevent most dwarves from getting trapped, especially from getting trapped in obvious places, but you have a problem that merely reissuing the order the way you would for damp stone or for unstable areas doesn't help; it'll still trap your dwarf. We need to get slightly more complicated. First, if completing a job would prevent _any_ dwarf from pathing back to the mayor's office then it's canceled and the tile is marked (much the way damp tiles are marked) as a bottleneck or something (it's hard to come up with a good word for this). The dwarf doing the job should consider all the possible places he can stand while doing the work, and only cancel the job on his account if he would get trapped while standing in all of them. Basically, we've added two extra steps here. We have to consider the position of all the dwarves (and visitors, but probably not invaders or wildlife) and not just the one doing the work, but also we need to make multiple checks for the one doing the work, one for each available tile he could stand on. Clearly if completing the job would trap other dwarves then it would be canceled even if the dwarf doing the job could move to a safe spot first, and the job would not need to be canceled if doing it would not trap anyone if the dwarf doing the job had a safe spot to do the job from.
The fourth problem is easy, and I have seen several people propose the correctly solution, including here in this thread. Rather than consider the adjacent tiles in a fixed order and choosing the first one the dwarf can get to, instead path to all of them and choose the shortest path.
The last issue people mention is not very serious, and personally I think he did it that way specifically to make large numbers of miners more efficient by increasing the number of tiles that can be worked as much as to avoid a more complicated solution. In fact, I'm not really sure that it's a problem per se, although I do agree that it is often annoying to have rooms that are partially dug out, and dug out in the least useful way. Some orderliness would be nice.
So, what about that more complicated solution that I mentioned? While I haven't worked out all the details or anything, you can easily see that each digging job can be a node in a directed acyclic graph, where the edges represent dependencies. For example, consider a long, one-tile-wide hallway. Each tile to be dug depends on it's neighbor being dug, making a chain all the way back to the one tile that is the exposed workface simply because you can't get to the middle squares until you've dug out the ones in front of them. More complicated situations often have no unique graph, the dwarves can dig them out in any one of many possible orders with the same results. What's interesting is that if we consider cases where a dwarf might get trapped or cause a cave-in, we see that there are ways to execute the orders so that nothing bad happens and that in these cases there are far fewer possible ways to create the graph. There will still be cases were someone gets trapped or causes a collapse, but generally it'll be because that's what the user wanted.
You can also see that once you have this graph, actually executing it is not particularly hard (although allowing multiple dwarves to dig in the same area involves having multiple simultaneous traversals of the graph that don't conflict or visit the same nodes more than once.) Creating the graph is more complicated, but I think it could and should be done. In fact, if Toady were to go for this solution, it would fix problems 2 through 5 all at once. Since number 5 is partially desirable, some fudging can be done when the dwarves actually do the digging, so that they don't always dig things in exactly the same order.
So, what's the downside? Well, implementing this might be quite difficult. It all depends on how the existing code is set up, how he stores what jobs are yet to be done, etc. Not much we can say about that without having the source code though. Also, a lot of what I've proposed adds pathfinding checks, often a substantial number of them. That won't make the game any faster, certainly.
I think the upsides outweigh the downsides, because micromanaging this kind of thing is very tedious. The dwarves can already do many things that make them look quite bright, but their inability to dig simple trenches without killing themselves breaks the user's suspension of disbelief; digging is something dwarves are supposed to be good at, especially in this post-Tolkien era.
I welcome feedback. Have I missed anything? Not made something clear?
Author
Topic: Dwarf Digging Pattern (Read 3218 times)