Ray marching in a grid-aligned world
In many games or other graphical applications, there is often a need to draw a ray from a point until it hits an object. This is the fundamental operation of ray tracing, an essential technique in computer graphics: drawing reflecting and refracting light rays from a light source to the camera. Unfortunately, this process is quite computationally expensive, which is why most real-time graphics programs only approximate it.
However, if you can simplify the world you can make ray tracing a lot easier, and it can be useful in many applications. In the game I'm working on, Afterlight Caves, I implemented a type of ray casting to draw laser beams on the game world.
For the purposes of this application, each beam has a starting point (the entity that fired it) and a direction, and should be drawn as a continuous line in that direction until it hits a piece of terrain. The nature of the terrain in Afterlight Caves is what enabled this more efficient ray casting algorithm.
Everything we need to check for collisions is aligned to a 60 by 60 pixel grid. This should make our job much easier, because we know we don't have to check every point on the ray, only points where a collision with the grid lines could occur. If we implement the algorithm in a smart way this can save us tons of computation time.
We're can skip over points that we know won't be collisions, so it's more like we're marching the ray in steps rather than tracing it out. Because of this we call the algorithm "ray marching."
The naive first attempt
My first implementation was a relatively simple algorithm that stepped in the given direction in increments of 60 (the standard block width) until it got a collisions, then backed up until it reached open space again.
/**
* Draws a ray from the given point in the given direction until it hits
* terrain, then returns the coordinates of the point it hit
* @param {Vector} startPos the starting position of the ray
* @param {Vector} dir the direction the ray is facing
* @return {Vector}
*/
export function nextIntersection(startPos, dir) {
dir = dir.norm();
let curPos = startPos;
let length = 0;
// make big steps until we hit a block
const dx = getBlockWidth();
let cellVec = getCell(curPos);
do {
length += dx;
curPos = startPos.add(dir.mult(length));
cellVec = getCell(curPos);
} while (!solidAt(cellVec.x, cellVec.y));
// make small steps until we're out of the block
do {
length -= 2;
curPos = startPos.add(dir.mult(length));
cellVec = getCell(curPos);
} while (solidAt(cellVec.x, cellVec.y));
return curPos;
}
At first glance this appears correct, and it works perfectly as long as you only shoot in a cardinal direction. The problem arises when you try to shoot diagonally.
By stepping in increments of 60, the algorithm can jump right over small corners. Even if you set the step size to one half (or one third or one fourth) of the block width there will still be some small corner size that the algorithm will miss.
Obviously we'll have to do some more math to solve this problem in the general case.
The smart method
The key observation here is that we only need to check for a block when the beam crosses a grid line. We need to find these intersections for an arbitrary line, and calculate whether they are on the boundary of a solid block in the right direction.
The line can go in any direction, so to get the "next" grid coordinate we need to remember whether we're moving in the negative, positive, or zero direction for both axes. We'll store these values in a vector to help us later:
const signVec = new Vector(Math.sign(dir.x), Math.sign(dir.y));
The next thing we need is the equation of the line in terms of both x and y. Doing some basic high school level geometry I got this:
const f = x => (dir.y / dir.x) * (x - startPos.x) + startPos.y;
const g = y => (dir.x / dir.y) * (y - startPos.y) + startPos.x;
where dir is the direction vector and startPos
is the starting position. Using these functions, f(x) will
give you the y value of the line at a particular x, and
g(y) will give you the x value at a particular y.
At each step, we move nextPos to the top-left corner of the
next grid space we want to investigate. Then we calculate the x value of
the line at that y, and the y value of the line at that x.
const nextPos = cellVec.mult(bw, bh);
const ny = dir.x === 0 ? nextPos.y : f(nextPos.x);
const nx = dir.y === 0 ? nextPos.x : g(nextPos.y);
The ternary if statements just guard against division by zero when the line is straight vertical or horizontal.
The diagram below shows the locations of nx and
ny at the first step.
In our example, because nx > nextPos.x we know that the
line intersects with the next cell at the vertical line x =
nextPos.x. If the line travels in the negative x direction we just
need to multiply both sides of the inequality by -1. Now we just need to
check if that cell is a solid piece of terrain with the
solidAt() helper function.
If that block is solid terrain, we've found the first collision point
along the ray, which is the answer we were looking for. If not, we move
nextPos over by one cell unit and continue the process.
Note that we check for a collision with the top and bottom of blocks the
same way, by testing whether ny > nextPos.y and testing
whether the next block up is solid.
Final algorithm
After several hours of covering edge cases, debugging, and testing here's the final algorithm. Maybe it could be a little more efficient or clean, but it correctly solves the problem in a reasonable amount of time, which is good enough for me.
/**
* Draws a ray from the given point in the given direction until it
* hits terrain, then returns the coordinates of the point it hit
* @param {Vector} startPos the starting position of the ray
* @param {Vector} dir the direction the ray is facing
* @return {Vector}
*/
export function nextIntersection(startPos, dir) {
// no direction
if (dir.isZeroVec()) return startPos;
const cellVec = getCell(startPos);
// see if we're starting in a block
if (solidAt(cellVec.x, cellVec.y)) return startPos;
dir = dir.norm();
const bw = getBlockWidth();
const bh = getBlockHeight();
const signVec = new Vector(Math.sign(dir.x), Math.sign(dir.y));
/** @param {number} x */
const f = x => (dir.y / dir.x) * (x - startPos.x) + startPos.y;
/** @param {number} y */
const g = y => (dir.x / dir.y) * (y - startPos.y) + startPos.x;
if (signVec.x > 0) cellVec.x++;
if (signVec.y > 0) cellVec.y++;
while (true) {
// go to the next block boundary
const nextPos = cellVec.mult(bw, bh);
const ny = dir.x === 0 ? nextPos.y : f(nextPos.x);
const nx = dir.y === 0 ? nextPos.x : g(nextPos.y);
if (
signVec.x === 0 ||
(signVec.y !== 0 && signVec.y * ny >= signVec.y * nextPos.y)
) {
// the next intersection with the game grid is vertical
const xInter = dir.x === 0 ? startPos.x : g(nextPos.y);
const intersection = new Vector(xInter, nextPos.y + signVec.y);
const blockToCheck = getCell(intersection);
if (solidAt(blockToCheck.x, blockToCheck.y)) {
return intersection;
}
cellVec.y += signVec.y;
}
if (
signVec.y === 0 ||
(signVec.x !== 0 && signVec.x * nx >= signVec.x * nextPos.x)
) {
// next intersection is horizontal
const yInter = dir.y === 0 ? startPos.y : f(nextPos.x);
const intersection = new Vector(nextPos.x + signVec.x, yInter);
const blockToCheck = getCell(intersection);
if (solidAt(blockToCheck.x, blockToCheck.y)) {
return intersection;
}
cellVec.x += signVec.x;
}
}
}