Efficient 3D printer/builder -> 3D grid path finder

I'be noticed that most 3D printers using turtles do it on a zig-zag like movement, going through all blocks on the building area, instead of going only to to-be-placed block's location. Even something that tries to go only to blocks to-be-placed layer by layer, whatever their building direction is, would be rather inefficient for building 8 cubes in the vertexes of a cube.
I would like to improve this by:
-subdividing the to-be-printed schematic into connected (diagonals also) sets of blocks, ordered by inclusion. Eg., a cube inside a hollow ball would result into the cube and ball being separately saved to variables and the cube being recognized as being inside the ball.
-building the sets the more included first (eg., cube first) and using a 3D path finder program to move between sets that are already built and have the same level in respect to the said order relation ( eg., for a solid sphere and a hollow sphere with a cube in it, it would build the cube, build the hollow sphere, then find the path to the solid sphere and build it).

I have ideas for implementing all the above except the path finding. Instead of it, I could just break blocks and replace them as the turtle moved directly to the next set to-be-built, but pickaxes won't yield wood and ect., so I would rather not.

What do you think?Mission impossible or reasonable plan?

A better bet would be to build layer-by-layer, but skip empty layers. 3-D path finding is very difficult to do well when you have the ability to look ahead of your current position. Trying to pathfind blind sounds like a bad plan. You should look into existing pathfinding algorithms if pathfinding is of interest to you.

Lyqyd, on 10 October 2012 - 03:53 PM said:

A better bet would be to build layer-by-layer, but skip empty layers. 3-D path finding is very difficult to do well when you have the ability to look ahead of your current position. Trying to pathfind blind sounds like a bad plan. You should look into existing pathfinding algorithms if pathfinding is of interest to you.

I wrote the topic in a hurry, perhaps some parts were not clear; the idea is to have something like a MCedit schematic as an input, so it's not blind pathfinding. I did some research, and path finding seems to be done using an algorithm called A*, and it's not that complicated, there's even someone who implemented in Lua for turtles in 2D (it does say blind pathfinding, but it only does that when it gets stuck):
THIS VIDEO IS NOT MINE, it's from EllypticGeometry
[media]http://www.youtube.com/watch?v=GDBY4PlNVAo[/media]
I was just hoping someone might have it laying around?

How far is your lua skills? because as my like 2 moths of lua coding I have no idea how to do this. Might just be focused more on other stuff though

Actually, Ellyptic replied and I've decided A* (3D path finding algorythm) is not that complicated to implement, plus, instead of all the sets in the topic, I might use a travelling salesman approximated solution using space-filling curves, So I'll start coding, unless someone has a better idea?

Doyle3694, on 10 October 2012 - 08:45 PM said:

How far is your lua skills? because as my like 2 moths of lua coding I have no idea how to do this. Might just be focused more on other stuff though

It's not much about the Lua skills, it's more about the maths. That said, an update:

I've found a 2D path finder optimized with jump points written in pure Lua, which I've already tried out with success in ComputerCraft. However, it only uses the optimization in case diagonal moves are allowed. The one thing that stands between adapting the algorithm to straight moves + turning cost is transforming diagonal jumps into optimal straight movements, as I describe and ask in comment 20 here: http://harablog.wordpress.com/2011/09/07/jump-point-search/ , which I copy:

I am interested in applying jump points to minimize number of turns + path length in a straight moves only scenario. Other techniques I found to deal with this problem use, for instance, rectangular symmetry. The ‘only’ problem I haven’t dealt with is transforming diagonal jumps into a optimal (minimum number of turns + path length) sequence of straight moves.
What I’ve thought until now: for minimizing turns, we should use the Manhattan heuristic and add the number of turns needed to perform a jump to the g-factor. Also, maybe the Euclidean heuristic in the g-factor can be replaced with the Manhattan heuristic?
Besides that, the main problem is transforming a diagonal jump into a sequence of turn-wise optimal moves (that number then would add to the jump node g-score).
Eg, a simple case where we try to move from S to E:
(bear in mind that no other jump point was found in the diagonal search until we found E)
1 0 1 1 1 E
1 0 1 0 0 0
1 0 0 0 0 0
1 0 0 0 0 1
0 0 0 0 0 0
S 1 1 0 1 1
There is already several paths made available by the fact that it is a diagonal jump point (marked with 2′s):
1 0 1 1 1 E
1 0 1 2 2 2
1 0 2 2 2 0
1 2 2 2 0 1
2 2 2 0 0 0
S 1 1 1 1 1
Under these conditions, what is the best, turn-wise, straight moves only path ?(because the distance covered will be the same under the Manhattan metric) (having in account an initial orientation).
We can ignore holes in the map (filled with 3′s):
1 3 1 1 1 E
1 3 1 0 0 0
1 0 0 0 0 0
1 0 0 0 0 1
0 0 0 0 0 3
S 1 1 3 1 1
This case is simple, and a perfect solution with 3 turns + a possible start turn would be the following path (marked P):
1 3 1 1 1 E
1 3 1 0 0 P
1 P P P P P
1 P 0 0 0 1
P P 0 0 0 3
S 1 1 3 1 1
From there on, I haven’t thought much.