Kind of a long title, but that is exactly what this post is about. I will walk thru an implementation of a 2D shadow casting algorithm in JavaScript for a Phaser JS game.

What Is Shadow Casting For?

What is this useful for? Well in my case, I have a turn based tactics game where I want fog of war and limited visibility based on the terrain. The player’s field of view (or FoV) should only include squares that units that the player controls can see.

Some people also use this type of algorithm for determining which squares are “lit” in a dungeon by a light source.

How Does It Work?

The basic idea is you cast a “ray” down a diagonal and then sweep it across to another diagonal. Anytime you hit something that is marked as a wall (anything you can’t see thru), you stop. That object then casts a shadow along the ray that hit its edge behind it, blocking the view.

There is a somewhat more thorough explanation for it at this website, which is where I adapted my code from (the code there is in python).

The Code

class FovShadow {
    constructor(two_d_map, tile_size, map_offset) {
        this.map_tiles = {}
        this.map = two_d_map
        this.tile_size = tile_size
        this.map_offset = map_offset
    }
}

As you can see this is the constructor of the class. It takes in a two dimensional array representing the map tiles, how many pixels wide a tile is and an offset from the edge of the game screen where the map starts. The last two values are important for determining which tile a unit is on when running the algorithm against its position. The map_tiles variable will hole which tiles are visible to the player.

getVisibleTiles(unit, vision_reset) {
        if(vision_reset) {
            this.map_tiles = {}
        }
        let origin = { x: Math.floor((unit.x - this.map_offset.x) / this.tile_size),  y: Math.floor((unit.y - this.map_offset.y) / this.tile_size) }
        this.markVisible({depth: 0, column: 0}, origin, 0)
        for(let i = 0; i < 4; i++) {
            let first_row = new ScanRow(1, -1, 1)
            this.scanRowForVisibleTiles(first_row, unit.sight_range, origin, i)
        }
    }

This is the function that is called whenever we need to update which tiles are visible. If we moved a unit, we will need to reset the vision.

We determine which tile the unit is on based on their x and y position in the game, the tile size and the offset of the map. Then we mark the tile they are standing on as visible. Finally we begin scanning for visible tiles in each direction (up, right, down, and left).

class ScanRow {
    constructor(depth, start_slope, end_slope) {
        this.depth = depth
        this.start_slope = start_slope
        this.end_slope = end_slope
    }

    getTiles() {
        let row_tiles = []
        let min_column = Math.floor((this.depth * this.start_slope) + 0.5)
        let max_column = Math.ceil((this.depth * this.end_slope) - 0.5)
        for(let i = min_column; i <= max_column; i++) {
            row_tiles.push({ depth: this.depth, column: i })
        }
        return row_tiles
    }

    nextRow() {
        return new ScanRow(this.depth + 1, this.start_slope, this.end_slope)
    }
}

export default ScanRow

We take a short break from the FovShadow class to define the supporting class used by the code that scans for visible tiles, the ScanRow class. A ScanRow represents a row or column of tiles. It is represented by 3 values.

The depth is how many rows or columns removed from our starting point we are. The start and end slopes represent the slope (think geometry slope or algebra slope, its math time) of the rays that mark the diagonals of our field of view between obstacles or the edges of the quadrant we are scanning.

If you can see past a tile, you would call “nextRow()” to recursively begin looking at the next row. Now back to our Shadow Casting class.

    scanRowForVisibleTiles(row, max_depth, origin, direction) {

        if(row.depth > max_depth) {
            return
        }
        let prev_tile = null
        let tiles = row.getTiles()
        for(let i = 0; i < tiles.length; i++) {
            let cur_tile = tiles[i]
            if(this.isWall(cur_tile, origin, direction) || this.isSymetric(row, cur_tile)) {
                this.markVisible(cur_tile, origin, direction)
            }
            if(prev_tile && this.isWall(prev_tile, origin, direction) && this.isFloor(cur_tile, origin, direction)) {
                row.start_slope = this.getSlope(cur_tile)
            }
            if(prev_tile && this.isFloor(prev_tile, origin, direction) && this.isWall(cur_tile, origin, direction)) {
                let next_row = row.nextRow()
                next_row.end_slope = this.getSlope(cur_tile)
                this.scanRowForVisibleTiles(next_row, max_depth, origin, direction)
            }
            prev_tile = cur_tile
        }
        if(this.isFloor(prev_tile, origin, direction)) {
            this.scanRowForVisibleTiles(row.nextRow(), max_depth, origin, direction)
        }
    }

