Original Post
Hey, I'm having some trouble implementing a ray tracing algorithm... I thought I'd ask for some help before sinking more hours into this. In a nutshell, the algorithm misses the target sometimes; it seems to occur when the target is positioned between two cells in the grid. I feel like this must be a problem with how my delta values are calculated, or with how I calculate the distance to the next cell. Here's the code:
/* Get a list of contacts between the target and subject. */
public Long[] ray(Body subject, Body target) {
/* Create the ray to check for intersection. */
Ray ray = new Ray(subject, target);
/* Get the direction vector for the ray. */
Vector2f direction = ray.getDirection();
/* Get the ray's starting coordinates in the grid. */
int startX = (int) Math.floor(subject.getCenterX() / cellWidth);
int startY = (int) Math.floor(subject.getCenterY() / cellHeight);
/* Distance in the x, y direction of the vector for a single step. */
float deltaX = (float) Math.sqrt(1 +
(direction.y * direction.y) / (direction.x * direction.x));
float deltaY = (float) Math.sqrt(1 +
(direction.x * direction.x) / (direction.y * direction.y));
/* The current cell to examine. */
int currentX = startX;
int currentY = startY;
/* The target's cell. */
int targetX = (int) Math.floor(target.getCenterX() / cellWidth);
int targetY = (int) Math.floor(target.getCenterY() / cellHeight);
/* Length of the ray from current position to next x, y-side of a cell. */
float sideDistX, sideDistY;
/* 1 or -1 depending on the ray's direction. */
int stepX, stepY;
/* Initialize the step and distance. */
if (direction.x < 0) {
stepX = -1;
sideDistX = (startX - currentX) * deltaX;
} else {
stepX = 1;
sideDistX = (currentX + 1 - startX) * deltaX;
}
if (direction.y < 0) {
stepY = -1;
sideDistY = (startY - currentY) * deltaY;
} else {
stepY = 1;
sideDistY = (currentY + 1 - startY) * deltaY;
}
/* Advance one step. */
if (sideDistX < sideDistY) {
sideDistX += deltaX;
currentX += stepX;
} else {
sideDistY += deltaY;
currentY += stepY;
}
LinkedList<Long> contacts = new LinkedList<Long>();
while (!(currentX == targetX && currentY == targetY)) {
contacts.addAll(cells[currentX][currentY].getContactsWith(ray));
if (sideDistX < sideDistY) {
sideDistX += deltaX;
currentX += stepX;
} else {
sideDistY += deltaY;
currentY += stepY;
}
}
return contacts.toArray(new Long[0]);
}