Attempts at a translucent FOV, partial code

I think I did not explain the algorithm correctly, so here is the code. This wont compile since there are other dependencies, but you can at least understand what I am trying to do.

AnyTranslucentAdapterAlgorithm.java

package sid.rpg.los;

import java.util.Arrays;

import rlforj.los.IFovAlgorithm;
import rlforj.los.ILosAlgorithm;
import rlforj.los.ILosBoard;

import static rlforj.util.MathUtils.*;

public class AnyTranslucentAdapterAlgorithm implements ITranslucentFovAlgorithm
{

  IFovAlgorithm algo;
  AnyTransAdVisitBoard atvBoard;
  
  public AnyTranslucentAdapterAlgorithm(IFovAlgorithm algo)
  {
    this.algo=algo;
  }

  public void visitFieldOfView(ITranslucentBoard b, int x, int y, int distance)
  {
    System.out.println("called");
    atvBoard=new AnyTransAdVisitBoard(x, y, distance, b);
    
    algo.visitFieldOfView(atvBoard, x, y, distance);
    
    b.visit(x, y, ITranslucentFovAlgorithm.MAX_VISIBILITY);
    
    int width, height;
    width=height=2*distance+1;
    int[] vis=new int[width*height];
    Arrays.fill(vis, 0);
    vis[(distance)*height+distance]=ITranslucentFovAlgorithm.MAX_VISIBILITY;
    
    int[][] quads={
        { 1 , 1 },
        {-1 , 1 },
        { 1 ,-1 },
        {-1 ,-1 }
    };
    
    for(int q=0; q<4; q++)
    {
    int i = 0;
    int j = 0;
    int sgnx=quads[q][0];
    int sgny=quads[q][1];
    int maxI = distance + distance;
    // For each square outline
    for (i = 1; i <= maxI ; ++i)
    {
      int startJ = max(0, i - distance);
      int maxJ = min(i, distance);
      // Visit the nodes in the outline
      for (j = startJ; j <= maxJ; ++j)
      {
        int adx = i - j;
        int ady = j;
        
        int dx=adx*sgnx;
        int dy=ady*sgny;
        boolean diagonal=false;
        if(!atvBoard.wasVisited(x+dx, y+dy))
        {
          continue;
        }
        
        int[] LEFT  =new int[]{-1, 0};
        int[] UP    =new int[]{ 0,-1};
        int[] LEFTUP=new int[]{-1,-1};
        
        int[][] preferences;
        if(adx>ady) //Bresenham preferences, now not used
        {
          if(2*ady-adx>=0) {
            preferences=new int[][]{LEFTUP, LEFT, UP};
            diagonal=true;
          } else {
            preferences=new int[][]{LEFT, LEFTUP, UP};
          }
        } else {
          if(2*adx-ady>=0) {
            preferences=new int[][]{LEFTUP, UP, LEFT};
            diagonal=true;
          } else {
            preferences=new int[][]{UP, LEFTUP, LEFT};
          }
        }
        int pf, x1=adx, y1=ady;
        
//        Select preferred logic
//        for(pf=0; pf<3; pf++) {
//          x1=adx+preferences[pf][0]; y1=ady+preferences[pf][1];
//          x1*=sgnx; y1*=sgny;
//          if (atvBoard.wasVisited(x + x1, y + y1)
//              && vis[(x1+distance)*height+y1+distance]>0)/* Source location visible */
////          && b.transmitFractionLos(x + x1, y + y1)>0)/* not opaque */
//          {
//            break;
//          }
//        }
//        if(pf==3) //all blocked ??!! Shouldnt happen!
//          continue;
//        int pv=vis[(x1+distance)*height+y1+distance];
        
//        //max logic
        int pv=0, maxPf=-1;
        for(pf=0; pf<3; pf++) {
          x1=adx+preferences[pf][0]; y1=ady+preferences[pf][1];
          x1*=sgnx; y1*=sgny;
          int pv1=vis[(x1+distance)*height+y1+distance];
          if(atvBoard.wasVisited(x + x1, y + y1) && pv1>pv)
          {
            maxPf=pf;
            pv=pv1;
          }
        }
        
        if(maxPf>-1 && preferences[maxPf]==LEFTUP)
          diagonal=true;// wont work
        //avg logic, bad
//        int pv=0;
//        for(pf=0; pf<3; pf++) {
//          x1=adx+preferences[pf][0]; y1=ady+preferences[pf][1];
//          x1*=sgnx; y1*=sgny;
//          int pv1=vis[(x1+distance)*height+y1+distance];
//          pv+=pv1;
//        }
//        pv/=3;
        int v=0;
        int tf=b.transmitFractionLos(x+dx, y+dy);
        if(tf==0)
          v=pv;
        else
          v=(pv*tf)>>15;
        
        if(diagonal && v<ITranslucentFovAlgorithm.MAX_VISIBILITY) {
          v=(v*90)>>7;//divide by root 2 is 45/64, good value 58/64 or 117/128
          if(v>ITranslucentFovAlgorithm.MAX_VISIBILITY)
            v=ITranslucentFovAlgorithm.MAX_VISIBILITY;
        }
        vis[(dx+distance)*height+dy+distance] = v;
        
//        System.out.println("dx dy "+dx+" "+dy+" x y "+(x+dx)+" "+(y+dy));
//        System.out.println("vis calc "+v+" from x1 y1 pv "+x1+" "+y1+" "+pv);
        
        if(v>0)
          b.visit(x+dx, y+dy, v);
      }
    }
  }
    atvBoard=null; //free it
    
  }

