# Maximum number of cubes within a radius

Last night I was mining obsidian in Minecraft, which takes a long time (15 seconds for each block). As a result, I would hold down the left mouse button with my left hand while I did something else. In order to maximize the usefulness of this tactic, I would orient myself in such a way as to mine as many blocks as possible without moving. This lead me to wonder...

Excluding the cube the rod starts in, how can I determine the number of
unit cubes that a rod of length $k$ can go through?


For example, the following picture shows a rod of length $4$ going through $4$ cubes (although a fifth could easily be added).

-
Stop playing minecraft or get cheats to mine faster... lol. =) –  Patrick Da Silva Aug 8 '11 at 7:02
@Patrick: He he he he... :P –  El'endia Starman Aug 8 '11 at 7:03
Relying on the picture, do you need to go entirely through the cube, or if the tip of the rod touches a cube without going through it that is fine too? –  Patrick Da Silva Aug 8 '11 at 7:26
@Patrick: I'd say the tip. After all, you don't need to be able to mine a cube on the other side to mine the cube itself. –  El'endia Starman Aug 8 '11 at 7:39
I added an answer that was inspired by the Bresenham algorithm for rasterization of lines on a digital display. However, his algorithm cannot be used directly, because it would mark for each x (the longer dimension) exactly one cell in the shorter direction (y). In the figure below, C3 would be marked but not C4, because the center of C3 is closer to the line than the center of C4. –  Jiri Aug 9 '11 at 16:08

Let us first consider the two dimensional case to explain the concepts. A line segment of the length $L$ (I will call it line $L$) is to be laid down on a unit square grid such that the number of the intersected grid cells is maximized. The cell coordinates are given by their left bottom corners.

The figure shows a line of length 4.8 starting in the cell $(0, 0)$ and ending in the cell $(4, 3)$. The angle $\alpha$ between this line and the x-axis is $45^{\circ}$. We can assume without loss of generality that the line always starts in the cell $(0, 0)$ and goes upwards and right such that $0 \le \alpha \le 45^{\circ}$ and it ends in a cell $(X, Y)$. When we move a point $P$ along the line we encounter the crossing points with the cells. A cell can be entered only at its left side (such as $C_1$) or at its bottom side (such as $C_2$). If a cell is entered at its left side, the $x$ grid coordinate of $P$ is increased by $1$ and the $y$ grid coordinate is unchanged. If a cell is entered at its bottom side, the $y$ grid coordinate of $P$ is increased by $1$ and the $x$ grid coordinate is unchanged. So, at each entering point into a cell exactly one grid coordinate of $P$ is increased by $1$. Since the point $P$ starts in $(0, 0)$ and ends in $(X, Y)$, there are exactly $X + Y$ different entering points, so there are exactly $X + Y$ crossed cells (not counting the starting cell). In the figure we have $4 + 3 = 7$ crossed cells. Since $X + Y \approx L \cos \alpha + L \sin\alpha$, the maximal number of crossed cell will be achieved with $\alpha = 45^{\circ}$.

There is one degenerate case when the line enters a cell through its bottom left corner. Then both grid coordinates are increased but only one new cell is crossed. Since we would get less crossed cells in this case we avoid this case by displacing the line slightly. This is always possible because the start and end points are real numbers and there are at most finite number of considered cells.

It remains to find $(X, Y)$. First we place the starting point at the coordinate origin and let the line pass through the opposite cell corners (parallel to cell diagonals):

If $L = n \sqrt 2$ ($n$ is an integer) then the line ends at a cell corner $(n, n)$. Now, it can be displaced such that it does not pass through the corners and ends in the cell $(n, n)$. The maximal number of intersected cells (not counting the starting cell) is $n + n = 2n$, where $n = \lfloor L / \sqrt 2 \rfloor$.

If $L = n \sqrt 2 + r, 0 < r < \sqrt 2$, then the line ends on the diagonal of the cell $(n, n)$. Moving the line along $45^{\circ}$ until the next cell is reached and displacing it, we obtain the end cell $(n+1, n+1)$. The maximal number of intersected cells is $n+1 + n+1 = 2n + 2$.

The three dimensional case is analogous. The cells are now unit cubes, the line segment is the rod. When moving along the rod we enter the cubes through one of three possible faces and the corresponding coordinate is increased. E.g. entering a cube through its bottom face increases the z-coordinate by $1$. Maximal number of intersected cubes is achieved when the rod is put through the opposite corners of the cubes (along longest diagonals) and then slightly displaced to pass through the faces. The maximum is X + Y + Z, where (X, Y, Z) is the last cube (not counting the first cube).

If $L = n \sqrt 3$ then the rod ends at the cube corner $(n, n, n)$. It can be displaced such that it ends in the cube $(n, n, n)$. The maximal number of intersected cubes is $n + n + n = 3n$.

If $L = n \sqrt 3 + r, 0 < r < \sqrt 3$, then the rod ends at the diagonal of the cube $(n, n, n)$. It can be displaced such that it ends in the cube $(n+1, n+1, n+1)$. The maximal number of intersected cubes is now $n+1 + n+1 + n+1 = 3n + 3$.

Let us summarize:

$$L = \mbox{length of the rod}$$ $$n = \lfloor L / \sqrt 3 \rfloor$$ $$r = L - n \sqrt 3$$

$$max = \begin{cases} 3n & \mbox{if} \;\; r = 0 \\ 3n + 3 & \mbox{if} \;\; r > 0 \;\; \end{cases}$$

-