Home Blog Index
Joseph Petitti —

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.

The Afterlight Caves game world
Although entities can roam freely, all terrain in the game is made up of uniformly-sized squares.

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.

Naive ray marching causes the ray to miss collisions with corners
The naive method can miss collisions with corners

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.

A diagram showins the intersections of a ray with a grid
The red points are the only ones we need to check

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.

Diagram showing where nx and ny are located

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; } } }