FOV, the simple way.


A couple of nights ago i was perusing rogue basin and reddit, just clicking around and i got to thinking about FOV. Truth be told i had NEVER given it
much thought before, and im not sure what made me wind the alley ways to land where i did, but in reading about some of the common methods used in roguelike
games i couldnt help but wonder, "Why so complicated?." Don't get me wrong, i have just as much respect for a good algorithm as the next guys, but some of
approaches just seemed well, over engineered, and some of the edge cases they discusses seemed to be nothing but a by product of said over engineering. So i said
to myself, "Self, What do you know about FOV anyway?". Nothing. So i got to work on my own implemntation.

One of the criteria i set for myself, is it must be simple. No octants, no recursion, and no processor intensive maths(adios cos, sqrt!). After skimming thru
a few cursory articles on FOV, i decided that a variation of raycasting was going to be the way to go. Ray casting is a fancy way of saying "Draw a line from a central point"
as far as you can and then stop." Armed with this intrepid knowledge of casting rays, I knew the first task to tackle: drawing a line. After fooling around with y = mx + b for
a little while i decided to see what other people had come with. /r/aotdev gave me some sage advice a few weeks ago: "You dont have to implement EVERYTHING from scratch." I still
wasnt sure about that, but i took him at his word for it thumbed through a few line drawing algorithms. Let me introduce you to Bresenham's line drawing algorithm.
                        function line(x0, y0, x1, y1)
                        deltax := x1 - x0
                        deltay := y1 - y0
                        deltaerr := abs(deltay / deltax)
                        error := 0
                        int y := y0
                        for x from x0 to x1 
                            plot(x, y)
                            error := error + deltaerr
                            if error ≥ 0.5 then
                                y := y + sign(deltay)
                                error := error - 1.0
                     
Pseudocode for Bresenham's Algorithm

Coming at you all the way from 1962, this bad boy's been drawing lines since before computers had monitors. Perfect. It turns out there really hasnt been that much change
in Line drawing tech in the past 60 some odd years, besides, how complicated can you make a line anyway? And speaking of old algorithms, Dijkstra's Algorithm for shortest paths is even older!
But i digress, back to the task at hand. So now we have an idea of how to draw our lines, err, cast our rays, what ever. Bresenhams Algorithm when translated to C++ by yours truly
Looks like this:

void Bresenham(Point p1, Point p2)
{
    int dx, dy, sx, sy, err, e2;

    dx = abs(p2.x - p1.x);
    sx = (p1.x < p2.x) ? 1:-1;
    dy = -abs(p2.y - p1.y);
    sy = (p1.y < p2.y) ? 1:-1;
    err = dx+dy;

    while (true)
    {
      if (p1 == p2)
            break;
      
      if (onmap(p1)) 
      {
        plot(p1.x, p1.y);
        e2 = 2*err;
        if (e2 >= dy)
        {
            err += dy;
            p1.x += sx;
        }
        if (e2 <= dx)
        {
            err += dx;
            p1.y += sy;
        }
      }
    }
}
                    

Seeing is believing, so i had to take this bad mama jamma from the 60's out for a spin...



Bresenham, Doing lines since the 60's...


After being too excited about drawing a line i sat back down from dancing and started in on the next task at hand. I didnt want my lines just scattering out endlessly in every direction, i knew they
had to stop when they hit a wall or some other obstruction, but what about when theirs nothing to stop them? The starting point for the line is the position of the player, so i decided that the end
point would be a tile say, 8 points away. Figuring out what the Point 8 steps in front of your player is trivial, but i needed to know everysingle tile that was 8 points away in every direction. So i sat
down and started doodling, and what i came up with, was this:
                        [-2,-1][-1,-2][0,-2][1,-2][2,-2]   [8,-2]
                        [-2,-1][-1,-1][0,-1][1,-1][2,-1]   [8,-1]
                        [-2, 0][-1,0][player][1,0][2, 0]   [8, 0]
                        [-2, 1][-1, 1][0, 1][1, 1][2, 1]   [8, 1]
                        [-2, 2][-1, 2][0, 2][1, 2][2, 2]...[8, 2]
                    
Eureka! Do you see it? looking at as columns, the values of the y axis go from -2, -1, 0, 1, 2. and looking at the rows, the values of the x axis go from -2, -1, 0, 1, 2. I knew what needed to be done.
Five minutes later i had the end points for my lines, for whatever length i choose to make them:
void Fov::get_rad(Point p, int radius)
{
    Radius.clear();
    int i; Point next;
    for (i = -radius; i <= radius; i++)
    {
        Radius.push_back({p.x + radius, p.y + i});
        Radius.push_back({p.x + (-radius), p.y + i});
        Radius.push_back({p.x + i, p.y + (-radius)});
        Radius.push_back({p.x + i, p.y + radius});
    }
}
                    

Armed with the end points for my lines, and Bresenhams line drawing algorithm, i was ready to start casting rays like a boss. But just drawing lines in every direction isn't what this is all about.
Well, it kind of is actually. As i mentioned above, we draw the lines until we can't. So I needed to make a slight tweak to the line drawing algorithm. Behold:
void Fov::plot(int x, int y)
{
   marked.push_back({x,y});
}
                        
