Since I’ve been working hard on getting Ambience’s main storyline finished, I’ve been playing through the game as I complete each part of the story, including all the dungeons. Recently I finished making a new dungeon, and went to try it out for the first time. However, I soon found myself wrestling with a buggy fog system which was supposed to limit the player’s field of vision to the current room or corridor.

I have to admit, I already knew the system was buggy – but I had decided to “leave it to later”, or at least once I had finished the groundwork for the main storyline. But as I played through the dungeon, it soon emerged that the buggy fog of war system made the game needlessly frustrating and near-impossible to play. This couldn’t wait any longer. The fog had to be cleared.

The Main Idea

Most dungeon crawlers have a fog system to limit the player’s line of sight to the current area the player’s in. There are plenty of techniques for doing this, including the famous ray-casting methods. Ambience, however, uses a grid-based motion system, which I decided to take advantage of in my own fog system. I used a data structure which GameMaker: Studio calls a DS Grid, which is basically a 2-dimensional grid which stores integers in each cell. For the fog, I made one of these DS grids and used it to store the current visibility of each cell position in the room. I then used other algorithms to update the visibility (fog values) of each cell as the player moved. (We’ll get into some of these algorithms a bit later, since this was the buggy thing.)

Here’s the grid overlaid on a typical dungeon map, with visible and invisible cells also marked. (Note too that the minimap at the top-left also shows you what areas you’ve seen.)

There’s a catch, though. One of the gameplay mechanics of Ambience involves changing the weather (or “Ambience”), which in turn has an effect on the map – and hence the visibility. For example, activating the Ambience of Sun evaporates any water in the room, turning them into corridors which you can traverse – see the GIFs I’ve linked to below as an example.

With the water gone, the size and shape of the rooms changes, which means the game has to update the room-based grid entries to keep up. The basic idea here is to replace the water values with room or corridor values – but getting it right actually becomes a bit more subtle than that. Again, more on that later.

Fog Algorithms

The Expanding Bubble

Here’s a GIF of the original fog system that I had in place before I set to work fixing it. (Please excuse the poor quality – I’ve included these GIFs only to illustrate the fog patterns, not for crystal-clear gameplay.) As you can probably see, there are quite a few problems, including walking onto dark areas that didn’t update and getting attacked by invisible enemies right next to you.

I like to call the algorithm I used here the “expanding bubble” algorithm, and here’s why. The game decides which cells are visible by drawing a rectangle and making it expand out from the player in each of the four basic directions: left, right, up, and down. Once the rectangle hits a wall, the expansion stops and the player’s left in a rectangular “bubble” of visibility.

The expanding bubble method. The rectangle expands first to the left (red), then to the right (yellow), up (blue) and down (green).

The problem with this method is that it assumes that all the rooms are rectangular in shape, which isn’t true once you evaporate all the water. For non-rectangular rooms, as you move around, the rectangle changes shape very frequently depending on whether there are corridors to the left or right, and so on. Part of the problem is the fact that the bubble expands to the left and right first, giving priority to visibility in those directions; then, once the super-wide bubble starts expanding vertically, it runs into a wall very quickly and so the vertical visibility is much smaller than it should be.

The Laser Pointer

To overcome the problems with super-wide rectangles, I decided to change the visibility “expansion” so that the visibility expanded in a narrow channel in all directions, instead of sweeping out a big rectangle. The result was what I call the “laser pointer” method, which works as follows: the game shoots out straight lines in the four directions like “laser beams”, until it meets a wall, corridor, or something else invisible. It then constructs a rectangle based on the distance the laser beams traveled unimpeded. That rectangle becomes the field of view.

This method is similar to many ray-casting algorithms, which cast out “rays” from a central point (say the player) and restrict visibility to the area where the rays can freely travel without meeting a wall. However, since I was doing all this with a rectangular grid and not with “real” X/Y coordinates, I found it easiest to just focus on the four basic directions instead of having to worry about diagonals.

