Author Topic: cfov  (Read 9385 times)

Xecutor

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 263
  • Karma: +0/-0
    • View Profile
cfov
« on: May 10, 2013, 01:47:38 PM »
Hello there.

When I was playtesting Tetrogue I found one strange bug in a fov.
I'm using non-recursive shadowcasting implementation.
I tried to fix the bug, but I understood that I have no idea how this algo actually works, despite the fact that I wrote it several years ago. Well, I understand how it is supposed to work, but actual implementation has a lot cryptic flags and variables.

I looked at mrpas. The idea is pretty simple. But actual implementation is not really easy to understand.
While I was thinking about mrpas, I've got an idea.

And this idea is so straightforward, that I don't really understand why I haven't heard about algo like this.
So, here is idea:
The algo requires precomputation. Data for rings up to max sight range radius must be precomputed.
Ring of radius r is set points x,y such that:
floor(sqrt(x*x+y*y))<=r and that point doesn't belong to any ring with radius less than r.
Note, that x*x+y*y<=r*r is NOT equivalent to what I wrote above.
In addition to x,y following info is stored:
indexes of corners that create shadow
octant index of the tile (and second index if tile belongs to two octants).
Actually precomputing this is not strictly necessary, but making these calculation in runtime is not very efficient.
On this image:

indexes of corners that create shadow are 1 and 3.
i.e. lower left corner is 0, lower right 1, upper right 2, upper left 3.


The actual fov calculation works like this:
For each octant there is a list of tiles that block vision.
For each blocking tile starting and ending angles are stored.
Rings from 1 to max sight range are enumerated.
For each ring tiles in this ring are enumerated.
Each tile is checked if it is shadowed by one of blocking tiles in an octant.
If tile is completely shadowed, it is skipped and next is checked.
If current tile is blocking vision and partially shadowed, it is considered visible, and is added to the list of blocking tiles.
If current tile is transparent then it is considered visible if:
at least 50% of it's angle range is visible or at least 20% of it's angle range is visible and median angle is in visible range.

That's all.
Well. Almost. We haven't used corners indexes yet.
Indexes of corners are required to properly implement vision thru diagonal tiles.
Blocking angles of tiles corners that are dungeon corners can be reduced.
Like here:

Here only 60% of possible blocking angle range of corner is used.
This creates diagonal view like here:



So, what are benefits of this algo?
It is reasonably fast. On my PC 1000 fov calculations of range 15 takes around 100ms.
It looks more or less ok. :)
Using this algo it is possible to implement following features almost for free:
 - temporal blockers, to simulate something like bushes, where you can't see several tiles behind the bush, but can see further.
 - delayed blockers, to simulate something like cloudy glass in a window, or low located window.
 - directional fov of arbitrary direction and angle range.

Here are samples and C++ implementation:cfov.
sampleDbg.exe is a little older implementation that shows some debugging information when clicking on tiles.
sample.exe have realtime directional fov mode. In samples green tiles are bushes, grey are windows.
Ah! Almost forgot. cfov stands for Circular Field of View :)
testmap.txt is editable, but the code that reads it is not really foolproof, so be careful.

Method generateFov is template and it's argument MapAdapter must implement following methods:
TileInfo getTile(int x,int y); - returns info about tile
void setVisible(int x,int y); - this one is called to report visible tiles.
int getWidth();
int getHeight();

Hm. Probably instead of getWidth() and getHeight() it is better to make method like:
bool isInside(int x,int y);

Whole CircularFov class is also template and it's parameter is some kind of Point class, that must have
at least members x and y and operator< (to be stored in the std::set).

This is first experimental implementation, so I guess it can be improved in many ways.
Suggestions are welcome.

Thank you for your attention.

eclectocrat

  • Rogueliker
  • ***
  • Posts: 80
  • Karma: +0/-0
  • Most of your personality is unconscious.
    • View Profile
    • Mysterious Castle
    • Email
Re: cfov
« Reply #1 on: May 10, 2013, 02:04:22 PM »
Looks great, but in your Map adapter setVisible function, could you also pass the distance from the fov source, so you can simulate a light gradient, for example? Should be pretty easy, and It'd make it useful as a sort of tile based shadow casting.

Regardless, good luck!

Xecutor

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 263
  • Karma: +0/-0
    • View Profile
Re: cfov
« Reply #2 on: May 10, 2013, 02:25:13 PM »
Yep, that's very easy to add and indeed might be useful.
Forgot to mention in benefits:
each visible tile is reported exactly once.
If it is to be used to gather target for some kind of aoe spell, no need to check for uniqueness.

eclectocrat

  • Rogueliker
  • ***
  • Posts: 80
  • Karma: +0/-0
  • Most of your personality is unconscious.
    • View Profile
    • Mysterious Castle
    • Email
Re: cfov
« Reply #3 on: May 10, 2013, 03:31:19 PM »
Cool, I'll seriously consider switching to this because it supports more options than my fovlib.

Thanks dude!

Xecutor

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 263
  • Karma: +0/-0
    • View Profile
Re: cfov
« Reply #4 on: May 11, 2013, 03:44:53 AM »
Hm. I always knew that it's a bad idea to make serious posts at the late evening.
I forgot to include example of corners rounding.
Here:
Code: [Select]
  int cornAngle=60;
  for(int y=0;y<H;++y)
  {
    for(int x=0;x<W;++x)
    {
      if(m[y][x].ti.block)
      {
        if(y>0 && x>0 && !m[y-1][x].ti.block && !m[y][x-1].ti.block)
        {
          m[y][x].ti.corners[3]=cornAngle;
        }
        if(y>0 && x<W-1 && !m[y-1][x].ti.block && !m[y][x+1].ti.block)
        {
          m[y][x].ti.corners[2]=cornAngle;
        }
        if(y<H-1 && x<W-1 && !m[y+1][x].ti.block && !m[y][x+1].ti.block)
        {
          m[y][x].ti.corners[1]=cornAngle;
        }
        if(y<H-1 && x>0 && !m[y+1][x].ti.block && !m[y][x-1].ti.block)
        {
          m[y][x].ti.corners[0]=cornAngle;
        }
      }
    }
  }
by default elements of corners must be set to 100.

Setup of directional view might look like this:
Code: [Select]
        viewAngle=AngleRange::SCALED_PI/3;
        int a=AngleRange::getAngle(dx,dy);
        AngleRange dr;
        dr.sa=AngleRange::addNorm(a,viewAngle);
        dr.ea=AngleRange::subNorm(a,viewAngle);
        cf.setPermBlock(dr,1);
where dx,dy is offset of the point at which the character is looking.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: cfov
« Reply #5 on: May 11, 2013, 07:36:02 AM »
It is reasonably fast. On my PC 1000 fov calculations of range 15 takes around 100ms.

0,1ms per frame?

Xecutor

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 263
  • Karma: +0/-0
    • View Profile
Re: cfov
« Reply #6 on: May 11, 2013, 08:07:26 AM »
It is reasonably fast. On my PC 1000 fov calculations of range 15 takes around 100ms.

0,1ms per frame?
Yep. And that's more or less worst case. In typical dungeon it's closer to 0.06ms per frame.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: cfov
« Reply #7 on: May 11, 2013, 10:15:20 AM »
Yep. And that's more or less worst case. In typical dungeon it's closer to 0.06ms per frame.

The fov in Kaduria is 2ms per frame in 35x35 area. Maybe I should use your fov:)

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 805
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: cfov
« Reply #8 on: May 11, 2013, 10:43:01 AM »
Very interesting. It seems it should be pretty smooth sailing to implement this on a hex grid, as well ...:)

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.