At the end of generating a procedural map for the Derelict Facility engine, I had a sprawling interconnected maze of rooms and corridors. But there was a devastating problem: I could see everything.

The entire map was rendered at once. It looked like a top-down blueprint, not a dark, atmospheric facility. I needed to implement Fog of War. I needed to treat the player character like a lighthouse in the dark.

The Engineering Problem: The Grid vs. The Real World

In the real world, light travels in perfectly straight lines. If you look at a wall, photons travel from the wall to your eye.

In a game engine, you don’t have a “real world”. You have a 2D grid of memory ([]Tile). If the player is at X: 10, Y: 10 and a wall is at X: 15, Y: 12, how do you mathematically determine if the player can see the wall?

You need to draw a line between them. But grids don’t allow smooth lines. They only allow stepping from one integer coordinate to the next. You can’t stand at X: 10.5.

The Naive Approach: Floating Point Math

The modern instinct for drawing a line from point A to point B is trigonometric. You calculate the angle (math.Atan2), find the sine and cosine, and step along the floating-point line, rounding to the nearest integer grid tile at each step.

This works, but it is deeply flawed for systems engineering:

1. It is slow. Transcendental functions (sin, cos) are expensive CPU operations.
2. It is imprecise. Floating-point rounding errors create “holes” where a ray might accidentally skip a wall tile.
3. It is overkill. You don’t need a floating-point unit to navigate a 2D integer grid.

Bresenham’s Line Algorithm (1962)

In 1962, Jack Bresenham at IBM solved this problem for hardware plotters and early CRT displays. His algorithm determines which pixels to illuminate to form a straight line using only integer addition, subtraction, and bit-shifting. No division. No floating point.

It was designed for hardware that literally lacked decimal math processors, and it remains the industry standard today.

Here is the exact implementation used in the Derelict Facility engine to chart the path of a photon across the map grid:

func getLine(x0, y0, x1, y1 int) []entity.Point {
var points []entity.Point

    // dx is the absolute horizontal distance
    dx := math.Abs(x1 - x0)

    // dy is the absolute vertical distance. We make it negative as a
    // math trick so we can ADD it to our error tracker later.
    dy := -math.Abs(y1 - y0)

    // Step direction: are we going left or right? Up or down?
    sx := -1
    if x0 < x1 { sx = 1 }

    sy := -1
    if y0 < y1 { sy = 1 }

    // The Error Tracker: how far we've drifted from the true mathematical line
    err := dx + dy

    for {
        points = append(points, entity.Point{X: x0, Y: y0})

        if x0 == x1 && y0 == y1 {
            break // Destination reached
        }

        // Double the error for comparison.
        // This prevents us from ever needing fractions (like 0.5).
        e2 := 2 * err

        // Adjust X if our drift tolerance allows it
        if e2 >= dy {
            err += dy
            x0 += sx
        }

        // Adjust Y if our drift tolerance allows it
        if e2 <= dx {
            err += dx
            y0 += sy
        }
    }

    return points

}

How the Error Tracker Works

The genius of Bresenham is the err accumulator. It tracks how far our jagged, step-by-step integer path has drifted from the mathematically perfect straight line.

When the drift exceeds a specific threshold, the algorithm corrects itself by stepping diagonally. By using e2 := 2 * err, we eliminate the need to compare against 0.5, allowing the entire calculation to remain strictly within integer bounds.

Perimeter Raycasting

To implement the “Lighthouse”, we define a vision radius (e.g., 8 tiles). We want to illuminate everything within that radius, unless a wall blocks the light.

The obvious instinct is to just cast 360 rays in a circle based on angles (using sine/cosine). However, as these rays get further away from the player, the physical gap between the rays gets larger. Eventually, the gap becomes wider than a single 1x1 grid tile. This results in missing tiles—annoying “stripes of darkness” appearing inside a lit room.

Instead, we use a technique called Perimeter Raycasting.

The algorithm is strictly grid-aligned:

1. Define a square box around the player based on the radius (Top, Bottom, Left, and Right edges).
2. Iterate through every single tile on that square’s perimeter.
3. Calculate a line from the Player to that Target Tile (using Bresenham’s algorithm).
4. Walk along that line, tile by tile, setting Visible = true until it hits a wall.

func (m \*Map) castRay(x1, y1, x2, y2 int) {
line := getLine(x1, y1, x2, y2)

    for _, p := range line {
        // Stop if the ray leaves the map
        if p.X < 0 || p.X >= m.Width || p.Y < 0 || p.Y >= m.Height {
            break
        }

        idx := m.GetIndex(p.X, p.Y)

        // Mark the tile as currently visible
        m.Tiles[idx].Visible = true

        // Permanently mark it as explored (for fog of war memory)
        m.Tiles[idx].Explored = true

        // If the tile is solid matter, light cannot pass through it.
        // Break the loop to stop casting this specific ray.
        if !m.Tiles[idx].Walkable {
            break
        }
    }

}

Because getLine is so highly optimized, I can comfortably cast hundreds of rays every frame without dropping below 60 FPS.

When you strip away heavy abstractions and write algorithms that respect the physical capabilities of the CPU (in this case, basic integer arithmetic), performance stops being a goal you have to fight for and becomes the natural default state of the code.

Further Reading

• What the Hero Sees (Bob Nystrom) - A phenomenal visual breakdown of grid-based FOV algorithms.

This is Part 3 of the Building a Game Engine in Pure Go series. The full source code for Derelict Facility is available on GitHub.