This is our recursive function to go through rows and columns (all called “rows” here) and mark tiles that we can see. We only go as far as our unit can see (they have limited sight range), represented by “max_depth”.

For each tile in our ScanRow, we first check to see if the tile is a Wall, meaning we can’t see thru it. If it is, we mark it as visible. If this tile is a Floor tile and the previous tile we checked is a Wall tile, we need to reset our vision slope and go one step further away. Another way of saying this is, if the tile you are looking at is a Floor and the last tile you looked at is a Wall, look past the Wall. Check what is on the other side.

If the tile you are looking at now is a Wall and the previous tile was a Floor tile, we need to check the next row and limit it to the slope or angle from our origin to the Wall we hit.

If we finished scanning the row and the last tile we looked at was a Floor tile, look at the next row.

That is the basic logic of the Shadow Casting algorithm.

I will include the helper functions below in case you want to implement this yourself. As a note, this is all prototype code and was not written elegantly or efficiently.

    isWall(tile, origin, direction) {
        let coordinates = this.getMapXYCoordinates(tile, origin, direction)
        if(coordinates.y >= this.map.length || coordinates.y < 0) {
            return true
        }
        if(coordinates.x >= this.map[coordinates.y].length || coordinates.y < 0) {
            return true
        }
        return (this.map[coordinates.y][coordinates.x] === WALL || this.map[coordinates.y][coordinates.x] === DOOR_CLOSED)
    }

    isFloor(tile, origin, direction) {
        if(!tile) {
            return false
        }
        let coordinates = this.getMapXYCoordinates(tile, origin, direction)
        if(coordinates.y >= this.map.length || coordinates.y < 0) {
            return false
        }
        if(coordinates.x >= this.map[coordinates.y].length || coordinates.x < 0) {
            return false
        }
        return (this.map[coordinates.y][coordinates.x] !== WALL && this.map[coordinates.y][coordinates.x] !== DOOR_CLOSED)
    }

    isSymetric(row, tile) {
        return (tile.column >= row.depth * row.start_slope && 
            tile.column <= row.depth * row.end_slope)
    }

    markVisible(tile, origin, direction) {
        if(!tile) {
            return
        }
        let coordinates = this.getMapXYCoordinates(tile, origin, direction)
        if(coordinates.y >= this.map.length || coordinates.y < 0) {
            return
        }
        if(coordinates.x >= this.map[coordinates.y].length || coordinates.x < 0) {
            return
        }
        this.map_tiles[`${coordinates.x}_${coordinates.y}`] = { x: coordinates.x, y: coordinates.y, is_visible: true }
    }

    markAllHidden() {
        Object.keys(this.map_tiles).forEach(function(key) {
            this.map_tiles[key].is_visible = false
        }.bind(this))
    }

    getSlope(tile) {
        return new Fraction((2 * tile.column - 1), (2 * tile.depth))
    }

    getMapXYCoordinates(tile, origin, direction) {
        // UP
        if(direction === 0) {
            return { x: origin.x + tile.column, y: origin.y - tile.depth }
        }
        // RIGHT
        if(direction === 1) {
            return { x: origin.x + tile.depth, y: origin.y + tile.column }
        }
        // DOWN
        if(direction === 2) {
            return { x: origin.x + tile.column, y: origin.y + tile.depth }
        }
        // LEFT
        if(direction === 3) {
            return { x: origin.x - tile.depth, y: origin.y + tile.column }
        }

        return { x: 0, y: 0 }
    }

The getMapXYCoordinates helps translate from the ScanRow to the actual 2D map. The getSlope function returns a Fraction class value for a more accurate slope (rise over run or in this case column/row over depth). The isFloor and isWall is pretty self explanatory. However I did implement doors that close and change their values from “Floor” to “Wall” and vice versa.