Here’s a GIF of the result. As a visibility method, it’s slightly more inclusive and so better than before, as seen in the screenshot below. But since it still assumes rectangular rooms, it indiscriminately makes all the tiles visible in that rectangle, including wall tiles and (occasionally) tiles in adjacent rooms.

The field of view looks better now, but look at that isolated tile on the mini-map…

The “walking on fog” problem also reappears, but this is mainly because I told the game not to update the fog while you’re walking around in the room (for efficiency reasons). I did however disable this, forcing the fog to update with each step, but it still gave some odd results – mostly because of the non-rectangular rooms. For example, the player has trouble seeing past isolated wall sections, no matter how far from the wall the player is.

So again, a better method was in order – preferably one which didn’t assume rectangular rooms. But how was I going to do that? And moreover, how could I implement it so that the visibility didn’t have to update with each step?

The Lord of the Rings

While mulling this over late at night, I drafted a possible solution (which I also posted, somewhat cryptically, on Twitter.) Here’s the game plan:

Set all grid cells to be invisible, and make only the player’s cell visible.
Check for invisible cells at a 1-cell radius around the player. If there are any invisible room tiles there which are also adjacent to a visible tile, make them visible.
Check again, this time at a 2-cell radius around the player.
Rinse and repeat, until you reach a radius where the visibility doesn’t change.
Repeat this one more time to make a visible border around the visible region. (This was to make the entrances to any corridors easily visible from the room.)

As you can see in the picture below, the visible region is constructed as a series of concentric rings radiating out from the player.

The rings method. The “border” tiles marked in purple were made visible at the final step, but remained invisible before that.

The result worked like a charm – you could even see around corners! Here’s a GIF of the result too if you’d like to see it in action.

But What About the Water?

Oh yeah, that’s right – we also have to turn the water tiles into room tiles as well! Or corridor tiles? See, the visibility algorithms I described above are just for when the player’s standing in a room; corridor tiles are distinct and have their own visibility process. So when the player activates the Ambience of Sun and dries up all the water in the room, should the ground tiles become rooms or corridors?

That’s a trick question, by the way. If you turn all the water grid values into corridor values, then walking around in a large space (where a large body of water once was) would result in only a two-tile field of vision – not good. On the other hand, turning all the water into rooms leads to problems with too much visibility in narrow corridors origially taken up by narrow rivers of water!

So instead, I decided to use a combination of both room and corridor tiles to replace the evaporated water.

Here’s the basic process: I picked out all the water tiles and turned them all into corridors to begin with. (That took care of the narrow rivers.) Then for all the corridor tiles, I counted the number of adjacent room or corridor tiles. If there were lots of adjacent room tiles, the water value in the grid data structure was then turned into a room; otherwise it remained a corridor. After this process, I could then update the visibility again using the “Lord of the Rings” algorithm without any problem.

The Learning Curve

It’s been a long post, so congratulations for making this far! Just to wrap up, here’s a quick few thoughts on what I learned from all this.

Even simple mechanics you hardly think about can make or break your game. Fog is an excellent example of this. Even though my fog system had been in the game in a broken state for so long, I hardly thought about it until I went ahead and started playing the game. I quickly found that the system made the game barely playable when non-rectangular rooms were involved. That’s not something you want a player to have to endure at all, if possible.
Don’t sacrifice performance for simple systems. You might have noticed that I spent a lot of time playing around with systems that only worked for rectangular rooms. But nothing’s worse than settling on a sub-standard system, or deciding to make a new system and then forgetting about it entirely. Even if your game is early in development, take the time to think about what you want your game to be capable of, and then build your systems to suit.
Finally, don’t be afraid of solving hard problems! The biggest reason why I settled for the sub-standard systems for so long was because I was daunted by the prospect of building a system which would also work for non-rectangular rooms, and quite honestly wasn’t sure where to start. But I got there in the end, and in fact was surprised by how quickly I found a solution. (In fact, writing this blog post probably took more time!) So don’t be afraid to take on a challenging task, even if you don’t know where to start – chances are you can figure out a good solution, too.