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 thrua 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 AlgorithmComing 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 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 shadowBut 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. 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 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 |

Max Goren

maxgoren@icloud.com