Fog of War

“Unknowns” are an important part of roguelikes.

One could say they constitute the primary appeal of the genre, especially considering that it makes sense to define “fun” as a result of encountering the unexpected. Thus it’s no surprise that roguelikes are growing in popularity, seeing that they place a heavy emphasis on exploring the unknown.

As described in the article linked above, the best (must “fun”) kind of randomness is that which can be controlled to an extent (or even fully) and/or gives the player sufficient time to react to the results. Players should be able to take advantage of it with the right tools or knowledge, rather than feel frustrated by what seems like whims of the the RNG god (also known as Xom in some circles).

Randomizing as many aspects of a game as feasible is one way of creating unknowns, and another useful one is fog of war. I love this mainstay of the strategy genre, since one of the greatest unknowns is what the heck your opponents are up to.

So Cogmind has fog of war. Duh.

Fog of War

Gaining information about the map is quite important to the gameplay. This already manifested itself in the prototype with roaming groups of sentries that you’d do best to avoid lest they alert their nearby friends until you have an entire mob of robots on your tail, and the fact that the main purpose of each map was to find the “level access” (stairs) to escape.

Map knowledge will become even more important with the addition of machines and a more complex model for how enemies track you down (one you’ll be able to take advantage of).

Among the tools you have at your disposal are the traditional sensors for scanning robots and terrain at different ranges and accuracy, terminals will allow access to many kinds of map data, and now we even have allies who can spot for us (see previous post).

Implementation

While it will be quite useful to keep an eye on multiple parts of the map at once, adding allies that can share FOV information with you throws the prototype’s simple implementation out the window.

Now there are multiple points of origin to consider, so I figure I’d outline the process here for other devs who might be interested in a quick solution.

First of all, how is the FOV of a single unit calculated?

Cogmind uses a brute force Bresenham raycast model that shoots rays from the FOV origin to the edge of a bounding box that represents the farthest possible area visible, and each ray quits after either reaching the maximum sight range or as soon as it hits an opaque wall. Yes, there is lots of overlap, but it also ensures a more liberal result that catches everything that should be seen. It’s worth the extra cost, rather than having the occasional odd piece missing around a strangely shaped map feature. (And becomes absolutely necessary if you want to properly implement semi-transparent cells.)

Here you can see Cogmind’s FOV highlighted.

FOV for each individual unit that needs it is calculated and stored separately as above.

Then, to speed up all the “I need to know if anyone in this faction can see this particular location” checks, a final composite FOV is stored. Unlike the individual FOV map, this one stores a total “count” of how many units can see a particular location. So it is initially filled with 0’s, then as faction member calculates their FOV they increment the count at each location they can see. The numbers are updated every time an individual FOV changes, so when a member moves, for example, they first subtract their own original FOV from the composite, then increment the new recalculated area. This way you not only know which map locations are visible (value > 0), you even know precisely how many units can see it.

0’s are not visible, while other values represent the total number of members that can see that cell.

There are two key optimizations that make this method much faster (on top of the very fast raycasting method that is Bresenham):

The first is to not clear an individual’s FOV map before it’s recalculated--this is a waste of time since the map isn’t changing size, only content. Instead, with each map you store an “FOV ID” which is essentially an integer that equates to the value identifying visible cells on the map. Example: The first time you use a map it is filled with zeros and your ID is set to ‘1’; the raycasting process sets all visible cells in the map to ‘1’; later when you want to know if a particular cell is visible, you just test whether it equals the current ID. Every time you recalculate the FOV, you first increment the ID (2, 3, 4…), so you never have to clear your map in memory. Saves a lot of time if you’re frequently updating numerous maps. (I also use a similar time-saving method with my Dijkstra and A* pathfinding implementations, and in many other areas.)

Another [perhaps no-brainer] enhancement is to only update individual FOVs if they actually see a change on the map. Many aspects of game programming are so much easier when you have a static map, but I’m a big fan of destructible terrain so we have to also deal with changes like wall destruction/creation and doors opening/closing. As long as updates don’t occur immediately (only after an event is completed), you can store a list of all cell locations with changed transparency values. When the event has completed, only update the FOV of any individuals that can actually see at least one of those cells.

In an older SRPG I coded I actually went so far as to divide each FOV into octants and only updated individual octants that contained changes. That’s probably overkill for Cogmind, since very few units will actually rely on FOV (only those that want to share info with Cogmind--the rest will be using faster methods like direct LOS checks etc.).