Fog of war

____________________
/English in grey/ 

/Français en italique bleu/
____________________ 

Hello Villains!
We are going to talk to you about the fog of war which is a new feature we’ve just added.
Fog of war is used mostly in strategy games. It mimics the visibility zone of your units. It’s a darker/fog layer that hides unit and terrain. It disappears as your units approach the fog zone, depending on their vision range.
Bonjour les Méchants !
Nous allons parler du fog of war (ou “brouillard de guerre”), un élément de jeu que l’on a rajouté récemment.

Le fog of war est utilisé principalement dans les jeux de stratégie. Il permet de représenter la zone visible par vos unités. C’est un calque plus sombre qui masque le terrain et les unités ennemies. Il disparaît dès que votre unité approche de la zone de brouillard, en fonction de leur périmètre de vision.

In most strategy games, fog of war adds a “poker” feeling into the game.
Each player doesn’t know what the other player is doing because it’s hidden by the fog of war like you don’t see cards of your opponent in a poker table.
You have to guess what he is doing from the little clue you can get by sending scout units like you would do by looking at the face of your opponent in a poker game. Knowing the play style of your adversary is also a lead. 
Based on this reduced information, you need to guess what you should do to thwart your adversary.
Reducing the information given to the player with the fog of war is actually more fun, as he has to guess things only from clues like a detective!
Dans la plupart des jeux de stratégie, le fog of war ajoute un côté “poker” au jeu.
Chaque joueur  ignore ce que l’autre fait car c’est caché par le fog of war, de la même manière qu’on ne voit pas les cartes de son adversaire au poker.
Il faut deviner ce qu’il fait à partir des petits indices que vous pouvez récolter en envoyant vos éclaireurs comme on examine le visage de son adversaire au poker. Connaître le style de jeu de son adversaire est aussi une piste. Avec ces informations limitées, à vous de deviner quelle attaque lancer.
Limiter les informations données au joueur avec le fog of war est en fait plus amusant, puisqu’il le force à extrapoler à partir d’indices comme un détective !

But as MachiaVillain is a solo game, we added a fog of war in order to benefit from different advantages (not always present in multiplayer game):
– Exploring. Like in an adventure game, the player will have to explore his environment. Of course, this is going to be interesting once we will have monsters/stuff hide in the forest.
– Players will have to make the interesting choice between building/growing and exploring. When do you need to explore to discover new resource?
– It reduces the quantity of information you need to process at the same time at the beginning. You will start with a small portion of the map visible, so you can concentrate your attention learning how to play and not be distracted by the environment. Of course, when you will get better at playing, you will probably start sending your minion exploring your surroundings, at the first to seek resources.
– Hides the type of mineral in rocks. You need to find the best digging strategy to discover precious mineral deposits.
Mais comme MachiaVillain est un jeu solo, nous avons ajouté un fog of war pour bénéficier d’autres avantages (pas toujours présents dans un jeu multijoueur):
– L’exploration. Comme dans un jeu d’aventure, le joueur  devra explorer son environnement. Bien sûr, cela deviendra partciulièrement intéressant quand on aura des monstres et autres surprises cachés dans le décor.
– Les joueurs auront à faire un choix intéressant entre construire/s’agrandir et explorer. Quand aurez-vous besoin d’explorer pour découvrir de nouvelles ressources ?
– Le fog of war réduit la quantité d’information à digérer d’un coup au début du jeu. Commencer avec une petite partie de la carte visible permet de se concentrer sur apprendre à jouer sans être distrait par l’environnement. Bien sûr dès que vous commencerez à maîtriser le jeu, vous pourrez envoyer vos minions en exploration, au départ pour rechercher des ressources.
– Cacher les minéraux présents dans la roche. Vous devrez trouver la meilleure stratégie pour creuser et découvrir les minerais précieux.

