pwmarcz.pl

Blog » Making Grass, part 5: Field of Vision

Making Grass, part 5: Field of Vision


Part of a series about Grass, a real-time roguelike engine with pretty graphics.

FOV and memory

Compare the following three screenshots.

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:

FOV transitions

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

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:

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:

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.

Part of a series about Grass, a real-time roguelike engine with pretty graphics.