  public void visitFieldOfView(ILosBoard b, int x, int y, int distance)
  {
    // TODO Auto-generated method stub
    throw new RuntimeException("Not Implemented");
  }
  
}

Just for reference:
AnyTransAdVisitBoard.java

package sid.rpg.los;

import java.util.Arrays;

import rlforj.los.ILosBoard;
import rlforj.los.GenericCalculateProjection.VisitedBoard;
import rlforj.util.MathUtils;

public class AnyTransAdVisitBoard implements ILosBoard, VisitedBoard
{

  int visitingQuadrant;
  int sgnx, sgny;
  int radius;
  int centerx, centery;
  
  protected int width, height;
  protected boolean[] visited;
  ITranslucentBoard board;
  
  public AnyTransAdVisitBoard(int sx, int sy, int radius, ITranslucentBoard originalBoard)
  {
    this.radius=radius;
    height=width=2*radius+1;
    visited=new boolean[width*height];
    Arrays.fill(visited, false);
    
    board=originalBoard;
    centerx=sx; centery=sy;
  }
  
  public boolean contains(int x, int y)
  {
    return board.contains(x, y) &&
      MathUtils.abs(x-centerx)<=radius && MathUtils.abs(y-centery)<=radius;
  }

  public boolean isObstacle(int x, int y)
  {
    if(!board.contains(x, y))
      return false;
    return board.transmitFractionLos(x, y)==0;
  }

  public void visit(int x, int y)
  {
    visited[(x-centerx+radius)*height+(y-centery+radius)]=true;

  }

  public boolean wasVisited(int x, int y)
  {
    if(!contains(x, y))
      return false;
    
    return visited[(x-centerx+radius)*height+(y-centery+radius)];
  }

}

Attempts at a translucent FOV, Update

I tried to use translucent FOV in a game-like setting so that I can figure out what works and what not.




Initial results looked fine. Note that you cannot see deep into the mist.



















A couple of problems popped up. For example when you are inside a mist, the FOV is square instead of round. This is the result of the fact that the way I do the calculation, the limit of FOV is the point where all "light" is absorbed by the mists. Hence the distance calculation is really approximate and leads to a square FOV.

I had to use this approximate algorithm since the density of the mist may vary from point to point. Hence any kind of radius based calculation is out of question.










Another problem were strange angles the FOV. I realized they were cause by the step of the algorithm that preferentially chose which direction to choose the light from. The direction directly towards the light was given the top preference, with the other two directions being considered after that.








The first problem was solved by tweaking the extra falloff for diagonal moves. I just played around with the number until I arrived at a roughly circular shape.

For the second problem, I started picking up light from the brightest tile ( of the three tiles in the general direction of the light source).



These tweaks seem to have given me a reasonable algorithm. This is the result after the tweaks. The person is standing outside the mist.
