Let’s now talk about how we do it technically in MachiaVillain:
The terrain view is partitioned in grid cells. We need to know which grid cell is visible from your minion.
A cell will have 3 states:
– in total Dark (undiscovered)
– hidden in shadow (discovered but not visible)
– visible (seen by at least one of your minions).
Parlons des aspects techniques du fog of war dans MachiaVillain:
La vue du terrain est fragmentée en cellules disposées en grille. Nous devons savoir quelle cellule est visible par vos minions.
Une cellule a 3 états:
– dans le noir complet (zone pas encore découverte)
– caché dans l’ombre (zone déjà découverte, mais pas actuellement visible)
– visible (dans le champ de vision d’au moins un de vos minions)

We have to find out which square is visible by your monster.
We can apply two important rules:
– Monster can’t see too far.
– Monster can’t see through a wall.
Nous devons trouver quelle cellule est dans le champ de vision de votre monstre
On peut appliquer 2 règles importantes:
– Les monstres ne peuvent pas voir trop loin.
– Les monstres ne peuvent pas voir à travers un mur.

For the first rule, we can select all grid cell around the monster from a distance.
This will give us a disk of visibility around the monster.
Pour la première règle, on peut sélectionner toutes les cellules dans un certain périmètre autour du monstre. Cela nous donnera le champ de vision du monstre.

FogOfWarDisk

The second rule is more complex.  We have to find out what is blocking the view of your monster.  Like a real life light ray, we will send a ray from the eyes of the monster.  If the ray hit a something like a wall, it will stop. Each grid cell the ray passed on without being stopped by a wall, is a visible cell. This ray will also stop when it’s too far from the monster (monster view range).
La deuxième règle est plus complexe. Nous devons identifier ce qui bloque la vue du monstre. On lance une ligne à partir du monstre, comme un rayon laser. Si le rayon rencontre un mur, il s’arrête. Chaque cellule traversée par un rayon non interrompu est une cellule visible. Ce rayon s’arrête évidemment à une certaine distance du monstre (périmètre de visibilité du monstre).

To do this we use a field of view algorithms for 2D grid based worlds. You can get a comparison of different algorithms here : Comparative study of field of view algorithms for 2D grid based worlds
We choose a modified version of the BASIC algorithm because we have an outdoor map (not inside a dungeon).
Pour cela, nous utilisons un algorithme de champ de vision pour les environnements basés sur des grilles 2D (pour les anglophones, vous pouvez voir une comparaison des différents algorithmes par ici: Comparative study of field of view algorithms for 2D grid based worlds). Nous avons choisi une version modifiée de l’algorithme BASIC car nous avons une carte extérieure (pas intérieure comme un donjon).

How is it working?
We need to send rays all around the monster (we decide that the monster sees all around him for the Gameplay we want).
To throw a ray we have to know the starting position and the ending position. The starting position is the eyes of the monster.
All around = on a circle. So we are first drawing a circle around our monster. Each cell of this circle will be the target of a ray.
To draw this circle we use an algorithm that draws circles on a 2D grid very fast. We use Andres’ circle algorithm (“Discrete circles, rings and spheres”).
(we used the Bresenham’s circle algorithm at first, but it gave us “hole” in our ray grid, see this illustration )
Of course, the radius of this circle will be equal to the visibility range of your monster.
Comment est-ce que cela marche ?
Nous devons envoyer des rayons tout autour du monstre (nous avons décidé que le monstre voit tout autour de lui). Pour envoyer un rayon,  nous avons besoin de connaître sa position de départ (la tête du monstre) et son extrémité. Tout autour = sur un cercle. Nous commençons donc par tracer un cercle autour du monstre. Chaque cellule de ce cercle sera la cible d’un rayon. Pour dessiner ce cercle, nous utilisons un algorithme qui dessine très rapidement des cercles sur une grille 2D, l’algorithme de tracé d’arc de cercle d’Andres.
(Nous avons commencé par utiliser l’algorithme de tracé d’arc de cercle de Bresenham, mais ils laissait des “trous” dans notre grille de rayon, cf. illustration)

FogOfWarCircle

And then we throw a ray from the monster, targeting each cell of the circle.
Et ensuite nous lançons un rayon partant du monstre vers chaque cellule du cercle.

FogOfWarRay

