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 ScanRowWe 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.