Are there any recursive digger programs?

I'm looking for a turtle program that digs everything it touches, and everything that touches those blocks, and so on. Effectively, digging everything connected to a block. (Think floodfill, replacing blocks with air.) (Mainly for cleaning up skyblock structures).

I was thinking about writing a program to do this, but figured someone else has to have done this already. However, I checked the program subforum and couldn't find one. So… is there one already? Or is there a program that already does this sort of recursive search? I figured that some programs may use this sort of thing for ore vein digging or treecutting, but most treecutters seem to be hardcoded, and most digging programs are quarry-style.

And if there isn't, does anyone have any suggestions as to how to write a program that does so relatively efficiently? The niave method (keeping a stack of blocks to check and always checking the last block in the stack) ends up being relatively slow and moves a lot unnecessarily, as it'll end up generally digging one block / move. Looping through all blocks to detect to determine the position/orientation that ends up with the most blocks checked / move ends up with way too much computation, and is complex besides. Doing a brute-force computation of possible moves is even slower.

Also, is this the right subforum for this sort of question? And is there a thread somewhere with a sorted list of programs? The programs subforum is for released programs, not questions. And this forum seems to be mainly about coding questions, not suggestions of programs.

Although I've never been able to find any (properly documented) rules on the subject, program requests are generally placed in General, whereas Ask A Pro is exclusively for code-related questions.

You may find these links useful:

http://www.computercraft.info/forums2/index.php?/topic/21809-looking-for-a-mining-program/
http://www.computercraft.info/forums2/index.php?/forum/21-turtle-programs/
http://www.computercraft.info/forums2/index.php?/topic/19777-kings-branch-mining-script/

The recent-ish addition of turtle.inspect() to ComputerCraft adds possibilities to harvesting scripts that a lot of older code doesn't take advantage of.

Regarding tree-choppers, this sort of "exhaustive mining" thing really isn't the way to go. I've made a self-sustaining chopper that can gather more saplings than it needs simply by digging up the trunk and spinning through all four facings as it goes; by placing oaks in close proximity according to a tessellated pattern, this still allows it to gather nearly every log.

Bomb Bloke, on 26 February 2015 - 01:26 PM said:

Although I've never been able to find any (properly documented) rules on the subject, program requests are generally placed in General, whereas Ask A Pro is exclusively for code-related questions.

Alright. How could I get this thread moved? And how could I request a rules clarification regarding where to post things like this, so others don't have to go through this as well?

Bomb Bloke, on 26 February 2015 - 01:26 PM said:

http://www.computerc...mining-program/

This may be helpful. Thanks.

Bomb Bloke, on 26 February 2015 - 01:26 PM said:

The recent-ish addition of turtle.inspect() to ComputerCraft adds possibilities to harvesting scripts that a lot of older code doesn't take advantage of.

I've noticed this.

Bomb Bloke, on 26 February 2015 - 01:26 PM said:

Regarding tree-choppers, this sort of "exhaustive mining" thing really isn't the way to go.

I am aware of this. I was just looking through treechopper code to see if anyone had implemented it that way, as it might provide a good starting point as something that could be easily adapted.

Also, could you post / have you posted that treechopping script?

This doesn't appear to be a "code this thing now!" post, and will instead have useful/interesting conversation, so it is fine here, despite not being Ask a Pro's usual fare.

If I were to design a program like this, I would likely create a three-dimensional table of mined blocks, using x/y/z coordinates as the indices. This way, the program could avoid traversing blocks unnecessarily as much as possible. I would also likely use a second x/y/z table to represent "blocks of interest", which would be blocks connected to a mined block that were not subsequently explored for connected blocks. I would probably use a trio of mining functions to replace (and internally use) the turtle mining functions such that they would take into account the turtle's location and direction to automatically mark mined blocks and (un)mark blocks of interest.

Each time the turtle mined a block connected to a block it had previously mined, it would spin around and check all adjacent blocks, including the top and bottom block. I might use a table of functions to change which blocks it looks at depending on whether it arrived at its current position via the top, bottom, or side of the block, but that would only save a bit of time, not fuel, and may not be worth the effort.

After an initial pass through the structure to be demolished, I would likely have it create a flat table of the blocks of interest using the vector type (though it may be easier to create and maintain this table as entries are added, likely will be). I would then loop through the table to find the shortest distance to a block of interest. I'd then have the turtle move to that space and follow any adjacent blocks through and repeat the closest-block-of-interest procedure.

Lyqyd, on 26 February 2015 - 07:59 PM said:

This doesn't appear to be a "code this thing now!" post, and will instead have useful/interesting conversation, so it is fine here, despite not being Ask a Pro's usual fare.

Good to know, thanks.

Lyqyd, on 26 February 2015 - 07:59 PM said:

If I were to design a program like this […]

Yeah, that's basically what I'm thinking of. I just worry it could become too slow in the cleanup phase (O(n^2) distance calculations required overall). I'll see what I can come up with.

Yeah, that would be the worst case. There is always the possibility that the first pass would cut off large contiguous chunks of blocks, so you'd have a huge number of blocks of interest the first time, then get rid of a bunch of them (hopefully, entirely depending on how well the algorithm makes decisions on which direction to pursue each time) by mining that chunk, and have fewer to calculate against the next time.

Another concern is how it travels to the next block of interest. If you constrict it to passing through blocks it had mined, it is guaranteed not to damage any structures that fall within the boundary limits of the one being destroyed, but you also must implement a pathfinding algorithm.

The Lone Wolfling, on 26 February 2015 - 03:56 PM said:

Also, could you post / have you posted that treechopping script?

The code is here, but don't expect to make all that much sense of it. The turtle's planting patterns are dictated by the layout of dirt blocks in its work area, not by its code. It also relies on certain machines being present in certain places in order to work, plus a networked server to determine whether it's worthwhile collecting more resources at all. I suppose a couple of screenshots would speak volumes on the matter…

The "node" file it runs simply defines a global table that contains sets of x/y/z co-ords (where the power generator is, where the furnace is, where to dump stuff, where to start chopping…). This makes it relatively easy for me to set these turtles up in bulk. Not that I need that many; one pulls in roughly a thousand logs every few hours, alongside hundreds of units of charcoal.

You may or may not also be interested in this script, written for this. It uses a "somewhat" refined version of the chopper's pathfinding code. Doesn't do any actual digging, it's a simple explorer.

Though if I were to tweak it further, I'd probably aim to remove the recursion completely, as that only limits the potential distance it can move by linking its capabilities to the maximum length of the function stack (256 calls, by the way). I was also mulling over how to reduce the size of the node database - recording every block is all well and good, but would lead to a huge amount of RAM usage. For a digger, for eg, it'd probably be better to track what's in a chunk until you leave that chunk, then discard the recording and just store a single "chunk mined" flag instead.