For this work we use another 2D algorithm which is “Bresenham’s line algorithm” (I promise, the last one!)
In school you may remember that to get a line equation (y=ax+b), and draw it on paper, you need to do some kind of division or multiplication.
With the Bresenham algorithm you only do subtraction and addition, which is more simple even for a computer. And you draw the line one cell at a time, which is great, because if one of the cells of the line is a wall, we just stop drawing the line ICON_Happy
For one ray:
Pour que cela marche, nous utilisons un autre algorithme, l’algorithme de tracé de segment de Bresenham (promis, c’est le dernier !).
Vous vous rappelez peut être que pour tracer une droite d’après son équation (type y=ax+b), vous devez faire une multiplication ou une division.  Avec l’algorithme de Bresenham, vous faîtes seulement des additions et des soustractions ce qui est plus simple même pour l’ordinateur. Et vous tracez la droite une cellule après l’autre, ce qui est très pratique puisque si une cellule sur la droite est un mur, on peut arrêter de dessiner la droite ICON_Happy
Pour un rayon:

FogOfWarOneRay

Everything put together (throw ray on circles cell + stop the ray when it a wall)
Tout ensemble (rayon lancé, cellules du cercle, rayon interrompu par un mur)
FogOfWarRayXoll

And voilà:
Et voilà:

FogOfWarVisibility

What is great with the fog of war algorithm, is that we can use it to also get when enemies are visible or not by your monster.
So we reuse the calculation already done for another purpose. If an enemy is sitting in a visible cell, it’s visible by the monster.
The old algorithm was sending 3D ray, checking polygon and was heavy. Now we have more feature for a lower computation cost!
Ce qui est super avec l’algorithme du fog of war, c’est qu’on peut aussi  l’utiliser pour calculer si un ennemi est visible par un monstre ou pas. Donc nous pouvons réutiliser un calcul déjà effectué pour un autre usage. Si un ennemi est situé sur une cellule visible, il est visible par le monstre.
L’ancien algorithme utilisait un rayon 3D, vérifiant des polygones, et était du coup plus lourd. Maintenant nous avons une feature de plus pour un “coût de calcul” plus faible !

We can go further with the fog of war (just ideas):
– Add more hidden creatures in the forest. So the exploration must be done by strong monsters. Or you will learn to run away ICON_Happy
– Add thieves. So you will have to think strategically where to store your goods, so you always have a monster near to see him coming, and to protect it.
– Patrol against thieves. You can get some of you monster patrolling to detect thieves.
– A monster with a better visibility (“eyes” monster). You can hire a monster with a better view range. So he will be better at exploring and patrolling.
– Let the player deactivate it.
On peut aller plus loin avec le fog of war (quelques idées):
– Ajouter plus de créatures cachées dans la forêt. L’exploration devra être faite par des monstres costauds… ou vous devrez apprendre à fuir très vite ICON_Happy
– Ajouter des voleurs. Il vous faudra choisir stratégiquement où stocker vos richesses de manière à toujours avoir un monstre qui puisse repérer un voleur et les protéger.
– Patrouiller pour détecter les voleurs
– Un monstre avec une meilleure visibilité, qui sera adapté à l’exploration et à la patrouille.
– Un réseau de caméras permettant de surveiller les zones déjà visitées.
– Permettre au joueur de désactiver le fog of war.

I could go on and on about the fog of war, but that’s probably enough already ICON_Happy
Je pourrais continuer à parler du fog of war, mais ça fait déjà beaucoup ICON_Happy

PS: Pictures are drawn by hand to illustrate the explanation and are not 100% accurate with algorithm underneath.
PS: Les illustrations ont été faites à la main pour illustrer les explications, et ne sont pas 100% raccord avec l’algorithme derrière.

2 responses to “Fog of war”

  1. Alexis Pereira Avatar
    Alexis Pereira

    Génial! 😀 Continuez comme ça, ce jeu va déjà au delà de mes attentes quand j’ai soutenu le projet sur Kickstarter

    1. WildFactor Avatar
      WildFactor

      Merci Alexis 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.


     

Sign up to be kept up-to-date with news and offers, 100% spam free!!