[bljdmymf] Shortest paths for higher dimensional chess pieces

Given a higher dimensional rook or bishop as previously described, compute a path which reaches a given destination in the smallest number of moves.

In 2D on an empty board, a rook or bishop takes at most 2 moves to reach any given (accessible) square, and it is not difficult to describe the positions in which they require only 1.

In N dimensions, I suspect at most N moves are necessary (which is a lot).  When can we get there in less, and how?

The movement of both pieces can be described as a integer scalar multiple of a vector whose components are all -1, 0, or 1.  For a bishop, the number of nonzero components is even; for a rook, odd.  Without loss of generality, assume the piece is at the origin.  Find moves which sum to the coordinates of the destination.  This seems reminiscent of bin-packing.

One heuristic is, for all possible moves from the current location, choose the one that minimizes the straight-line (Euclidean) distance to the destination: the distance from a point to a line.  Repeat for the next move.

Other open problems: computational complexity; the tricky knight; what if there are obstacles?