void Fov::Bresenham(field& layout, Point p1, Point p2)
{
    int dx, dy, sx, sy, err, e2;
                        
    dx = abs(p2.x - p1.x);
    sx = (p1.x < p2.x) ? 1:-1;
    dy = -abs(p2.y - p1.y);
    sy = (p1.y < p2.y) ? 1:-1;
    err = dx+dy;
                        
    while (true)
    {
        if (p1 == p2 || layout[p1.x][p1.y].blocks) //<---changed
            break;
                              
         if (onmap(p1)) 
         {
             plot(p1.x, p1.y);
             e2 = 2*err;
             if (e2 >= dy)
             {
                err += dy;
                p1.x += sx;
             }
             if (e2 <= dx)
             {
                    err += dx;
                    p1.y += sy;
             }
         }
    }
 }
                    

Now the line stops if it encounters a blocking tile before it reaches its end point, and i changed the plot(x,y) function to just store the lines coordinates in a vector instead of drawing it.
This last bit i fiddeled around with before deciding on the vector of points idea, and it has to do with the opposite of raycasting, which is shadow casting. See, i wanted the FOV to act on tiles
that are only CURRENTLY in the platers FOV, not "once you've seen it you can always see it." I'll get back to that in a second though, because i've decided that here is as good a place as any
to present the whole enchillada.
                        class Fov {
                            public:
                            int mapW;
                            int mapH;
                            std::vector<Point> marked;
                            std::vector<Point> Radius;
                            void get_rad(Point p, int rad);
                            void plot(int x, int y);
                            void Bresenham(field& layout, Point p1, Point p2);
                            void plot_fov(field& layout, Point p1, int rad);
                            bool onmap(Point curr);
                            Fov(int mw, int mh);
                            Fov()
                            {
                        
                            }
                        };
                        
                        Fov::Fov(int mw, int mh)
                        {
                            this->mapW = mw;
                            this->mapH = mh;
                        }
                        
                        bool Fov::onmap(Point curr)
                        {
                          if ((curr.x > 0 && curr.x < mapW) && (curr.y > 0 && curr.y < mapH)) 
                            return true;
                          
                          return false;
                        }
                        
                        void Fov::plot(int x, int y)
                        {
                            marked.push_back({x,y});
                        }
                        
                        void Fov::Bresenham(field& layout, Point p1, Point p2)
                        {
                            int dx, dy, sx, sy, err, e2;
                        
                            dx = abs(p2.x - p1.x);
                            sx = (p1.x < p2.x) ? 1:-1;
                            dy = -abs(p2.y - p1.y);
                            sy = (p1.y < p2.y) ? 1:-1;
                            err = dx+dy;
                        
                            while (true)
                            {
                              if (p1 == p2 || (layout[p1.x][p1.y].blocks) 
                                    break;
                              
                              if (onmap(p1)) 
                              {
                                plot(p1.x, p1.y);
                                e2 = 2*err;
                                if (e2 >= dy)
                                {
                                    err += dy;
                                    p1.x += sx;
                                }
                                if (e2 <= dx)
                                {
                                    err += dx;
                                    p1.y += sy;
                                }
                              }
                            }
                        }

                        void Fov::get_rad(Point p, int radius)
                        {
                            Radius.clear();
                            int i; Point next;
                            for (i = -radius; i <= radius; i++)
                            {
                                Radius.push_back({p.x + radius, p.y + i});
                                Radius.push_back({p.x + (-radius), p.y + i});
                                Radius.push_back({p.x + i, p.y + (-radius)});
                                Radius.push_back({p.x + i, p.y + radius});
                            }
                        }
                        
                        void Fov::plot_fov(field& layout, Point p, int rad)
                        {
                            marked.clear();
                            get_rad(p, rad);
                            for (auto e : Radius)
                            {
                                Bresenham(layout, p, e);
                            }
                        }
                    
And there you have it, Simple FOV in less than 100 lines of code. But let get back to what i was saying about Shadows. You see, at first, i was using a property in the points themselves to denote
which points were in the players FOV, a boolean named .fov_lit. And this works, kind of, but it has one really annoying draw back, and its what people refer to as "Artifacts."
You see when a tile comes into view, it becomes visible, all is well. The problem arrises when that tile should than go out of view. It would be easier for me to just show you:

You can see here, when the character is standing next to the pillar, the other side of the pillar remains lit, i.e.
there's no shadow


But now storing the list of which tiles should be lit in an array instead of setting a flag in the tile itsself, We get the desired shadow effect.
The reason this works, is because the vector of Points is cleared before every computation of FOV, so if it was visibile last time, but its not visible now, the change is reflected as such.

All thats needed now is to incorporate it into your main rendering function, what i did was have a boolean for fov_mode, and used "dimming" on the color of the tiles being presented
and the tiles in the fov vector are output at "full color", like this:
void draw(field& layout, std::vector fov)
{
  int x, y;
  for (x = 0; x < map_width; x++)
  {
   for (y = 0; y < map_height; y++)
   {
      if (fov_mode)
      {
  	terminal_color(layout[x][y].color * .55); //<--- dims the color output
	terminal_printf(x,y, "%c", layout[x][y].symbol);
      }
   }
 }
 for (auto p : fov)
 {
   terminal_color(layout[x][y].color);
   terminal_printf(x,y, "%c", layout[x][y].symbol);
 }
}		
			

In the beginning i had set out to come up with a simple, straight foward answer to FOV with minimal math and minimal fuss, and i have to say, i'm pleased with the results!
To see this technique fully integrated, the code demonstrated here, as always, is available on my github: Github Repo



(c) 2020 MaxCodes.info
Max Goren
maxgoren@icloud.com