Official development blog

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

cogmind_fov

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.

cogmind_fov_composite

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

This entry was posted in Mechanics and tagged , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

5 Comments

  1. Someone64
    Posted November 24, 2013 at 4:25 am | Permalink

    Speaking of fog of war, are you gonna be able to see all parts of the map (as in the map layout) as soon as you enter or are you gonna have to reveal them by moving around and discovering terrain? This is yet another visual effects request but, if the latter, make it so that the completely unrevealed parts of the map have a sort of staticky effect to them rather than the plain and boring black/grey color. Maybe make it so that the unrevealed parts have tiles of solid various grey toned that change constantly.

    • Kyzrati
      Posted November 24, 2013 at 5:50 am | Permalink

      No, you’ll have to learn the map layout. Forgot to mention that part; it’s also a pretty standard roguelike feature of fog of war. Previously explored but unseen areas are faded to various shades of green (as seen in the above images); completely unexplored areas are simply black. The reason for the black (and the reason pretty much every other game does it that way) is that from a player experience perspective you want to keep less important parts of the interface less active, since they shouldn’t be drawing the player’s attention unless they’re important for some reason.

      Explored areas can be affected by corruption, however, and black strips and patterns can appear in them due to memory loss. This is a neat effect, and different from any other game I know of. Unexplored black area will be used for other things that *are* important, too, like icons and possible animations representing positional information gained through hacking.

      • Someone64
        Posted November 24, 2013 at 8:18 am | Permalink

        I think I remember you saying at some point that you were gonna make it so that the game wouldn’t even bet set in the X-COM universe anymore and rather a completely original setting so I guess renaming wouldn’t be much of a problem in the sense that you’d have to give it another name that implies that it’s an X-COM roguelike.

        • Someone64
          Posted November 24, 2013 at 8:18 am | Permalink

          Oops, wrong post to reply to.

        • Kyzrati
          Posted November 24, 2013 at 9:54 am | Permalink

          That’s correct.

Post a Comment

Your email is never published nor shared. Only the anti-spam entry is required. See here for the privacy policy.

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>