I am working on a video game. I need to determine each point along a ray with every x interval with the following information:
- X, Y, Z coordinates of the starting point of the ray, and,
- X, Y, Z coordinates representing the angle of the ray (the game is 3D, from what I can tell the game engine uses Euclidian vectors)
Of course rays are infinite in number, so I need something like "get next point." My idea is to have the computer get the first point, check it, and if that is not successful, get the next point and check it and so on until a specific point fits what I need. Of course, there some be some arbitrary upper limit to prevent the program crashing due to continually checking many rays.
In my game (it's a Minecraft clone for learning purpuses for anyone who knows about that) there is a 3d grid, each cell in the game is filled completly with some material, ie grass or air. I need to determine the first non-air block in the direction the player is looking. The player can be looking in any direction and is not bound to the grid in any way other than their location being represented by a floating point x, y, and z coordinate on the grid.
NOTE: My game engine does not have a built-in feature to do this.
Best Answer
From your question, you want to find every cube that a ray passes through, and enumerate them.
The direction he's looking in will be signified by $(d_x,d_y,d_z)\newcommand{\sgn}{\operatorname{sgn}}$, note that I assume that the direction is a vector starting at the center of the coordinate system, and not from the player.
We can simply enumerate coordinates on the ray with some interval, and discard duplicates, we just have to make sure that the interval is small enough such that we miss no blocks.
If we want this interval to be small enough such that it always ends up in the current or an adjacent block, we want $e$ to be the minumum distance to one of the lines in the grid between the boxes. (If the point is on a line, we discard that one) So let $e$ be that distance then we simply need to normalize the vector to have that size.
Finding $e$ is tricky, we need to find the distance from the point to many lines in a grid. For the following I assume that $q$ is the side length between the boxes, and that $x,y,z$ is the coordinate of the point.
We will perform an algorithm 3 times, one for each dimension. Each time we perform it, we are given a number, totaling at $3$ numbers. $e$ is the smallest of those $3$ numbers. The first time we will have $h=x,p=y$, the second time $h=x,p=z$ and the third time will have $h=y,p=z$.
The algorithm is as follows:
Let $s=\dfrac1e\sqrt{(d_x)^2+(d_y)^2+(d_z)^2}$, and define:
$$ \begin{align} \delta_x&=\frac{d_x}s\\ \delta_y&=\frac{d_y}s\\ \delta_z&=\frac{d_z}s \end{align} $$
Now simply given a point, calculate the next point with the given formula: $$ \begin{align} \text{next $x$}&=x+\delta_x\\ \text{next $y$}&=y+\delta_y\\ \text{next $z$}&=z+\delta_z \end{align} $$ Where $x,y,z$ are the coordinates of the previous point. Each of these points will be inside a box on the ray, and you wont miss any because we normalized the direction. Note that we might get the same box several times in a row, so if that's a problem you have to check for duplicates. The starting point is of course the players position.