Improving Symmetric Shadowcasting for Tile Bitmasking

On my spare time, sometimes, I like to write code for my forever-work-in-progress traditional roguelike. I don’t expect to finish it, since it’s mostly a training ground for my favorite language/engine of the day, but I still enjoy trying new things. At this moment, I’m using Rust, and was motivated by the Porklike tutorial to implement nice tiles with bitmasking. The general idea is to have nice-looking walls that form a cohesive structure, instead of a repetitive pattern of the same tile.

A point to consider, though, is that when used naively, a bitmask can reveal information to the player. As an example, this cropped screenshot of Caves of Qud:

The player can’t see behind those two wall tiles. We have the same amount of information for both tiles, yet one is clearly the beginning of a longer wall, while the other is just a pillar. I’m not saying this is a bad thing; maybe it doesn’t matter, maybe it’s even desirable to have this information. Personally I find it removes a bit of exploration and surprise.

A simple solution to this, and the one I chose, is to only apply the bitmasking algorithm on revealed tiles, and assume that non-revealed tiles could be walls; this way a wall is not revealed to be a pillar until you’ve seen all the floor tiles around it. The small counterpart of this method is that somes sprites will suddenly switch (e.g. from “wall part” to “pillar”) according the the tiles you’ve seen or not.

The algorithm I use to calculate the field of view (FoV) is the popular ”Symmetric Shadowcasting”. It works really great, but there is a small problem:

The ? tile is obviously a floor, but the algorithm says that we don’t know what’s there. Since we consider unrevealed tiles to be walls, we’re left with a strange gap between two disconnected walls. Ideally, those two sprites should have smooth corners, a bit like the ones in the bottom.

So what’s happening (and why)? This is what the algorithm sees:

A floor tile is considered to be inside the FoV when you can see its center point. This is the symmetric part of the algorithm, whose goal is to make sure that if you can’t see an enemy, then the enemy can’t see you either.

The missing floor happens to be technically right outside the FoV. That’s why the algorithm doesn’t reveal it, so as not to also reveal a potential enemy who couldn’t see you. While it is a desirable property for gameplay reasons, it makes the dynamic bitmasking look a bit buggy.

And anyway, the player knows it’s a floor, so we might as well show it, right? Let’s fix modify the algorithm, and change the scan() function from this:

### fov_compute.py

def reveal(tile):
	x, y = quadrant.transform(tile)
	mark_visible(x, y)

def scan(row):
	prev_tile = None
	for tile in row.tiles():

		# The tile is revealed if it's a wall,
		# or if it's a floor that satisfies the symmetry rule
		if is_wall(tile) or is_symmetric(row, tile):
			reveal(tile)

# (more code)

To this:

### fov_compute.py

def reveal(tile):
	x, y = quadrant.transform(tile)
	mark_visible(x, y)

def partial_reveal(tile):
	x, y = quadrant.transform(tile)
	mark_visited(x, y)

def scan(row):
	prev_tile = None
	for tile in row.tiles():

		# The tile is revealed if it's a wall,
		# or if it's a floor that satisfies the symmetry rule
		if is_wall(tile) or is_symmetric(row, tile):
			reveal(tile)
		else # this is a floor, partially within the FoV
			partial_reveal(tile)

# (more code)

### game.py

def mark_visited(x, y):
	map[x][y].visited = true

Ta-da. Of course we need to add our third closure mark_visited to the compute_fov() call, but that’s basically it. You could also add a boolean parameter to the mark_visible() function, instead of another closure.

What it does is simply flagging the partially visible floor tiles as “visited”; they’re shown as floors, but greyed out because they’re outside the FoV.

The result:

The tile is correctly registered as floor, it’s displayed as such, and if there’s an enemy on it, they will stay hidden until we’re coming close enough.