Blog » Making Grass, part 5: Field of Vision

Making Grass, part 5: Field of Vision

2019-05-09

FOV and memory

Compare the following three screenshots.

• In the first one, we show everything to the player. This is the easiest to implement, but a bit boring.

• The second screenshot implements field of vision (FOV). I calculate which squares are visible to the player, and render everything else in a darker shade. We're also not going to show monsters outside the FOV (for instance, behind closed doors). There is an element of surprise. Still, we know the whole map from the beginning.

• Finally, the third screenshot shows player memory (also known as "fog of war"). In addition to darkening unseen squares, I'm also not showing the squares the player has never seen. (Here, the right part of the map is explored, but the left part is completely unknown for the player, except for the part at the bottom that they glanced from across the river). Now you can go out and explore the map!

Once I had the FOV code, adding memory was pretty easy. It took me about 15 minutes to go "what if I added this array of booleans… now it works".

Smooth transitions

Since I wanted to keep smooth animation, FOV presented an additional challenge. I couldn't just show new fields entering the FOV. I have to add a smooth animation:

This is harder than it looks. Each square can have one of three states:

• unknown (alpha = 0)
• known but unseen (alpha = 0.4)
• seen (alpha = 1)

In addition, the state depends on your position. So when the player is moving between source and destination, I'm taking the "old" state (seen from the source square) and "new" state (seen from the destination square) and interpolate between them.

In addition, there can be monsters coming into your field of view or leaving it, and they are also smoothly animated! So for monsters, I might have to interpolate based on 4 values (player source, player destination, monster source, monster destination).

The good news is that if I ever implement teleportation, all this code should still work the same.

Implications about player knowledge

The visibility has to actually do something, instead of just making the screen slightly darker. This means patching a lot of things:

• As mentioned before, I need to hide monsters that the player cannot see. This is easy but has additional implications.

• I can highlight squares with mouse cursor, and get more information about them. This should be also disabled for unseen squares, and for unknown ones. Wait, I can still describe unseen-but-remembered squares… but I have to be careful not to mention anything about monsters.

• What about pathfinding? I can trace a path through remembered squares, but not unknown ones. Still, I shouldn't take unseen monsters into account. This produces a funny-looking effect when the player character tries to follow a path, enters the room with a monster, sees that the path is blocked and decides to go the other way. Then, when it stops seeing the monster, it wants to go back, and so keeps going back-and-forth between the two paths. I haven't solved this one yet.

The game still "cheats" a bit by showing the current level state for the "remembered" squares. This means we immediately notice if someone opens a door, picks up an item, or (in principle) digs out a corridor in the rock or changes the level in some other way. A more correct implementation would store a "last seen tile" in the player memory, not just a single boolean.

FOV implementation

There are many different methods of computing the FOV for a square grid like the one in roguelikes. Some more interesting properties:

• A more permissive algorithm will allow player to basically peek around the corners. This makes for an easier game but might be slightly unrealistic. It also has some implications for targeting and shooting.

• Some of the algorithms are asymmetric. This means you can see position A from position B but not vice versa. I though I didn't care until I got shot at from the dark.

I chose recursive shadowcasting because it had a short snippet of code, and after reading the description I think I understand it.

If you want to read more about FOV algorithms, there is a very interesting comparative study by Jice and a page by Adam Milazzo. Red Blob Games also has a page about 2D visibility in a more general setting (without grid).

What about all the monsters?

Then I thought, what if I want to calculate FOV for the monsters as well? This gets pretty expensive if I calculate this whole field for every single monster. If I only want to determine whether a monster can see the player, maybe I can just trace a line of sight.

However, I didn't know if the line of sight algorithm will be compatible with my FOV algorithm. I decided to go looking at how other solved it. I have a lot of respect for Dungeon Crawl Stone Soup, and it's being actively developed, so I dove into their code.

Surprisingly, I found that there is no compatibility issue because everything uses the same FOV algorithm, and in fact, all the visibility fields are cached! That is, for every (x, y) on the map, we store a separate 2D map (of size LOS_MAX_RANGE) that specifies which cells are visible.

And come to think of it, this is not a bad idea. If I have, say, a 50 by 50 map, and my field of view is 12 squares long in one direction, I need a 50 x 50 array of 25 x 25 arrays, or 1,562,500 cells in total. If I use one byte per cell (which is doable with ArrayBuffer), that means 1.5 megabytes for the whole level. Not so expensive these days, and I guess I could get it down to 1 bit per cell if I ever needed to.

One subtle corner case, that I also picked up from Crawl, is cache invalidation. If you open or close a door, that will change what squares are visible around that door, so you need to mark all squares in the vicinity (in the FOV radius) for recalculation.