ALEMIL

Welcome to a blog about application and game development

Field of View in tile based games

Field of View in tile based games 2018-03-04 14:26:20
Est. read time: 4 minutes, 58 seconds

There are multiple algorithms that can calculate Field of View in different ways. Some are more complex and some more performant. Today I would like to explain the implementation I chose in a roguelike game that I am currently working on. It is based on recursive shadowcasting by Björn Bergström. You should check it out if you need to know more theory behind the algorithm. It works really well in a tile-based game, like a roguelike or 2d strategy game.

Field of View algorithm can be used to create multiple game features. It can determine which tiles should be visible to the player, or which tiles should be lit starting from some light source. You could even use the same calculations when animating explosions.

Implementation will be cleaned up a bit but it's based on existing roguelike source code inside Entity Component System. I will comment as much as possible, so hopefully, you won’t have any trouble modifying it to fit your needs. If you find something unclear, don’t hesitate to ask questions in the comments below.

void FieldOfView::calculateFoV(const Entity entity)
{
// Fetch sight component from ECS manager that holds information about range of vision
// and flag defining if FoV should update visibility
const std::shared_ptr sight = this->manager.getComponent(entity);
// Calculations can be skipped when nothing on the map moved
if (!sight->updateFOV) return;

std::shared_ptr position = this->manager.getComponent(entity);

// These multipliers are used when transforming to other octants
// ASEngine::ivec2 is a 2d vector that just contains x, y integers.
std::array x = {
ASEngine::ivec2(1, 0), ASEngine::ivec2(0, 1), ASEngine::ivec2(0, -1), ASEngine::ivec2(-1, 0),
ASEngine::ivec2(-1, 0), ASEngine::ivec2(0, -1), ASEngine::ivec2(0, 1), ASEngine::ivec2(1, 0) };
std::array y = {
ASEngine::ivec2(0, 1), ASEngine::ivec2(1, 0), ASEngine::ivec2(1, 0), ASEngine::ivec2(0, 1),
ASEngine::ivec2(0, -1), ASEngine::ivec2(-1, 0), ASEngine::ivec2(-1, 0), ASEngine::ivec2(0, -1) };

// This is a cached object of map that I use to speed up accessing different locations.
// This allows me to sacrifice a bit of performance in ECS for reduced complexity.
// This method clears all "visible" flags on LocalMap tiles
Systems::inst().getWorldMap().clearVisible();

// Mark player position as visible
Systems::inst().getWorldMap().getCurrentMap()->toggleVisible(true, position->tilePosition);

// Add visible and seen flags to glyphs in the area, for every octant around the player
for (unsigned int i = 0; i < 8; i++) {
this->castLight(position->tilePosition, sight->getCurrentSight(), 1, 1.0, 0.0, x[i], y[i], disable);
}

// Finished calculating FoV
sight->updateFOV = false;
}
Going over the code, we start by determining if FoV should recalculate. The algorithm can take quite a bit of processing power, so if we have a turn based game, we might want to spare some resources by only calculating after something moves.

Next, we clear all "visible" marks from tiles. I have 2 flags per tile defining how and if a tile should be rendered. First is "visible" - that when false, do not render the tile. The other is "seen", which is a memory of the location - player have seen the tile. It doesn't display current state, like enemy standing there, but it is rendered. Only "visible" is cleared for every recalculation.

We mark position of the player to be visible, as it will not be hit by the calulations in castLight function.
When doing the calculations, the screen is split into 8 octants, like so:

Field of view processing
- Green is tile that will be lit in the currently processed octant
- Green turns into yellow when octant is finished processing.
- Red is a tile where vision is being blocked by an obstacle.
- Blue is recursive processing of the tiles that happens when light blocker is hit.



For each of the octants we run our calculations recursively when we hit light blocking entity.
void FieldOfView::castLight(const ASEngine::ivec2 & center, unsigned int radius, unsigned int row, 
float startSlope, float endSlope, ASEngine::ivec2 x, ASEngine::ivec2 y, const std::vector& disable)
{
// If start of the slope is lower than the end slope, scan of the octant is completed.
if (startSlope < endSlope) return;

// Start slope value at the beginning of the row scan is 1.0 and as cells are being processed
// it drops to the value of endSlope (0.0)
float nextStartSlope = startSlope;
// Radius squared
const unsigned int radius2 = radius * radius;

// We want to process as many rows as our range of vision allows. Keep in mind that every octant
// will have it's row calculated from different cell toward another cell. Row here is another
// set of checks, each time started further from the starting position up until range is hit
for (unsigned int distance = row; distance <= radius; distance++) {
bool blocked = false;
for (int deltaX = -distance, deltaY = -distance; deltaX <= 0; deltaX++) {
const float lSlope = (deltaX - 0.5f) / (deltaY + 0.5f);
const float rSlope = (deltaX + 0.5f) / (deltaY - 0.5f);

if (startSlope < rSlope) continue;
if (endSlope > lSlope) break;

ASEngine::ivec2 currentPosition = ASEngine::ivec2(deltaX * x.x + deltaY * x.y, deltaX * y.x + deltaY * y.y);

if ((currentPosition.x < 0 && std::abs(currentPosition.x) > center.x) || (currentPosition.y < 0 && std::abs(currentPosition.y) > center.y)) {
continue;
}

ASEngine::ivec2 mapPosition = ASEngine::ivec2(center.x + currentPosition.x, center.y + currentPosition.y);

const auto currentDistance = static_cast(deltaX * deltaX + deltaY * deltaY);
// If distance from the starting position is lower than squared radius, we mark the spot as visible
if (currentDistance < radius2) {
Systems::inst().getWorldMap().toggleVisible(true, mapPosition);
}

// Previously processed cell blocked the light
if (blocked) {
if (Systems::inst().getWorldMap().isBlockingLight(mapPosition)) {
nextStartSlope = rSlope;
continue;
}
blocked = false;
startSlope = nextStartSlope;
}
else if (Systems::inst().getWorldMap().isBlockingLight(mapPosition)) {
blocked = true;
nextStartSlope = rSlope;
castLight(center, radius, distance + 1, startSlope, lSlope, x, y, disable);
}
}
// If light is completely blocked, don't try to go this path
if (blocked) break;
}
}
At this point you might be thinking - this seems complex, it has already been solved, why bother implementing this? There are multiple libraries and engines that can already to it for you. Unfortunately these same libraries may get in the way of your vision. Let's say for example that you want your player's view to be limited when he loses one of his eyes, or block vision behind him. Such possibilities might not be available with general solutions. If you know how your algorithm works, you can modify it, in this case by disabling some octants.

And to finish, a short presentation of a working algorithm in a roguelike game:

Field of view in a roguelike game

Did you found this article useful? Need to know more? Leave a comment below!



Comments +