Another example with light and dense mist. Notice the different visible radius for the two kinds of mist. ( Light mist that is not visible kind of looks like dense mist, sorry about the mixup. I hope the picture is still understandable. )
Also note the FOV is roughly circular, although not perfect.




There is much scope for improvement, though I don't know how right now. I think in uniformly misty levels I will just use a smaller FOV radius, and use this algorithm only if I have mix of mist and clear area. ( Shadar Logoth, anyone ? )








On complaints that difference between light and dense fog is not obvious, I make light fog blue. Ugly as heck, but I hope this gets the point across. :P

Attempts at a translucent FOV

All Roguelikes have some sort of Field of View algorithm. You want to hack and slash some monsters, you want to be able to see them first. And quite often you dont want to see through walls(kills the suspension of belief).

The original Rogue (yes, the one which started it all.) took a simplistic approach to FOV. In the room you are in, everything is visible. Nothing outside is visible. Once you are in a corridor, only the corridor tiles adjacent to you are visible, which was fine, since you cannot be attacked on the corridor. This approach still made the game enjoyable.

Modern roguelikes are more sophisticated. You can look into rooms though open doors and windows. You cannot look behind pillars. There are many cool algorithms available. Some of them are really cool and sophisticated. And fast!

Given modern computers, roguelikes with their simple graphics and turn based systems probably dont put too much pressure on the CPU. Some games like Dwarven Fortress use all that CPU for realistic world simulations. Well, what else can you use your free CPU for ?

I decided to try translucent FOV. The idea is that you are looking through smoke or fog, or some such. If you are standing always in the open or in the middle of a fog, its no big deal. You have a large visual radius in open space, and a small radius in fog. However, wont it be cool if you stand at the border of fog and clear air, and you can see a long way into the open, but only a small distance into the fog! You can stand at the edge of a forest, and look miles around in the plains behind you, but only a few feet in front of you in the gloomy forest you are about to enter!

How to do it seems straightforward. Each tile can transmit a certain amount of light, represented by a fraction, 0 to 1. Transparent ones like open ground will transmit all light, ie transmittance 1. Opaque ones will stop all light, ie transmittance 1. Fog will maybe allow 90% of the light, ie transmittance 0.9.

When you want to see if a tile is visible, you trace a line from the center to the tile. You start with a value of 1. At each tile on the way to the destnation, you do a visibility*=transmittance. If the transmittance is 1, you achieve a normal FOV. If it is 0, all further ones are 0 and you get a shadow. If however, transmittance is in between, you achieve an exponential falloff.

So my first attempt was to create a Bresenham FOV. Trace a bresenham line from the center of FOV to every tile in the radius. Do the calculation for each tile on the step.

The results looked promising. :)


The left side of the image are transparent tiles. The right side is foggy. The brightness of the tile indicated amount of light reaching it. Notice the shadow on the upper right.







However, there a few problems with Bresenham FOV, namely:
Notice the missing walls that should be visible. I am sure this problem has been solved by the community, but I couldn't find any good pointers to the solution. So I had to dump Bresenham FOV.

Then I was hit by another idea: Use any FOV algorithm to calculate the lit tiles. Then start from the centre and go progressively outward. From every lit tile, decide which tile lies toward the center from this tile, and use that tiles visibility value to calculate this tiles visibility. If that tile is opaque, then light must be coming here from one of the other two that lies towards the center. Choose one of them, and use it.

..............
...........x3.
...........12.
.....x2.......
.....21.......
..............
..............
..............
..............
..............
.x1...........
.32..........@

From locations marked x, 1, 2 and 3 are respectively first, second and third preference areas from which to collect visibility values.

(UPDATE: I found this method produces strange angles. Now I take the brigtest tile of 1, 2 and 3 as the source of light tile)

Aaand the result is ......


Nice! The visibility is calculated by Precise Permissive, a great algorithm created by Jonathon Duerig. Only that.... notice the corners in the brightness bands? as if the LOS was based on square and not round.






Well let me go ahead and bump the visibility down a bit if it being transmitted diagonally. And you have ......



I am kind of happy :). I will still have to put it in a game to see how it looks and how effective it is. It seems OK fast.








I will try to check in my code in my RLForJ project on sourceforge very soon. The code is in Java.