As soon as I’d finished Night of the Life Challenged & Pulse-Impaired, I knew exactly which systems I’d built that would prove inadequate in the game that the 8-day project sought to prepare me for.
Chief among these was the sight system. In the demo, I’d written a simple Raycast-based approach to sight that worked well enough for the demo and was only a couple hours’ work, but I knew I’d have to devise a more sophisticated system when I began work on our current project, Struggle.
What followed was a series of experimentations in my quest for my ideal tile-based sight solution, detailed below.
Implementation One: Raycasting
The sight system implemented in the 8-day zombie-themed prototype was a rather primitive Raycast-based solution, which took only a couple of hours to write. It couldn’t have been simpler; whenever a unit moved, it performed a Raycast hit-check against all units on the opposing team, with the appropriate ignore layer in place of course (so friendly units weren’t counted as obstacles). Units had a limited sight range of about 5m, because the game was set in a dark graveyard, but a unit close enough to one of the street lamps would be seen at any distance.
This worked well enough for the purposes of that project, but it had definite limitations and imposed some requirements that would surely become bothersome when applied to a larger project like Struggle:
- It necessitated colliders on obstructing tiles. That might sound logical, but it complicates writing mouse interactivity with units, doors etc.
- It wouldn’t be practical to use this solution to determine what environment tiles were visible, if I wanted to highlight which tiles were visible and dim those that weren’t, for instance.
- It relied on mesh orientation and distances, creating an element of unpredictability that I’d rather not have if I introduced a new character mesh or environment adornment.
It’s worth noting that I briefly flirted with writing a more sophisticated Raycast-based solution that would calculate the visible percentage of a shooter’s target by raycasting the feet, knees, groin, sternum, shoulders etc. In fact I still like the idea of being able to decide that, for example, if a target’s shoulders and head are the only visible portion of his body then any shot which connected would deal damage and create symptoms tailored to those body parts.
Implementations Two and Three: Shadowcasting
Shadowcasting is a pretty well-known approach to tile-based field-of-vision calculation and seems to be the default algorithm for roguelike developers. I first encountered Shadowcasting in the Roguebasin community (an outstanding community resource for programmers) website, first writing an implementation of Recursive Shadowcasting and later Eric Lippert’s approach as taught in his fantastic series of articles on the subject, Shadowcasting in C#.
Shadowcasting proved that what I needed was such a tile-based approach, that could return to a unit a list of tiles that it could see from their current position; I could re-use this list whenever enemy units moved, saving further calls, or even remove the requirement for an actual line-of-sight check when firing (although I’ll definitely be implementing one soon for missed shots and friendly fire).
The rub, however, was consistency. Shadowcasting creates some pesky edge-cases where, for example, Tile A can see Tile B but Tile B cannot see Tile A. In a small roguelike with primitive AI enemies this would be perfectly acceptable, but when used to create intelligent decision-making AI that needs to be the match of a human player, it’s a vulnerability that would have made my eyes twitch during testing.
The next clue was found in Eric Lippert’s article; actually it was a comment in his example code that pointed me in the right direction:
// A more sophisticated algorithm would say that a cell is visible if there is // *any* straight line segment that passes through *any* portion of the origin cell // and any portion of the target cell, passing through only transparent cells // along the way. This is the "Permissive Field Of View" algorithm, and it // is much harder to implement.
Implementation Four: Precise Permissive Field Of View
The Precise Permissive Field of View algorithm claims to contain no approximation and that it is (theoretically) artifact-free. I must admit I was skeptical at first, but it really is quite brilliant. The essential difference between it and Shadowcasting is that it checks for visibility of a tile from any point within the origin tile, instead of just the center of the origin tile as with Shadowcasting.
One pleasant advantage of the permissive approach is ‘corner peeking’; units will naturally see around a corner. When prototyping said feature in the Raycast-based solution, I was compelled to create a second ‘source of vision’ to effectively pretend that the peeking unit was in their corner tile and the tile beside it (that would grant them a clear view around the corner). I’m sure you’ll breathe a sigh of relief to know such drastic measures weren’t necessary.
While the permissive approach proved itself to be exactly what I needed for Struggle, there is no one sight solution to rule them all. For example, Recursive Shadowcasting is optimal for many roguelike games where it’s used to mimic a light source at the point of the player – or indeed to actually cast shadows upon the map in a 2D lighting system.
Because Struggle is a tile-based strategy game, I didn’t explore options that relied on the 3D engine like creating 3D ‘cone of vision’ volumes or anything of that nature. I’d be interested to find out what the popular techniques in this vein are.