The isSymetric function is of note. One of the properties of the shadow casting algorithm is that if tile A can see tile B, then tile B can see tile A. If the math doesn’t work out in one direction for some reason, but does in the other then the two tiles are visible to one another.

Wrap Up

I know the explanation is not all that detailed, this was more of a quick breakdown of the implementation in JavaScript for any other Phaser devs out there.

Again, for a thorough breakdown including some handy visuals, check out the post at albertford.com

Keep getting wiser, stronger, and better.

Working on one of the subgame prototypes for a larger game idea and needed to implement pathfinding on a 2D map.

One of the most common algorithms for this kind of pathfinding is called A*  (read as A Star).  The precursor is doing just a Breadth First Search.  I was going to make a full A* implementation but the breadth first search was more than fast enough for my small, 2D maps. And as this is a prototype, going with good enough while I flesh out ideas.

The Algorithm

To begin we want 4 things: the map, your starting point, your target point, and some way to keep track of where you are going next and where you have been.

The explanation I was following referred to the places you have to visit next as the “frontier” and I liked that name so we will use it here.

Begin by putting your starting point in your frontier.
Then we loop over the frontier like this:

• Get the next location from the frontier
• If this location is our target point
  • We are done. Exit the loop.
• If we haven’t visited this location before
  • add it to our visited list
  • get all of its neighbors (up, down, left, right)
  • add them to the frontier if they are not walls
  • mark this location as their parent or previous tile.

Once this loop is complete, because either we hit the target or can’t get to it.  Take the last tile we visited and build a path by backtracking thru the parent or previous tile property until we get to our starting point.

Really a fairly straightforward algorithm that was actually kinda fun to implement and then see working.

This is the rough code I used for the prototype:

class Pathfinder {

    // map is a 2D array of integers, where 0 is a wall and anything else is walkable
    constructor(map) {
        this.map = map
        this.map_width = this.map[0].length
        this.map_height = this.map.length
    }

    findPath(start, end) {
        start.parent = null
        let frontier = [start]
        let neighbors = []
        let visited = []
        let current_point = start
        while (frontier.length > 0 && (current_point.x !== end.x || current_point.y !== end.y)) {
            current_point = frontier.shift()
            if(Object.keys(visited).includes(`${current_point.x}_${current_point.y}`)) {
                continue
            }
                
            neighbors = this.getTileNeighbors(current_point)
            neighbors.forEach(function (n_tile) {
                if(!Object.keys(visited).includes(`${n_tile.x}_${n_tile.y}`)) {
                    frontier.push(n_tile)
                }
            })
            visited[`${current_point.x}_${current_point.y}`] = current_point
        }

        let path = []
        while(current_point.x !== start.x || current_point.y !== start.y) {
            path.unshift(current_point)
            if(current_point.parent == null) {
                break
            }
            current_point = current_point.parent
        }

        return path
    }

    getTileNeighbors(tile) {
        let neighbors = []

        if(tile.x > 0 && this.isFreeTile(tile.x - 1, tile.y)) {
            neighbors.push({ x: tile.x - 1, y: tile.y, parent: tile })
        }
        if(tile.y > 0 && this.isFreeTile(tile.x, tile.y - 1)) {
            neighbors.push({ x: tile.x, y: tile.y - 1, parent: tile })
        }

        if(tile.y < this.map_height - 1 && this.isFreeTile(tile.x, tile.y + 1)) {
            neighbors.push({ x: tile.x, y: tile.y + 1, parent: tile})
        }
        if(tile.x < this.map_width - 1 && this.isFreeTile(tile.x + 1, tile.y)) {
            neighbors.push({ x: tile.x + 1, y: tile.y, parent: tile})
        }

        return neighbors
    }

    isFreeTile(x, y) {
        if(this.map[y][x] === 0) {
            return false
        }
        return true
    }
}

To make this into a more efficient pathfinding algorithm like A* you would need to change the Frontier into something like a Priority Queue that sorts the next tile to check based on a heuristic like distance to target.

You can find another good article comparing Breadth First, A*, and Dijkstra algorithms here.

Keep getting wiser, stronger, and better.