October 19, 2017 02:05:11
Web Rarely
The world wants to be deceived. -- Sebastian Brant
:: LOGIN
User:
Pass:
:: RSS FEED
:: SEARCH
Post
.: Roguelike Vision Algorithms | 2014-10-08 06:55AM :.

Table of Contents

  1. Introduction
  2. Desirable Algorithm Properties
  3. Existing Algorithms
    1. Ray casting
    2. Shadow casting (point-to-tile or point-to-point)
    3. Diamond walls (point-to-tile or point-to-point)
    4. Half-width walls (point-to-tile or point-to-point)
    5. Permissive field of view (tile-to-tile)
    6. Digital field of view (diamond-to-diamond)
    7. My algorithm
  4. Comparison
    1. Corner peeking
    2. Corridor asymmetry
    3. Narrow spaces
    4. Diagonal spaces
    5. Rooms
    6. Pillars
    7. Symmetrical versions
    8. Performance
  5. Code
    1. Ray casting
    2. Shadow casting
    3. Diamond walls
    4. Permissive field of view
    5. My algorithm
  6. Further Possibilities
    1. NetHack-style lighting
    2. Light sources
    3. Light falloff
    4. Colored lighting

Introduction

One task when implementing a roguelike is to figure out how to compute the region of the dungeon that's visible to the player or another monster. There are many existing algorithms, but they all have flaws, so I set out to develop a new algorithm that is fast, exact, and aesthetically pleasing to me. Although I didn't create a perfect algorithm, I still think my algorithm is an improvement over the others.

The visible region is called a monster's field of view, and determines whether the monster can see a particular part of the dungeon terrain. I'll assume that the dungeon is tile-based, which is usual. Whether the player can see a tile (called having line of sight and abbreviated LOS) is occasionally different from whether the player can see a monster in that tile, and frequently different from whether he can target that monster with a ranged weapon or spell (called having line of targeting here and abbreviated LOT).

Desirable Algorithm Properties

I'll first describe some frequently desirable traits of a field-of-view algorithm and then show why most existing algorithms lack one or more of these traits.
  • Symmetry: If you can see tile B while standing on tile A, then you should be able to see tile A when standing on tile B. This is generally considered desirable, partly because it's fair, and partly because the asymmetry in vision that almost all asymmetrical algorithms produce leads to poor tactical gameplay when the line of targeting is the same as the line of sight (as is normally the case). An algorithm that manages to be asymmetrical in the opposite of the normal way might actually be better than a symmetric algorithm.
  • Expansive walls: When standing in a (convex) room, you can see all of the room's walls, and when standing in a long corridor you can see all the wall tiles along the sides of the corridor. Although it rarely affects gameplay tactics much, it looks ugly and can make exploration tedious if an algorithm does not have this property.
  • Expanding pillar shadows: When sight is blocked by a pillar (an opaque tile not connected to others), the pillar should cast a shadow in the shape of a circular sector. This usually allows for more tactical gameplay, since it's easier to hide from, ambush, and escape other monsters. However, many roguelikes don't generate pillars, making this less relevant for them.
  • No blind corners: You can see at least two tiles around a corner, so that if you move diagonally around the corner, you won't find yourself next to (and being gored by) a monster you couldn't see. This also implies that you can see at least two tiles to either side before stepping into a hallway. This is desirable in most cases, since it's tedious if players must step carefully around every corner. Some algorithms allow you to see infinitely far around corners, protecting you from monsters with ranged weapons as well.
  • No artifacts: Although there can be reasonable disagreement over what the "right" behavior is for a field-of-view algorithm, an algorithm should at least do what it's supposed to. Generally this means that the algorithm should define the world geometry and accurately model light propagation within that geometry. The main causes of artifacts are the algorithm simply not corresponding to the world geometry, the algorithm being implemented using approximate rather than exact math, and bugs in the implementation.
  • Efficiency: The algorithm shouldn't take a long time, and preferrably should avoid testing the same tiles repeatedly.

Existing Algorithms

This is not an exhaustive list of algorithms, but covers the most frequently used ones.

Ray casting

Pros: Simple. Pretty fast. Expanding pillar shadows. Good balance of light and shadow. No blind corners. Cons: Asymmetrical. Lots of gaps. No expansive walls. Quirky.

Ray casting involves casting rays from the player to every point along the edge of the map or every point along the circumference of the player's view radius. The rays are cast using a simple line-drawing algorithm, usually Bresenham's, which stops as soon as it hits a wall. Ray casting is the simplest algorithm, and quite fast, but it has numerous problems. First, it's highly asymmetrical. Bresenham's algorithm isn't symmetrical, but even if you use a symmetrical line-drawing algorithm (which causes its own problems), the result will still be asymmetrical because the endpoints of the lines aren't simply reversed when you alternate positions. The algorithm also has gaps in both visible points and shadows and is generally very quirky. Gaps in the walls can be fixed up in a post-processing pass, which removes the ugliest artifacts, but this slows the algorithm and doesn't fix the other problems. The algorithm tests tiles multiple times, making it somewhat inefficient, but due to its simplicity it still ends up being pretty fast, especially with a small sight radius. (Ray casting has a reputation for being the fastest algorithm by far, but that's mainly due to people's generally poor implementations of more complex algorithms. A well-implemented shadow casting algorithm beats ray casting every time.) Leaving aside the numerous gaps and asymmetries and just considering the shapes of light and shadow, ray casting produces nicer results in my opinion than more complicated algorithms like shadow casting and diamond walls. Also, most of its problems become less severe as the sight radius decreases, and with a circular sight radius of 4 or less it actually works very nicely, with no post-processing required (although some artifacts remain).

──────────────┤
∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
─────┬┬─∙┌┬∙∙∙∙∙+
     ├┘∙∙└┤  └─────┤
Gaps in walls
(can be fixed with post-processing)
∙∙∙∙∙∙∙∙∙∙∙∙
∙@∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙┼∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙
Gaps in shadow
∙∙∙∙∙∙@∙∙∙∙∙∙
∙∙∙∙┼∙┼∙┼∙∙∙∙
∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙
Shadow asymmetry
────────────
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌∙∙
     ├┘∙∙└┤  └───
More gaps (see next two)
─────────────
∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬∙∙
     ├┘∙∙└┤  └───
Shadow disappears
────────────∙∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬─
     ├┘∙∙└┤  └───
Shadow partly reappears

Code to implement ray casting is below.

Shadow casting (point-to-tile or point-to-point)

Pros: Fast. Expanding pillar shadows. Expansive walls. Continuous point visibility. Cons: Diagonal vision much narrower than cardinal. Blind corners. Beam expands too much through a door. Asymmetrical. Nontrivial to eliminate all artifacts.

Shadow casting is the technique of casting circular sectors of light outward from the player. When a sector hits a wall, the sector may be reduced in angle or split into two sectors which are then processed independently. Implementations vary, but a good implementation will visit each tile only once, or nearly so, and a small and roughly constant amount of work is done per tile. This makes shadow casting one of the fastest algorithms if implemented well, but in poor implementations it can perform relatively slowly in diagonal tunnels and in open areas with lots of small obstructions. "Shadow casting" is a bit of a misnomer because what's actually cast is light, but I'll use it since "light casting" seems too similar to "ray casting". In every case I've seen, shadow casting has used square tiles, but other tile shapes are possible.

In the usual implementation, shadow casting renders a tile visible if there is an unobstructed line from the center of the player's tile to any part of the target tile. Here's an example to illustrate how shadow casting works for a single octant. (Not all implementations work in octants.) In the first picture, a 45-degree sector of light is projected down the 45-degree octant. The green line bounds the top of the sector and the blue line bounds the bottom. The fractions displayed are the slopes of the lines, which are always from 0 to 1 (inclusive). Tiles with circles are considered visible. Then, the algorithm works from left to right (increasing X). For each column, it scans from the top tile within the sector down to the bottom tile within the sector. If a transition from clear to opaque or vice versa is found, the sector is adjusted. In the second picture, the first three columns have been scanned and a transition from opaque to clear has been found in the fourth column, so the top vector is adjusted downward. In the next picture, a clear-to-opaque transition has been found and the bottom vector is adjusted upward. In the final picture, you can see that both types of transitions were found in the fifth column, so the sector splits into two sectors, each of which continue independently. The algorithm stops when it hits the maximum sight distance or all the sectors become empty (bottom slope > top slope).

Here are some of the features and problems of shadow casting (with the usual square tiles).

∙∙∙@┼∙∙∙∙∙
∙∙∙┼∙∙∙∙∙∙
∙∙┼∙∙∙∙∙∙
┼∙∙∙∙∙∙∙
┼∙∙∙∙∙∙∙∙
Thin diagonal spaces
∙∙∙@┼∙∙∙┼∙
∙∙∙∙∙∙∙∙∙∙
∙∙∙∙┼∙∙∙┼∙
∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙
In this case too
───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
Has blind corners
───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└
Asymmetrical
(compare w/ previous)
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
Gaps in pillar shadows
(not an artifact, just ugly)
∙∙∙∙∙∙∙∙│ 
∙∙∙∙┼∙│∙∙│ 
∙∙∙∙∙∙│∙∙│ 
∙∙∙∙∙∙∙∙∙└∙@∙∙∙│∙∙∙∙∙
Red shouldn't be visible
(implementation artifact)
∙│                   │∙∙∙∙∙∙∙∙∙∙∙
∙└───────────────────┤∙∙∙∙∙∙∙┼∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─∙┌┬────────┤∙∙∙∙∙∙∙┼∙∙∙
       ├┘∙∙└┤        │∙∙∙∙∙∙∙∙∙∙∙
Always a three-high beam through a door, and the beam isn't blocked by pillars
(not an artifact, but very ugly)

The asymmetry displayed above is an example of how asymmetrical algorithms tend to create unsatisfying tactical situations. If you can target what you can see, then the monster in the middle of the corridor would have an advantage over a monster on the side of it, despite the monster on the side appearing to have better cover. The monster on the side could be shot without even seeing the attacker. Asymmetries like these are why symmetry is considered a desirable property. However, if the asymmetry was reversed, it might actually be an improvement over symmetrical algorithms by allowing you to take cover, giving a more tactical feel to the gameplay (although it would probably be best if the visibility was symmetrical but not the targeting). There is an algorithm called "reverse shadow casting" which reverses the asymmetry, but it generally looks much poorer and runs much slower.

A small modification to the shadow casting code suffices to make it symmetrical, though. This works by changing the algorithm so it considers a tile visible only if there's an unobstructed line from the center of the player's tile to the center of the target tile (rather than any part of the target tile). This fixes some problems and causes others, as you can see below.

───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└
Symmetrical,
no expansive walls
──────
    │∙∙∙∙∙∙∙∙∙∙∙∙
    │∙∙∙∙∙∙
    │@∙∙∙∙∙
No expansive walls
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
No shadow gaps
∙∙∙∙∙∙∙∙∙│ 
∙∙∙∙┼∙∙│ 
∙∙∙∙∙∙│∙∙ 
∙∙∙∙∙∙∙∙∙└─
∙@∙∙∙│∙∙∙∙∙
Artifact is gone
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Better propagation through narrow spaces

Code to implement basic shadow casting is below.

Diamond walls (point-to-tile or point-to-point)

Pros: Pretty fast. Expanding pillar shadows. Expansive walls. No blind corners. Mostly continuous point visibility. Cons: Beam expands too much through a door. Asymmetrical; a small change fixes this but loses expansive walls and causes more visual discontinuities.

Like shadow casting, the diamond walls algorithm treats a tile as visible if there's an unobstructed line from the center of the player's tile to any part of the target tile. However, for the purpose of occlusion it treats walls as though they were diamonds (embedded in the tile, the remainder being empty space). This eliminates the thin diagonal spaces from the standard shadow casting algorithm and allows better peeking around corners, but it causes a couple problems of its own. The main new problem is that it is, in my opinion, a bit too permissive, meaning that it makes too many tiles visible. Nonetheless it seems like an improvement on standard shadow casting. (I chose to implement it by modifying my shadow casting code.) As for efficiency, it is somewhat slower than plain shadow casting, since it needs to do more work per tile, but it's still reasonably fast.

Treating walls as diamonds actually makes a lot of sense in roguelikes, although it sounds ridiculous. The reason is that most roguelikes allow monsters to move between diagonally adjacent walls, and if the walls were square, their corners would be touching, leaving no space. This is illustrated in the picture below. Making the physics of the world more consistent naturally leads to more intuitive lighting. Diamond walls also allow better vision around corners, which is usually desirable.

Unfortunately, there is a theoretical problem with diamond walls. The description states that lines tangent to a wall diamond aren't considered to intersect it and zero-width beams of light still illuminate tiles. This provides better vision around corners but also allows the following case where a monster can see through a wall. Implementations are expected to disallow seeing through walls as a special case, which prevents the problem but requires inconsistent physics.

Here are some features and problems of shadow casting with diamond walls.

   │∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙┼
∙∙∙■∙∙∙∙∙┼@
Visibility through diagonals
@┼∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙
Here too
──────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
No blind corners
───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└
Still asymmetrical
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
Bigger shadow gaps
than shadow casting
           │∙∙∙∙∙∙∙∙∙∙∙
───────────┤∙∙∙∙∙∙∙┼∙∙∙
@∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙
∙┌┬────────┤∙∙∙∙∙∙∙┼∙∙∙
∙└┤        │∙∙∙∙∙∙∙∙∙∙∙
Same problem casting through narrow spaces

The same simple change can be made to turn the diamond wall algorithm into a symmetric one, and it has the same benefits and drawbacks that it has for regular shadow casting.

───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└
Symmetrical,
no expansive walls
──────────┐
∙∙∙∙∙∙∙∙∙∙│
@∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
No expansive walls
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
No shadow gaps
├───∙──────
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙┼┼∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙│
Discontinuous visibility
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Better propagation through narrow spaces

Code to implement diamond walls is below.

Half-width walls

Pros & cons: The same as diamond walls, but more permissive and slightly slower.

There is another idea similar to diamond walls except that it uses walls that are half the usual width. It also solves the problem of not being able to see between diagonal tiles, but in my opinion looks poorer than diamond walls by being too permissive. The implementation is also slightly slower since not every wall tile has the same shape. (The shape depends on whether there is an adjacent wall for it to join with.) I implemented the algorithm but I don't consider it worth the effort to present.

Permissive field of view (tile-to-tile)

Pros: Symmetry. No blind corners. Expansive walls. Continuous point visibility. Cons: Slow. No expanding pillar shadows. Perhaps too much visibility around corners.

The permissive field of view algorithm treats a tile as visible if there's an unobstructed line from any part of the player's tile to any part of the target tile. Most implementations of this use an approximation, such as just testing the corners against each other, which fails in some cases. Exact implementations work in all cases but tend to be fairly slow. I provide an exact implementation (cleaned up and adapted from a demo by Jonathon Duerig). The main features of the algorithm are that it's symmetrical and allows peeking very far around corners, but it's too permissive for my taste, so I haven't made any effort to optimize the algorithm. That said, the algorithm looks and works much better if all creatures have a short sight radius.

There exists a version of the permissive FOV algorithm that allows the permissivity to be changed at runtime. I played with it, and half the usual permissivity looks decent to my eye, but then it's no longer symmetrical and I'd prefer to have a faster algorithm anyway.

   │∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙
∙∙∙■∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼@
   │∙∙∙∙∙∙∙∙∙
Thin pillar shadows
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Pillar shadow gaps
─┴─────────■───
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@┌─────────■───
∙│∙∙∙∙∙∙∙∙∙∙∙∙∙
+┤∙∙∙∙∙∙∙∙│∙∙∙∙
Can see all the way around corners
│∙│                 ┌┬───┐
│∙├┬────────────────┴┘∙∙∙│
│∙└┘∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙┌─┘
│@∙∙∙┌─────────────────┘  
└────┘                    
Including down Kuo corridors

Code to implement the permissive field of view algorithm is below.

Digital field of view (diamond-to-diamond)

Pros & cons: Same as the permissive field of view algorithm.

The digital field of view algorithm treats every tile as a diamond (embedded in the square, the remainder being empty space) and considers a tile visible if there is an unobstructed line from any part of the player's diamond to any part of the target diamond. As a result, it's slightly more permissive than even the permissive field of view algorithm (since walls present less of an obstruction), but otherwise it shares all the same features and drawbacks while being even slower. The idea is based on the rather unwieldy concept of digital straight line segments, and I did not bother to create an implementation of it. One interesting feature of the algorithm is that the knowledge of the digital line segment from a line-of-sight calculation allows easy tracing of a projectile path through space without hitting any walls, even down somewhat twisted tunnels (such as the Kuo corridor above). But the complexity seems to outweight the benefit.

My algorithm

None of the above algorithms really satisfy me. First of all, except for ray casting they're all either too permissive or too restrictive – sometimes both at once, and ray casting has too many artifacts to be usable. Here are the problems I intend to fix and the features I intend to have.
  • Less permissive than most other algorithms
  • More symmetrical than other algorithms
  • Able to be made symmetrical (at least versus non-passwall monsters) without losing expansive walls
  • Good vision through diagonal spaces, but not too much
  • Good light casting through narrow spaces, without losing expansive walls
  • Reduced shadow gaps compared to other algorithms
  • Efficiency on par with diamond walls
  • No blind corners
  • No artifacts
  • Consistent physics
To accomplish this, I'll represent the dungeon geometry as in the following image. (NOTE: Two corners in the second image should be beveled. I drew it incorrectly. Nonetheless, the image illustrates the utility of the inner square.)

A corner is beveled if neither of the two cardinally adjacent tiles are walls. Wall tiles are considered visible if a beam of light intersects the wall shape while clear tiles are considered visible if light intersects the central square (which can be at most 1/2 the width or height of the tile). Tangents to a shape do not intersect it, and a zero-width sector of light can't illuminate anything.

Solid walls with beveled edges allow peeking around corners and seeing through diagonal spaces while avoiding the theoretical problem of diamond walls. Not showing clear tiles unless light passes near the center should make it a bit less permissive, reduce shadow gaps, reduce asymmetry, and fix the behavior of light passing through narrow spaces.

The problem with light passage through narrow spaces is illustrated in the second image above. No matter how far you are down the tunnel, the circular sector will open up as it leaves the narrow space and, with other algorithms, immediately illuminate the tiles above and below. As seen in the screenshots above, pillars cannot stop this illumination. The reason is that, like the walls of the tunnel, the sector is still opening up after it passes between the pillars. Not illuminating tiles only barely touched by light avoids this, and allows pillars to effectively stop the light. This should also reduce shadow gaps by preventing small slivers of light from dispelling the shadow from a tile.

Permissivity can be tuned by adjusting the angle of the bevel and the size of the inner square. Another shape besides a square can be used, but it must fit within the area of the largest diamond that can be placed in the tile (i.e. it may not extend beyond the shape of a pillar). For a square, the maximum is 1/2 the width of the tile. Testing shows that using 1/2 the width gives good results. Using 3/8 the width of the tile allows for symmetrical sight between creatures in and on the side of a narrow corridor, which is a nice feature, but it looks a bit too restrictive otherwise (especially if there are many pillars), so I'll stick with 1/2. The actual implementation will use a modified shadow casting algorithm, giving decent performance as long as I can avoid doing too much work per tile.

Here are some samples from the asymmetrical version.

∙∙∙@┼∙∙∙∙∙
∙∙∙┼∙∙∙∙∙∙
∙∙┼∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙
Good diagonal vision
@┼∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙
Here too
───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
No blind corners
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
Fewer shadow gaps
         │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────────┤∙∙∙∙∙∙∙┼∙∙∙@∙∙∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
┬────────┤∙∙∙∙∙∙∙┼∙∙∙∙
┤        │∙∙∙∙∙∙∙∙∙∙∙∙∙
Good behavior casting through narrow spaces

My algorithm has two symmetrical versions: one that's fully symmetrical and another that's symmetrical except for some walls (i.e. symmetrical between monsters except sometimes against passwall monsters). Here's the version that's mostly symmetrical. As you can see, it doesn't suffer from the same problems of other algorithms when made symmetrical. Most importantly, it doesn't lose the expansive walls feature. This is the better of the two symmetrical versions, unless you need symmetry versus passwall monsters.

           
───────────
@∙∙∙∙∙∙∙∙∙∙
┬┬─┌┬─────
├┘∙∙└┤     
Symmetrical non-walls,
expansive walls
──────────┐
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
@∙∙∙∙∙∙∙∙∙│
Expansive walls
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙┼∙∙
∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
No shadow gaps

Here is the fully symmetrical version of my algorithm. It gains symmetry against all passwall monsters but loses expansive walls as usual, although walls are no less expansive than other algorithms (except permissive FOV) and more expansive than most. It is very similar but not identical to symmetrical diamond walls.

           
───────────
@∙∙∙∙∙∙∙∙∙∙
┬┬─┬─────
├┘∙∙└┤     
Symmetrical,
no expansive walls
──────────┐
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
@∙∙∙∙∙∙∙∙∙│
No expansive walls
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙┼∙∙
∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
No shadow gaps

Code to implement my algorithm is below.

Comparison

Here's a comparison of my algorithm with the ray casting, shadow casting, diamond walls, and permissive field of view algorithms. Unless otherwise stated, the comparison is done between the basic (usually asymmetrical) versions of the algorithms. In some sections I've reduced the line height in order to make the height of a tile closer to its width, allowing a better sense of symmetry on the two axes. Depending on your font and browser, this might look terrible, especially in vertical walls. To toggle this effect, click here. (This requires Javascript, and the effect is only enabled initially if Javascript is available.)

Corner peeking

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
Ray casting
───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
Shadow casting
──────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
Diamond walls
───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
My algorithm
───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  
Permissive FOV

Corridor asymmetry

Red tiles are where a monster can see the player but the player can't see the monster.

∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       
Ray casting
∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       
Shadow casting
∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       
Diamond walls
∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       
My algorithm (1/2-width inner square)
∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       
My algorithm (3/8-width inner square)
∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       
Permissive FOV

Narrow spaces

In this and subsequent sections I've reduced the line height of some sections in order to make the height of a tile closer to its width, allowing a better sense of symmetry on the two axes. Depending on your font and browser, this might look terrible, especially in vertical walls. To toggle this effect, click here. (This requires Javascript, and the effect is only enabled initially if Javascript is available.)

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙
Ray casting
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙
Shadow casting
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙
Diamond walls
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙
My algorithm
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙
Permissive FOV

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
Ray casting
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
Shadow casting
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
Diamond walls
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
My algorithm
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
Permissive FOV

Diagonal spaces

∙∙∙∙∙∙∙+
∙∙∙∙∙∙+∙
∙∙∙∙∙+∙∙
∙∙∙∙+∙∙∙
∙∙∙+∙∙∙∙
∙∙+∙∙∙∙∙
@+∙∙∙∙∙∙
Ray casting
∙∙∙∙∙∙∙+
∙∙∙∙∙∙+∙
∙∙∙∙∙+∙∙
∙∙∙∙+∙∙∙
∙∙∙+∙∙∙∙
∙∙+∙∙∙∙∙
@+∙∙∙∙∙∙
Shadow casting
∙∙∙∙∙∙∙+
∙∙∙∙∙∙+∙∙∙∙∙+∙∙
∙∙∙∙+∙∙∙
∙∙∙+∙∙∙∙
∙∙+∙∙∙∙∙
@+∙∙∙∙∙∙
Others

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@
Ray casting
───────
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@
Shadow casting
┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@
Diamond walls
┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@
My algorithm
┌──────│∙∙∙∙∙∙│∙∙∙∙∙∙│∙∙∙∙∙∙│∙∙∙∙∙∙│∙∙∙∙∙∙┤∙∙∙∙∙∙+
■∙∙∙∙∙+@
Permissive FOV

┌──────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@
Ray casting
┌──────
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@
Shadow casting
┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙∙∙│∙∙∙∙∙∙│∙∙∙∙∙+∙∙∙∙∙+∙
■∙∙∙∙+∙@
Diamond walls
┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@
My algorithm
┌───────
│∙∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@
Permissive FOV

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@
Ray casting
───────
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙+
∙∙∙∙∙∙+∙∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@
Shadow casting
┌───────│∙∙∙∙∙∙∙│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@
Diamond walls
┌───────│∙∙∙∙∙∙∙│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@
My algorithm
┌──────│∙∙∙∙∙∙∙│∙∙∙∙∙∙│∙∙∙∙∙∙∙∙
│∙∙∙∙∙│∙∙∙∙∙∙+
│∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@
Permissive FOV

Rooms

 ┌───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────┘
Ray casting
 ┌───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────
Shadow casting
───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│∙∙∙∙│ └─────┘
Diamond walls
───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────┘
My algorithm
───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│∙∙∙∙│ └─────┘
Permissive FOV

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
Ray casting
│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
Shadow casting
│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
Diamond walls
│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
My algorithm
│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
Permissive FOV

───────┬
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙
Ray casting
────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙
Shadow casting
───────┬
∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙
Diamond walls
───────┬
∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙
My algorithm
────────┬
∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙
Permissive FOV

────┬
∙∙∙∙∙│
∙∙∙∙∙
+∙│∙│
∙∙│∙∙∙∙∙∙∙└
@│∙∙∙∙
Ray casting
────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙
Shadow casting
────┬
∙∙∙∙∙│
∙∙∙∙∙
+∙│∙∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙
Diamond walls
────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙
My algorithm
────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙∙
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙
Permissive FOV

┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙
   │∙└
Ray casting
┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙│
   │∙└
Shadow casting
┌─┐   
│@└──┐
│∙∙∙∙└──┐∙│∙│
   │∙└
Diamond walls
┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙
   │∙└
My algorithm
┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙│
   │∙└
Permissive FOV

┌─┘∙└┬─┐
│∙∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘
Ray casting
┌─┘∙└┬─┐
│∙∙∙∙│∙
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘
Shadow casting
┌─┘∙└┬─
│∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘
Diamond walls
┌─┘∙└┬─┐
│∙∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘
My algorithm
┌─┘∙└┬─┐
│∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘
Permissive FOV

┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│─┬+┬──┘
Ray casting
┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│
└─┬+┬──┘
Shadow casting
┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│∙∙∙∙∙∙│
└─┬+┬──┘
Diamond walls
┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│─┬+┬──┘
My algorithm
┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│∙∙∙∙∙∙│─┬+┬──┘
Permissive FOV

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─
Ray casting
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘
Shadow casting
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴
Diamond walls
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴
My algorithm
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘
Permissive FOV

│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙──────┤
│∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
Ray casting
│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
Shadow casting
│∙│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙──────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
Diamond walls
∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙──────┤
│∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
My algorithm
│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
Permissive FOV

────────
∙∙∙∙∙∙∙∙
┬∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│
Ray casting
────────
∙∙∙∙∙∙∙∙
┬∙┌┬───
┘∙└┤   
∙∙│└┐  
∙┌┴┐└┐ 
┌┘ └┐∙└┐
┘   └┐@│
Shadow casting
───────
∙∙∙∙∙∙∙∙
┬─∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│
Diamond walls
───────
∙∙∙∙∙∙∙
┬─∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│
My algorithm
────────
∙∙∙∙∙∙∙∙
┬∙┌┬───
┘∙└┤   
∙∙│└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│
Permissive FOV

Pillars

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
Ray casting
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
Shadow casting
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Diamond walls
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
My algorithm
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
Permissive FOV

┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@
Ray casting
┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@
Shadow casting
┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@
Diamond walls
┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@
My algorithm
┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@
Permissive FOV

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
Ray casting
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
Shadow casting
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
Diamond walls
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
My algorithm
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙
Permissive FOV

∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Ray casting
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Shadow casting
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Diamond walls
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
My algorithm
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Permissive FOV

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴
Ray casting
┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴
Shadow casting
┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴
Diamond walls
┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴
My algorithm
┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴
Permissive FOV

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤
Ray casting
─────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
─────────────┤
Shadow casting
──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤
Diamond walls
──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤
My algorithm
──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤
Permissive FOV

+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙++∙+∙∙
∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙
+∙∙∙++∙∙∙+
Ray casting
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
Shadow casting
+∙∙+∙+∙∙+
∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙
+∙∙+∙+∙∙+
Diamond walls
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
++∙+∙+∙++
∙∙∙∙∙@∙∙∙∙∙
++∙+∙+∙++
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
My algorithm
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
Permissive FOV

∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+
Ray casting
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
Shadow casting
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
Diamond walls
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙++∙
∙+++∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙+++∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙++
My algorithm
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
Permissive FOV

∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙++∙++∙+∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙++∙++∙+∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙
Ray casting
∙∙∙++∙∙∙+∙+∙∙∙++∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙++∙+∙+∙++∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙++∙+∙+∙++∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙++∙∙∙+∙+∙∙∙++∙∙∙
Shadow casting
∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙+∙++∙++∙+∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙+∙++∙++∙+∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙
Diamond walls
∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙++∙++∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙++∙++∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│
My algorithm
∙∙∙∙++∙∙∙+∙+∙∙∙++∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙++∙+∙+∙++∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙++∙+∙+∙++∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙++∙∙∙+∙+∙∙∙++∙∙∙│
Permissive FOV

Symmetrical versions

This is a comparison between the symmetrical versions of the algorithms. Ray casting is not included because it cannot be made symmetrical with reasonable efficiency. My algorithm has two symmetrical versions: one that's fully symmetrical and another that's symmetrical except for some walls (i.e. that's symmetrical between monsters except for some passwall monsters).

│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙└┤        │
       ┌┘∙∙│∙└┐       │
Shadow casting
│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │
Diamond walls
│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │
My algorithm (full symmetry)
└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │
My algorithm (partial symmetry)
│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │
Permissive FOV

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
Shadow casting
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙
Diamond walls
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙
My algorithm (full symmetry)
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙
My algorithm (partial symmetry)
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
Permissive FOV

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙
Shadow casting
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙
Diamond walls
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙
My algorithm (full symmetry)
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙
My algorithm (partial symmetry)
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙
Permissive FOV

│   ┌──────────┐
│   │∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐│
└─┬┤∙∙∙∙│     ││
∙∙└┘∙∙∙∙│     │┐∙∙∙∙∙∙∙└───┐ ││
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
Shadow casting
│   ┌──────────┐
│   │∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐│
└─┬┤∙∙∙∙│     ││
∙∙└┘∙∙∙∙│     │┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
Diamond walls
│   ┌──────────┐
│   │∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐│
└─┬┤∙∙∙∙│     ││
∙∙└┘∙∙∙∙│     │┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
My algorithm (full symmetry)
│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
My algorithm (partial symmetry)
│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘
Permissive FOV

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘
Shadow casting
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘
Diamond walls
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│┌┤
└────────┴─
My algorithm (full symmetry)
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴
My algorithm (partial symmetry)
│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘
Permissive FOV

│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
Shadow casting
∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙│
├──────────┤
│∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
Diamond walls
└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├──────────┤
│∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
My algorithm (full symmetry)
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙──────┤
│∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
My algorithm (partial symmetry)
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴
Permissive FOV

────────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
┤∙∙∙∙∙∙┼∙
■∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@
Shadow casting
┌───────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙
∙∙∙∙∙∙┼∙
■∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@
Diamond walls
┌───────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙
∙∙∙∙∙∙┼∙
■∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@
My algorithm (full)
┌───────│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙
∙∙∙∙∙∙┼∙
■∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@
My algorithm (partial)
┌──────│∙∙∙∙∙∙∙│∙∙∙∙∙∙│∙∙∙∙∙∙∙∙
│∙∙∙∙∙│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@
Permissive FOV

┌───────
│∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙
┤∙∙∙┼∙
■∙∙∙∙┼∙@
Shadow casting
┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@
Diamond walls
┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@
My algorithm (full)
┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙
│∙∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@
My algorithm (partial)
┌───────
│∙∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙│∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@
Permissive FOV

┌───────────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
┴─────────+─────────┴
Shadow casting
───────────────────
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
─────────+─────────
Diamond walls
───────────────────
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
─────────+─────────
My algorithm (full symmetry)
┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴─────────+─────────┴
My algorithm (partial symmetry)
┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴─────────+─────────┴
Permissive FOV

─────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
───────+─────┤
Shadow casting
──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤
Diamond walls
──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤
My algorithm (full symmetry)
──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤
My algorithm (partial symmetry)
──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤
Permissive FOV

Performance

Here's a table describing the performance of the algorithms in various scenarios. Higher numbers are better, although what matters is the performance ratio between the algorithms, not the absolute numbers. (The absolute numbers represent the number of executions per second on a single core on my machine.)

MapRay castingShadow casting Diamond wallsMy algorithmPermissive FOV
Empty (20x20) 8360889577868756036912023
Empty (100x100) 3404491048863357686
Empty (r4) 29266737037835327628085947114
Empty (r8) 813121321481115119966021480
Outdoor (20x20) 139177174070941486616317513
Outdoor (100x100) 2496214092548697391689695
Outdoor (r4) 33573841598131664423842052208
Outdoor (r8) 12477820397113329210090627004
Short corridor (120x65)4877243670631951321380137914
Long corridor (120x65) 567062018571432369642012217
Corridor (r4) 54763782619466356148171885724
Corridor (r8) 26967850182739241526997645214
Twisty (120x65) 9284291727664269744904393691
Pillars 1 (120x65) 24500127665851915541613975
Pillars 1 (r4) 30510735853230801821463045589
Pillars 1 (r8) 1066971615671206988514824007
Pillars 2 (r4) 41707553383932876722829863121
Pillars 2 (r8) 19555028852614140813358832876
Room (120x65) 3947839846625094815234430615
Room (r4) 32905841725336496526098361807
Room (r8) 15443933466427613019106246470
Avg. speed factor70%*100%78%53%11%
* Ray casting average speed only counts tests with a limited sight radius (r4 or r8).

  • Empty maps are simply empty space with no obstacles.
  • Outdoor maps are maps with 25% of the space being randomly placed obstacles (wall tiles).
  • R4 and r8 refer to algorithms run with the maximum sight radius set to 4 or 8, while AxB refers to the width and height of the map and implies an unlimited sight radius. The size of the map or sight radius has the largest effect on ray casting, since it must always cast a number of rays proportional to the map size or sight radius.
  • Green cells are at least 75% of the speed of the fastest algorithm. Yellow cells are at least half its speed but less than 75%. Orange cells are at least one third its speed but less than half. Red cells are less than one third.
It seems that I didn't quite reach my goal of having speed on par with the diagonal walls algorithm, but I succeeded in all other goals. My algorithm is only about 2/3rds the speed of the diagonal walls algorithm, but it should be fast enough for almost any game. Furthermore, there is still significant optimization that could be done.

Code

This class, Visibility, defines the interface used by all algorithms.
abstract class Visibility
{
  /// <param name="origin">The location of the monster whose field of view will be calculated.</param>
  /// <param name="rangeLimit">The maximum distance from the origin that tiles will be lit.
  /// If equal to -1, no limit will be applied.
  /// </param>
  public abstract void Compute(LevelPoint origin, int rangeLimit);
}

Ray casting

Here's the code for ray casting, assuming the map is no larger than 65536 tiles across and with error-checking elided. Rather than hard-code any particular method for representing the map, checking for opacity, or computing distances, the code accepts pointers to functions that handle these details.
sealed class RayCastVisibility : Visibility
{
  /// <param name="mapSize">The size of the map.</param>
  /// <param name="blocksLight">A function that accepts the X and Y coordinates of a tile and determines
  /// whether the given tile blocks the passage of light.
  /// </param>
  /// <param name="setVisible">A function that sets a tile to be visible, given its X and Y coordinates.</param>
  /// <param name="getDistance">A function that a pair of X and Y coordinates and returns the distance
  /// between the two points.
  /// </param>
  public RayCastVisibility(Size mapSize, Func<int,int,bool> blocksLight, Action<int,int> setVisible,
                           Func<int,int,int,int,int> getDistance)
  {
    MapSize     = mapSize;
    BlocksLight = blocksLight;
    SetVisible  = setVisible;
    GetDistance = getDistance;
  }

  public override void Compute(LevelPoint origin, int rangeLimit)
  {
    SetVisible(origin.X, origin.Y);
    if(rangeLimit != 0)
    {
      Rectangle area = new Rectangle(0, 0, MapSize.Width, MapSize.Height); // cast to the edge of the map by default
      if(rangeLimit >= 0) // but limit the area to the rectangle containing the sight radius if one was provided
      {
        area.Intersect(new Rectangle(origin.X-rangeLimit, origin.Y-rangeLimit, rangeLimit*2+1, rangeLimit*2+1));
      }
      for(int x=area.Left; x<area.Right; x++) // cast rays towards the top and bottom of the area
      {
        TraceLine(origin, x, area.Top, rangeLimit);
        TraceLine(origin, x, area.Bottom-1, rangeLimit);
      }
      for(int y=area.Top+1; y<area.Bottom-1; y++) // and to the left and right
      {
        TraceLine(origin, area.Left, y, rangeLimit);
        TraceLine(origin, area.Right-1, y, rangeLimit);
      }
    }
  }

  void TraceLine(LevelPoint origin, int x2, int y2, int rangeLimit)
  {
    int xDiff = x2 - origin.X, yDiff = y2 - origin.Y, xLen = Math.Abs(xDiff), yLen = Math.Abs(yDiff);
    int xInc = Math.Sign(xDiff), yInc = Math.Sign(yDiff)<<16, index = (origin.Y<<16) + origin.X;
    if(xLen < yLen) // make sure we walk along the long axis
    {
      Utility.Swap(ref xLen, ref yLen);
      Utility.Swap(ref xInc, ref yInc);
    }
    int errorInc = yLen*2, error = -xLen, errorReset = xLen*2;
    while(--xLen >= 0) // skip the first point (the origin) since it's always visible and should never stop rays
    {
      index += xInc; // advance down the long axis (could be X or Y)
      error += errorInc;
      if(error > 0) { error -= errorReset; index += yInc; }
      int x = index & 0xFFFF, y = index >> 16;
      if(rangeLimit >= 0 && GetDistance(origin.X, origin.Y, x, y) > rangeLimit) break;
      SetVisible(x, y);
      if(BlocksLight(x, y)) break;
    }
  }

  readonly Size MapSize;
  readonly Func<int, int, bool> BlocksLight;
  readonly Func<int, int, int, int, int> GetDistance;
  readonly Action<int, int> SetVisible;
}

Shadow casting

Here's the code for basic, asymmetrical shadow casting with square tiles. See the "NOTE:" comment for a simple change you can make if you want the algorithm to be symmetrical.
sealed class ShadowCastVisibility : Visibility
{
  /// <param name="blocksLight">A function that accepts the X and Y coordinates of a tile and determines whether the
  /// given tile blocks the passage of light. The function must be able to accept coordinates that are out of bounds.
  /// </param>
  /// <param name="setVisible">A function that sets a tile to be visible, given its X and Y coordinates. The function
  /// must ignore coordinates that are out of bounds.
  /// </param>
  /// <param name="getDistance">A function that takes the X and Y coordinate of a point where X >= 0,
  /// Y >= 0, and X >= Y, and returns the distance from the point to the origin.
  /// </param>
  public ShadowCastVisibility(Func<int, int, bool> blocksLight, Action<int, int> setVisible,
                              Func<int,int,int> getDistance)
  {
    BlocksLight = blocksLight;
    GetDistance = getDistance;
    SetVisible  = setVisible;
  }

  public override void Compute(LevelPoint origin, int rangeLimit)
  {
    SetVisible(origin.X, origin.Y);
    for(uint octant=0; octant<8; octant++) Compute(octant, origin, rangeLimit, 1, new Slope(1, 1), new Slope(0, 1));
  }

  struct Slope // represents the slope Y/X as a rational number
  {
    public Slope(int y, int x) { Y=y; X=x; }
    public readonly int Y, X;
  }

  void Compute(uint octant, LevelPoint origin, int rangeLimit, int x, Slope top, Slope bottom)
  {
    for(; (uint)x <= (uint)rangeLimit; x++) // rangeLimit < 0 || x <= rangeLimit
    {
      // compute the Y coordinates where the top vector leaves the column (on the right) and where the bottom vector
      // enters the column (on the left). this equals (x+0.5)*top+0.5 and (x-0.5)*bottom+0.5 respectively, which can
      // be computed like (x+0.5)*top+0.5 = (2(x+0.5)*top+1)/2 = ((2x+1)*top+1)/2 to avoid floating point math
      int topY = top.X == 1 ? x : ((x*2+1) * top.Y + top.X - 1) / (top.X*2); // the rounding is a bit tricky, though
      int bottomY = bottom.Y == 0 ? 0 : ((x*2-1) * bottom.Y + bottom.X) / (bottom.X*2);
      
      int wasOpaque = -1; // 0:false, 1:true, -1:not applicable
      for(int y=topY; y >= bottomY; y--)
      {
        int tx = origin.X, ty = origin.Y;
        switch(octant) // translate local coordinates to map coordinates
        {
          case 0: tx += x; ty -= y; break;
          case 1: tx += y; ty -= x; break;
          case 2: tx -= y; ty -= x; break;
          case 3: tx -= x; ty -= y; break;
          case 4: tx -= x; ty += y; break;
          case 5: tx -= y; ty += x; break;
          case 6: tx += y; ty += x; break;
          case 7: tx += x; ty += y; break;
        }

        bool inRange = rangeLimit < 0 || GetDistance(tx, ty) <= rangeLimit;
        if(inRange) SetVisible(tx, ty);
        // NOTE: use the next line instead if you want the algorithm to be symmetrical
        // if(inRange && (y != topY || top.Y*x >= top.X*y) && (y != bottomY || bottom.Y*x <= bottom.X*y)) SetVisible(tx, ty);

        bool isOpaque = !inRange || BlocksLight(tx, ty);
        if(x != rangeLimit)
        {
          if(isOpaque) 
          {            
            if(wasOpaque == 0) // if we found a transition from clear to opaque, this sector is done in this column, so
            {                  // adjust the bottom vector upwards and continue processing it in the next column.
              Slope newBottom = new Slope(y*2+1, x*2-1); // (x*2-1, y*2+1) is a vector to the top-left of the opaque tile
              if(!inRange || y == bottomY) { bottom = newBottom; break; } // don't recurse unless we have to
              else Compute(octant, origin, rangeLimit, x+1, top, newBottom);
            }
            wasOpaque = 1;
          }
          else // adjust top vector downwards and continue if we found a transition from opaque to clear
          {    // (x*2+1, y*2+1) is the top-right corner of the clear tile (i.e. the bottom-right of the opaque tile)
            if(wasOpaque > 0) top = new Slope(y*2+1, x*2+1);
            wasOpaque = 0;
          }
        }
      }

      if(wasOpaque != 0) break; // if the column ended in a clear tile, continue processing the current sector
    }
  }

  readonly Func<int, int, bool> BlocksLight;
  readonly Func<int, int, int> GetDistance;
  readonly Action<int, int> SetVisible;
}

Diamond walls

Here is code to implement the diamond walls algorithm. As before, see the "NOTE:" comment for a simple change that will make the algorithm symmetrical.
sealed class DiamondWallsVisibility : Visibility
{
  /// <param name="blocksLight">A function that accepts the X and Y coordinates of a tile and determines
  /// whether the given tile blocks the passage of light.
  /// </param>
  /// <param name="setVisible">A function that sets a tile to be visible, given its X and Y coordinates.</param>
  /// <param name="getDistance">A function that takes the X and Y coordinate of a point where X >= 0,
  /// Y >= 0, and X >= Y, and returns the distance from the point to the origin (0,0).
  /// </param>
  public DiamondWallsVisibility(Func<int,int,bool> blocksLight, Action<int,int> setVisible,
                                Func<int,int,int> getDistance)
  {
    _blocksLight = blocksLight;
    GetDistance  = getDistance;
    SetVisible   = setVisible;
  }

  public override void Compute(LevelPoint origin, int rangeLimit)
  {
    SetVisible(origin.X, origin.Y);
    for(uint octant=0; octant<8; octant++) Compute(octant, origin, rangeLimit, 1, new Slope(1, 1), new Slope(0, 1));
  }

  struct Slope // represents the slope Y/X as a rational number
  {
    public Slope(int y, int x) { Y=y; X=x; }
    public bool Greater(int y, int x) { return Y*x > X*y; } // this > y/x
    public bool GreaterOrEqual(int y, int x) { return Y*x >= X*y; } // this >= y/x
    public bool LessOrEqual(int y, int x) { return Y*x <= X*y; } // this <= y/x
    public readonly int Y, X;
  }

  void Compute(uint octant, LevelPoint origin, int rangeLimit, int x, Slope top, Slope bottom)
  {
    for(; (uint)x <= (uint)rangeLimit; x++) // rangeLimit < 0 || x <= rangeLimit
    {
      int topY;
      if(top.X == 1)
      {
        topY = x;
      }
      else
      {
        topY = ((x*2-1) * top.Y + top.X) / (top.X*2); // get the tile that the top vector enters from the left
        int ay = (topY*2+1) * top.X;
        if(BlocksLight(x, topY, octant, origin)) // if the top tile is a wall...
        {
          if(top.GreaterOrEqual(ay, x*2)) topY++; // but the top vector misses the wall and passes into the tile above, move up
        }
        else // the top tile is not a wall
        {
          if(top.Greater(ay, x*2+1)) topY++; // so if the top vector passes into the tile above, move up
        }
      }

      int bottomY = bottom.Y == 0 ? 0 : ((x*2-1) * bottom.Y + bottom.X) / (bottom.X*2);
      int wasOpaque = -1; // 0:false, 1:true, -1:not applicable
      for(int y=topY; y >= bottomY; y--)
      {
        int tx = origin.X, ty = origin.Y;
        switch(octant) // translate local coordinates to map coordinates
        {
          case 0: tx += x; ty -= y; break;
          case 1: tx += y; ty -= x; break;
          case 2: tx -= y; ty -= x; break;
          case 3: tx -= x; ty -= y; break;
          case 4: tx -= x; ty += y; break;
          case 5: tx -= y; ty += x; break;
          case 6: tx += y; ty += x; break;
          case 7: tx += x; ty += y; break;
        }

        bool inRange = rangeLimit < 0 || GetDistance(tx, ty) <= rangeLimit;
        // NOTE: use the following line instead to make the algorithm symmetrical
        // if(inRange && (y != topY || top.GreaterOrEqual(y, x)) && (y != bottomY || bottom.LessOrEqual(y, x))) SetVisible(tx, ty);
        if(inRange) SetVisible(tx, ty);

        bool isOpaque = !inRange || _blocksLight(tx, ty);
        // if y == topY or y == bottomY, make sure the sector actually intersects the wall tile. if not, don't consider
        // it opaque to prevent the code below from moving the top vector up or the bottom vector down
        if(isOpaque &&
           (y == topY && top.LessOrEqual(y*2-1, x*2) && !BlocksLight(x, y-1, octant, origin) ||
            y == bottomY && bottom.GreaterOrEqual(y*2+1, x*2) && !BlocksLight(x, y+1, octant, origin)))
        {
          isOpaque = false;
        }

        if(x != rangeLimit)
        {
          if(isOpaque)
          {
            if(wasOpaque == 0) // if we found a transition from clear to opaque, this sector is done in this column, so
            {                  // adjust the bottom vector upwards and continue processing it in the next column.
              // (x*2-1, y*2+1) is a vector to the top-left corner of the opaque block
              if(!inRange || y == bottomY) { bottom = new Slope(y*2+1, x*2); break; } // don't recurse unless necessary
              else Compute(octant, origin, rangeLimit, x+1, top, new Slope(y*2+1, x*2));
            }
            wasOpaque = 1;
          }
          else // adjust the top vector downwards and continue if we found a transition from opaque to clear
          {    // (x*2+1, y*2+1) is the top-right corner of the clear tile (i.e. the bottom-right of the opaque tile)
            if(wasOpaque > 0) top = new Slope(y*2+1, x*2);
            wasOpaque = 0;
          }
        }
      }

      if(wasOpaque != 0) break; // if the column ended in a clear tile, continue processing the current sector
    }
  }

  bool BlocksLight(int x, int y, uint octant, LevelPoint origin)
  {
    int nx = origin.X, ny = origin.Y;
    switch(octant)
    {
      case 0: nx += x; ny -= y; break;
      case 1: nx += y; ny -= x; break;
      case 2: nx -= y; ny -= x; break;
      case 3: nx -= x; ny -= y; break;
      case 4: nx -= x; ny += y; break;
      case 5: nx -= y; ny += x; break;
      case 6: nx += y; ny += x; break;
      case 7: nx += x; ny += y; break;
    }
    return _blocksLight(nx, ny);
  }

  readonly Func<int, int, bool> _blocksLight;
  readonly Func<int, int, int> GetDistance;
  readonly Action<int, int> SetVisible;
}

Permissive field of view

Here is code to implement the permissive field of view algorithm. This code was adapted from a demo by Jonathon Duerig. The permissive field of view algorithm is always symmetrical.
sealed class PermissiveVisibility : Visibility
{
  /// <param name="blocksLight">A function that accepts the X and Y coordinates of a tile and determines
  /// whether the given tile blocks the passage of light.
  /// </param>
  /// <param name="setVisible">A function that sets a tile to be visible, given its X and Y coordinates.</param>
  /// <param name="getDistance">A function that takes the X and Y coordinate of a point where X >= 0,
  /// Y >= 0, and X >= Y, and returns the distance from the point to the origin (0,0).
  /// </param>
  public PermissiveVisibility(Func<int,int,bool> blocksLight, Action<int,int> setVisible,
                              Func<int,int,int> getDistance)
  {
    BlocksLight = blocksLight;
    SetVisible  = setVisible;
    GetDistance = getDistance;
  }

  public override void Compute(LevelPoint origin, int rangeLimit)
  {
    source = new Offset(origin.X, origin.Y);
    this.rangeLimit = rangeLimit;
    for(int q=0; q<4; q++)
    {
      quadrant.x = (short)(q == 0 || q == 3 ? 1 : -1);
      quadrant.y = (short)(q < 2 ? 1 : -1);
      ComputeQuadrant();
    }
  }

  sealed class Bump
  {
    public Bump parent;
    public Offset location;
  }

  struct Field
  {
    public Bump steepBump, shallowBump;
    public Line steep, shallow;
  }

  struct Line
  {
    public Line(Offset near, Offset far) { this.near = near; this.far = far; }

    public Offset near, far;

    public bool isBelow(Offset point)
    {
      return relativeSlope(point) > 0;
    }

    public bool isBelowOrContains(Offset point)
    {
      return relativeSlope(point) >= 0;
    }

    public bool isAbove(Offset point)
    {
      return relativeSlope(point) < 0;
    }

    public bool isAboveOrContains(Offset point)
    {
      return relativeSlope(point) <= 0;
    }

    public bool doesContain(Offset point)
    {
      return relativeSlope(point) == 0;
    }

    // negative if the line is above the point.
    // positive if the line is below the point.
    // 0 if the line is on the point.
    public int relativeSlope(Offset point)
    {
      return (far.y - near.y)*(far.x - point.x) - (far.y - point.y)*(far.x - near.x);
    }
  }

  struct Offset
  {
    public Offset(int x, int y) { this.x = (short)x; this.y = (short)y; }
    public short x, y;
  }

  void ComputeQuadrant()
  {
    const int Infinity = short.MaxValue;
    List<Bump> steepBumps = new List<Bump>(), shallowBumps = new List<Bump>();
    LinkedList<Field> activeFields = new LinkedList<Field>();
    activeFields.AddLast(new Field() { steep = new Line(new Offset(1, 0), new Offset(0, Infinity)), shallow = new Line(new Offset(0, 1), new Offset(Infinity, 0)) });

    Offset dest = new Offset();
    actIsBlocked(dest);
    for(int i=1; i<Infinity && activeFields.Count != 0; i++)
    {
      LinkedListNode<Field> current = activeFields.First;
      for(int j=0; j <= i; j++)
      {
        dest.x = (short)(i-j);
        dest.y = (short)j;
        current = visitSquare(dest, current, steepBumps, shallowBumps, activeFields);
      }
    }
  }

  bool actIsBlocked(Offset pos)
  {
    if(rangeLimit >= 0 && GetDistance(Math.Max(pos.x, pos.y), Math.Min(pos.x, pos.y)) > rangeLimit) return true;
    int x = pos.x*quadrant.x + source.x, y = pos.y*quadrant.y + source.y;
    SetVisible(x, y);
    return BlocksLight(x, y);
  }

  LinkedListNode<Field> visitSquare(Offset dest, LinkedListNode<Field> currentField, List<Bump> steepBumps, List<Bump> shallowBumps, LinkedList<Field> activeFields)
  {
    Offset topLeft = new Offset(dest.x, dest.y+1), bottomRight = new Offset(dest.x+1, dest.y);
    while(currentField != null && currentField.Value.steep.isBelowOrContains(bottomRight)) currentField = currentField.Next;
    if(currentField == null || currentField.Value.shallow.isAboveOrContains(topLeft) || !actIsBlocked(dest)) return currentField;

    if(currentField.Value.shallow.isAbove(bottomRight) && currentField.Value.steep.isBelow(topLeft))
    {
      LinkedListNode<Field> next = currentField.Next;
      activeFields.Remove(currentField);
      return next;
    }
    else if(currentField.Value.shallow.isAbove(bottomRight))
    {
      addShallowBump(topLeft, currentField, shallowBumps);
      return checkField(currentField, activeFields);
    }
    else if(currentField.Value.steep.isBelow(topLeft))
    {
      addSteepBump(bottomRight, currentField, steepBumps);
      return checkField(currentField, activeFields);
    }
    else
    {
      LinkedListNode<Field> steeper = currentField, shallower = activeFields.AddBefore(currentField, currentField.Value);
      addSteepBump(bottomRight, shallower, steepBumps);
      checkField(shallower, activeFields);
      addShallowBump(topLeft, steeper, shallowBumps);
      return checkField(steeper, activeFields);
    }
  }
  
  static void addShallowBump(Offset point, LinkedListNode<Field> currentField, List<Bump> shallowBumps)
  {
    Field value = currentField.Value;
    value.shallow.far = point;
    value.shallowBump = new Bump() { location = point, parent = value.shallowBump };
    shallowBumps.Add(value.shallowBump);

    Bump currentBump = value.steepBump;
    while(currentBump != null)
    {
      if(value.shallow.isAbove(currentBump.location)) value.shallow.near = currentBump.location;
      currentBump = currentBump.parent;
    }
    currentField.Value = value;
  }

  static void addSteepBump(Offset point, LinkedListNode<Field> currentField, List<Bump> steepBumps)
  {
    Field value = currentField.Value;
    value.steep.far = point;
    value.steepBump = new Bump() { location = point, parent = value.steepBump };
    steepBumps.Add(value.steepBump);
    // Now look through the list of shallow bumps and see if any of them are below the line.
    for(Bump currentBump = value.shallowBump; currentBump != null; currentBump = currentBump.parent)
    {
      if (value.steep.isBelow(currentBump.location)) value.steep.near = currentBump.location;
    }
    currentField.Value = value;
  }

  static LinkedListNode<Field> checkField(LinkedListNode<Field> currentField, LinkedList<Field> activeFields)
  {
    LinkedListNode<Field> result = currentField;
    if(currentField.Value.shallow.doesContain(currentField.Value.steep.near) &&
       currentField.Value.shallow.doesContain(currentField.Value.steep.far) &&
       (currentField.Value.shallow.doesContain(new Offset(0, 1)) || currentField.Value.shallow.doesContain(new Offset(1, 0))))
    {
      result = currentField.Next;
      activeFields.Remove(currentField);
    }
    return result;
  }

  readonly Func<int, int, bool> BlocksLight;
  readonly Func<int, int, int> GetDistance;
  readonly Action<int, int> SetVisible;

  Offset source, quadrant;
  int rangeLimit;
}

My algorithm

Here the code to implement my own visibility algorithm. It's long, but it's mostly comments. See the "NOTE:" comments for changes that can be made to make the algorithm mostly or fully symmetrical. Although it's fairly well optimized, there is still a significant improvement that could be made. If the map stored a bit mask for each tile indicating whether each of the corners was beveled, most of the calls to BlocksLight could be removed.
sealed class MyVisibility : Visibility
{
  /// <param name="blocksLight">A function that accepts the X and Y coordinates of a tile and determines whether the
  /// given tile blocks the passage of light. The function must be able to accept coordinates that are out of bounds.
  /// </param>
  /// <param name="setVisible">A function that sets a tile to be visible, given its X and Y coordinates. The function
  /// must ignore coordinates that are out of bounds.
  /// </param>
  /// <param name="getDistance">A function that takes the X and Y coordinate of a point where X >= 0,
  /// Y >= 0, and X >= Y, and returns the distance from the point to the origin (0,0).
  /// </param>
  public MyVisibility(Func<int, int, bool> blocksLight, Action<int, int> setVisible, Func<int, int, int> getDistance)
  {
    _blocksLight = blocksLight;
    GetDistance  = getDistance;
    _setVisible  = setVisible;
  }

  public override void Compute(LevelPoint origin, int rangeLimit)
  {
    _setVisible(origin.X, origin.Y);
    for(uint octant=0; octant<8; octant++) Compute(octant, origin, rangeLimit, 1, new Slope(1, 1), new Slope(0, 1));
  }

  struct Slope // represents the slope Y/X as a rational number
  {
    public Slope(uint y, uint x) { Y = y; X = x; }

    public bool Greater(uint y, uint x) { return Y*x > X*y; } // this > y/x
    public bool GreaterOrEqual(uint y, uint x) { return Y*x >= X*y; } // this >= y/x
    public bool Less(uint y, uint x) { return Y*x < X*y; } // this < y/x
    //public bool LessOrEqual(uint y, uint x) { return Y*x <= X*y; } // this <= y/x

    public readonly uint X, Y;
  }

  void Compute(uint octant, LevelPoint origin, int rangeLimit, uint x, Slope top, Slope bottom)
  {
    // throughout this function there are references to various parts of tiles. a tile's coordinates refer to its
    // center, and the following diagram shows the parts of the tile and the vectors from the origin that pass through
    // those parts. given a part of a tile with vector u, a vector v passes above it if v > u and below it if v < u
    //    g         center:        y / x
    // a------b   a top left:      (y*2+1) / (x*2-1)   i inner top left:      (y*4+1) / (x*4-1)
    // |  /\  |   b top right:     (y*2+1) / (x*2+1)   j inner top right:     (y*4+1) / (x*4+1)
    // |i/__\j|   c bottom left:   (y*2-1) / (x*2-1)   k inner bottom left:   (y*4-1) / (x*4-1)
    //e|/|  |\|f  d bottom right:  (y*2-1) / (x*2+1)   m inner bottom right:  (y*4-1) / (x*4+1)
    // |\|__|/|   e middle left:   (y*2) / (x*2-1)
    // |k\  /m|   f middle right:  (y*2) / (x*2+1)     a-d are the corners of the tile
    // |  \/  |   g top center:    (y*2+1) / (x*2)     e-h are the corners of the inner (wall) diamond
    // c------d   h bottom center: (y*2-1) / (x*2)     i-m are the corners of the inner square (1/2 tile width)
    //    h
    for(; x <= (uint)rangeLimit; x++) // (x <= (uint)rangeLimit) == (rangeLimit < 0 || x <= rangeLimit)
    {
      // compute the Y coordinates of the top and bottom of the sector. we maintain that top > bottom
      uint topY;
      if(top.X == 1) // if top == ?/1 then it must be 1/1 because 0/1 < top <= 1/1. this is special-cased because top
      {              // starts at 1/1 and remains 1/1 as long as it doesn't hit anything, so it's a common case
        topY = x;
      }
      else // top < 1
      {
        // get the tile that the top vector enters from the left. since our coordinates refer to the center of the
        // tile, this is (x-0.5)*top+0.5, which can be computed as (x-0.5)*top+0.5 = (2(x+0.5)*top+1)/2 =
        // ((2x+1)*top+1)/2. since top == a/b, this is ((2x+1)*a+b)/2b. if it enters a tile at one of the left
        // corners, it will round up, so it'll enter from the bottom-left and never the top-left
        topY = ((x*2-1) * top.Y + top.X) / (top.X*2); // the Y coordinate of the tile entered from the left
        // now it's possible that the vector passes from the left side of the tile up into the tile above before
        // exiting from the right side of this column. so we may need to increment topY
        if(BlocksLight(x, topY, octant, origin)) // if the tile blocks light (i.e. is a wall)...
        {
          // if the tile entered from the left blocks light, whether it passes into the tile above depends on the shape
          // of the wall tile as well as the angle of the vector. if the tile has does not have a beveled top-left
          // corner, then it is blocked. the corner is beveled if the tiles above and to the left are not walls. we can
          // ignore the tile to the left because if it was a wall tile, the top vector must have entered this tile from
          // the bottom-left corner, in which case it can't possibly enter the tile above.
          //
          // otherwise, with a beveled top-left corner, the slope of the vector must be greater than or equal to the
          // slope of the vector to the top center of the tile (x*2, topY*2+1) in order for it to miss the wall and
          // pass into the tile above
          if(top.GreaterOrEqual(topY*2+1, x*2) && !BlocksLight(x, topY+1, octant, origin)) topY++;
        }
        else // the tile doesn't block light
        {
          // since this tile doesn't block light, there's nothing to stop it from passing into the tile above, and it
          // does so if the vector is greater than the vector for the bottom-right corner of the tile above. however,
          // there is one additional consideration. later code in this method assumes that if a tile blocks light then
          // it must be visible, so if the tile above blocks light we have to make sure the light actually impacts the
          // wall shape. now there are three cases: 1) the tile above is clear, in which case the vector must be above
          // the bottom-right corner of the tile above, 2) the tile above blocks light and does not have a beveled
          // bottom-right corner, in which case the vector must be above the bottom-right corner, and 3) the tile above
          // blocks light and does have a beveled bottom-right corner, in which case the vector must be above the
          // bottom center of the tile above (i.e. the corner of the beveled edge).
          // 
          // now it's possible to merge 1 and 2 into a single check, and we get the following: if the tile above and to
          // the right is a wall, then the vector must be above the bottom-right corner. otherwise, the vector must be
          // above the bottom center. this works because if the tile above and to the right is a wall, then there are
          // two cases: 1) the tile above is also a wall, in which case we must check against the bottom-right corner,
          // or 2) the tile above is not a wall, in which case the vector passes into it if it's above the bottom-right
          // corner. so either way we use the bottom-right corner in that case. now, if the tile above and to the right
          // is not a wall, then we again have two cases: 1) the tile above is a wall with a beveled edge, in which
          // case we must check against the bottom center, or 2) the tile above is not a wall, in which case it will
          // only be visible if light passes through the inner square, and the inner square is guaranteed to be no
          // larger than a wall diamond, so if it wouldn't pass through a wall diamond then it can't be visible, so
          // there's no point in incrementing topY even if light passes through the corner of the tile above. so we
          // might as well use the bottom center for both cases.
          uint ax = x*2; // center
          if(BlocksLight(x+1, topY+1, octant, origin)) ax++; // use bottom-right if the tile above and right is a wall
          if(top.Greater(topY*2+1, ax)) topY++;
        }
      }

      uint bottomY;
      if(bottom.Y == 0) // if bottom == 0/?, then it's hitting the tile at Y=0 dead center. this is special-cased because
      {                 // bottom.Y starts at zero and remains zero as long as it doesn't hit anything, so it's common
        bottomY = 0;
      }
      else // bottom > 0
      {
        bottomY = ((x*2-1) * bottom.Y + bottom.X) / (bottom.X*2); // the tile that the bottom vector enters from the left
        // code below assumes that if a tile is a wall then it's visible, so if the tile contains a wall we have to
        // ensure that the bottom vector actually hits the wall shape. it misses the wall shape if the top-left corner
        // is beveled and bottom >= (bottomY*2+1)/(x*2). finally, the top-left corner is beveled if the tiles to the
        // left and above are clear. we can assume the tile to the left is clear because otherwise the bottom vector
        // would be greater, so we only have to check above
        if(bottom.GreaterOrEqual(bottomY*2+1, x*2) && BlocksLight(x, bottomY, octant, origin) &&
           !BlocksLight(x, bottomY+1, octant, origin))
        {
          bottomY++;
        }
      }

      // go through the tiles in the column now that we know which ones could possibly be visible
      int wasOpaque = -1; // 0:false, 1:true, -1:not applicable
      for(uint y = topY; (int)y >= (int)bottomY; y--) // use a signed comparison because y can wrap around when decremented
      {
        if(rangeLimit < 0 || GetDistance((int)x, (int)y) <= rangeLimit) // skip the tile if it's out of visual range
        {
          bool isOpaque = BlocksLight(x, y, octant, origin);
          // every tile where topY > y > bottomY is guaranteed to be visible. also, the code that initializes topY and
          // bottomY guarantees that if the tile is opaque then it's visible. so we only have to do extra work for the
          // case where the tile is clear and y == topY or y == bottomY. if y == topY then we have to make sure that
          // the top vector is above the bottom-right corner of the inner square. if y == bottomY then we have to make
          // sure that the bottom vector is below the top-left corner of the inner square
          bool isVisible =
            isOpaque || ((y != topY || top.Greater(y*4-1, x*4+1)) && (y != bottomY || bottom.Less(y*4+1, x*4-1)));
          // NOTE: if you want the algorithm to be either fully or mostly symmetrical, replace the line above with the
          // following line (and uncomment the Slope.LessOrEqual method). the line ensures that a clear tile is visible
          // only if there's an unobstructed line to its center. if you want it to be fully symmetrical, also remove
          // the "isOpaque ||" part and see NOTE comments further down
          // bool isVisible = isOpaque || ((y != topY || top.GreaterOrEqual(y, x)) && (y != bottomY || bottom.LessOrEqual(y, x)));
          if(isVisible) SetVisible(x, y, octant, origin);

          // if we found a transition from clear to opaque or vice versa, adjust the top and bottom vectors
          if(x != rangeLimit) // but don't bother adjusting them if this is the last column anyway
          {
            if(isOpaque)
            {
              if(wasOpaque == 0) // if we found a transition from clear to opaque, this sector is done in this column,
              {                  // so adjust the bottom vector upward and continue processing it in the next column
                // if the opaque tile has a beveled top-left corner, move the bottom vector up to the top center.
                // otherwise, move it up to the top left. the corner is beveled if the tiles above and to the left are
                // clear. we can assume the tile to the left is clear because otherwise the vector would be higher, so
                // we only have to check the tile above
                uint nx = x*2, ny = y*2+1; // top center by default
                // NOTE: if you're using full symmetry and want more expansive walls (recommended), comment out the next line
                if(BlocksLight(x, y+1, octant, origin)) nx--; // top left if the corner is not beveled
                if(top.Greater(ny, nx)) // we have to maintain the invariant that top > bottom, so the new sector
                {                       // created by adjusting the bottom is only valid if that's the case
                  // if we're at the bottom of the column, then just adjust the current sector rather than recursing
                  // since there's no chance that this sector can be split in two by a later transition back to clear
                  if(y == bottomY) { bottom = new Slope(ny, nx); break; } // don't recurse unless necessary
                  else Compute(octant, origin, rangeLimit, x+1, top, new Slope(ny, nx));
                }
                else // the new bottom is greater than or equal to the top, so the new sector is empty and we'll ignore
                {    // it. if we're at the bottom of the column, we'd normally adjust the current sector rather than
                  if(y == bottomY) return; // recursing, so that invalidates the current sector and we're done
                }
              }
              wasOpaque = 1;
            }
            else
            {
              if(wasOpaque > 0) // if we found a transition from opaque to clear, adjust the top vector downwards
              {
                // if the opaque tile has a beveled bottom-right corner, move the top vector down to the bottom center.
                // otherwise, move it down to the bottom right. the corner is beveled if the tiles below and to the right
                // are clear. we know the tile below is clear because that's the current tile, so just check to the right
                uint nx = x*2, ny = y*2+1; // the bottom of the opaque tile (oy*2-1) equals the top of this tile (y*2+1)
                // NOTE: if you're using full symmetry and want more expansive walls (recommended), comment out the next line
                if(BlocksLight(x+1, y+1, octant, origin)) nx++; // check the right of the opaque tile (y+1), not this one
                // we have to maintain the invariant that top > bottom. if not, the sector is empty and we're done
                if(bottom.GreaterOrEqual(ny, nx)) return;
                top = new Slope(ny, nx);
              }
              wasOpaque = 0;
            }
          }
        }
      }

      // if the column didn't end in a clear tile, then there's no reason to continue processing the current sector
      // because that means either 1) wasOpaque == -1, implying that the sector is empty or at its range limit, or 2)
      // wasOpaque == 1, implying that we found a transition from clear to opaque and we recursed and we never found
      // a transition back to clear, so there's nothing else for us to do that the recursive method hasn't already. (if
      // we didn't recurse (because y == bottomY), it would have executed a break, leaving wasOpaque equal to 0.)
      if(wasOpaque != 0) break;
    }
  }

  // NOTE: the code duplication between BlocksLight and SetVisible is for performance. don't refactor the octant
  // translation out unless you don't mind an 18% drop in speed
  bool BlocksLight(uint x, uint y, uint octant, LevelPoint origin)
  {
    uint nx = origin.X, ny = origin.Y;
    switch(octant)
    {
      case 0: nx += x; ny -= y; break;
      case 1: nx += y; ny -= x; break;
      case 2: nx -= y; ny -= x; break;
      case 3: nx -= x; ny -= y; break;
      case 4: nx -= x; ny += y; break;
      case 5: nx -= y; ny += x; break;
      case 6: nx += y; ny += x; break;
      case 7: nx += x; ny += y; break;
    }
    return _blocksLight((int)nx, (int)ny);
  }

  void SetVisible(uint x, uint y, uint octant, LevelPoint origin)
  {
    uint nx = origin.X, ny = origin.Y;
    switch(octant)
    {
      case 0: nx += x; ny -= y; break;
      case 1: nx += y; ny -= x; break;
      case 2: nx -= y; ny -= x; break;
      case 3: nx -= x; ny -= y; break;
      case 4: nx -= x; ny += y; break;
      case 5: nx -= y; ny += x; break;
      case 6: nx += y; ny += x; break;
      case 7: nx += x; ny += y; break;
    }
    _setVisible((int)nx, (int)ny);
  }

  readonly Func<int, int, bool> _blocksLight;
  readonly Func<int, int, int> GetDistance;
  readonly Action<int, int> _setVisible;
}

Further Possibilities

Here are some ideas for additional lighting possibilities that can be implemented on top of any of the above FOV algorithms.

NetHack-style lighting

In NetHack, the player has an unlimited sight radius, but outside of a certain minimum distance the player can only see tiles if they're "lit". An example is below. The player is in a dark room but can see the adjacent tiles due to the player's minimum sight radius of 1. The player can also see some tiles from the room down the hall because they're lit and unoccluded.

┌──────┐                ┌─────┐
│∙∙∙∙∙∙│       ┌───┐    │∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙@∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙│       └───┘    │∙∙∙∙∙│
└──────┘                └─────┘
NetHack-style lighting
┌──────┐                ┌─────┐
│∙∙∙∙∙∙│       ┌───┐    │∙∙∙∙∙│
│∙∙∙∙∙∙│       │@∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙│       └───┘    │∙∙∙∙∙
└──────┘                └─────┘
Occlusion rules remain in place
┌──────┐                ┌─────┐
│∙∙∙∙∙∙│       ┌───┐    │∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙│       └───┘    │@∙∙∙∙│
└──────┘                └─────┘

As you can see, lit tiles aren't actually light sources, so they don't illuminate other tiles. Instead, a lit tile is a tile that's been illuminated by some light source. With one possible exception (described below), only a small change to a field-of-view algorithm is needed to obtain NetHack-style lighting. First, have both a minimum and maximum sight radius and a way to tell if a tile is lit. The minimum radius is the radius of the player's carried light source (or "miner's hat"), and the maximum is how far the player can see even under perfect conditions. (The maximum may be infinite, since most roguelike maps tend to be fairly small compared to the limits of humanoid vision.) Whether a tile is lit is usually decided during dungeon generation. Second, run the algorithm out to the maximum light radius and set a tile to be visible if it would normally be visible and either it's within the minimum light radius or it's lit.

There's one consideration that isn't addressed by the above. If a floor tile is lit, then it doesn't matter which direction it's viewed from, but if a lit tile is a wall, then it does matter. For instance, if a room is lit then it only makes sense for the wall tiles to appear lit if you can see the side facing into the room. If you dig a tunnel to the back side of the wall, it should not appear lit because light from the room cannot reach the other side. There are several ways this can be dealt with:

  • Don't allow it. If the player cannot dig through walls in your game, then you simply need to avoid generating walls that are supposed to be lit on one side but not another.
  • Don't show lit walls as lit unless the player is in the room. This avoids the problem without restricting the player but prevents the player from looking down a hallway into a lit room and seeing the back wall lit. This still provides the main benefit of lit tiles, which is to let the player know about items, monsters, and rooms from a distance, but it could be considered a visual artifact.
  • Use a simple heuristic. A wall tile is considered lit by the FOV algorithm only if the previous tile was considered lit. This has the effect that the FOV algorithm must pass over a lit floor tile before a wall behind it can be illuminated. (This consideration includes the floor tile the player is standing on.) I think this would work in every reasonable case, but perhaps your game is unreasonable.
  • Instead of just having wall tiles, have four different types of wall tiles, indicating the direction the wall is facing, with the assumption that a lit wall tile is lit from the direction it's facing. (Alternately, have a bitmask, allowing a single wall tile to face multiple directions.) Then, a wall is only considered lit by the FOV algorithm if it encounters the wall from the correct direction. This enables the additional feature that walls might not look like walls unless the player sees them from the correct side, so if the player digs a tunnel to the back of a wall, it will not appear like a wall unless the player has already seen it from the other side.
  • Instead of just tracking whether a wall tile is lit, track the direction from which it's lit or have four lit flags, one for each direction. Then, the FOV algorithm only considers a wall tile lit if it encounters the wall from a lit direction. This is similar to the previous suggestion except that a wall tile will appear to be a wall regardless of which side it's seen from (unless you implement that some other way), and it works better if light sources can move or be created or destroyed.

While the above method works, it's not especially efficient. While this doesn't matter if only the player has decent vision, if monsters can see equally well and many monsters are being simulated on each turn, it would be preferable if we didn't have to run the FOV algorithm out to an infinite distance in all directions for all monsters. Some ideas for optimizing NetHack-style lighting follow.

  1. First, make use of the fact that in NetHack, all (or almost all) lit rooms are convex, and a key property of a convex region is that if you're within it you can see every part of it. So as a first step, you can check if the player is within a lit, convex room and if so set all tiles within the room to be visible. This takes care of the very common case in which the only visible lit tiles are in the same room as the player.
  2. With NetHack-style lighting, the minimum sight radius is usually 1 and all FOV algorithms work identically at a radius of 1, setting all adjacent tiles to be visible. Whenever the minimum sight radius is 1, you can special case it to simply set all adjacent tiles to be visible.
  3. With #1 done, we need only concern ourselves with lit tiles outside the player's current room (and whatever tiles would be exposed by the minimum sight radius). The map should have a list of the lit areas and their bounding boxes. At this point, you can take one of two approaches.
    1. Run the FOV algorithm once for the minimum sight radius. Then run it again for each lit area besides the one the player is currently in, initializing it so that it only scans in the direction of the lit area. If you have more than 5-15 lit areas, option b may be more efficient.
    2. If the minimum sight radius is 1, set each adjacent tile to be visible. Then have an array of eight integers that represent the maximum sight radius that the FOV algorithm will need to scan in each of the eight octants. Initialize each element with the minimum sight radius if it's greater than 1, or with zero otherwise (since a minimum sight radius of 1 was already handled). Step through each lit area besides the one the player is currently in, determine which octants it's in, and increase the distances in those octants to the distance to the furthest part of the lit room. Then run the FOV algorithm once for each octant, using the octant's computed maximum sight radius.
    These two approaches are illustrated below, and both of them work regardless of whether the underlying FOV algorithm uses octants, although if the algorithm uses quadrants then option b can just union the rectangular bounding boxes of the lit areas in each quadrant together instead of maintaining the area per octant.
  4. A further optimization that can be applied to either approach in step #3 is to keep track of the exits of the convex area that the player is in. These can be the exits from a room or the tiles at the points where a corridor changes direction. If there is no overlap between the sector leading to the lit room and a sector leading to an open exit from the area the player is in, then there is no way for light to pass through an exit towards the lit room, so the lit room can be skipped. Alternately, you can maintain a bitmask for each tile that indicates which lit rooms are visible from that tile (assuming all doors are open), and then only consider those in step #3. Both of these additional optimizations may require some data to be recomputed if the map changes.

In the image above, the octants are in red, the light yellow tiles are lit (but not necessarily visible), the two pairs of green lines delimit the sectors from the player to the two lit rooms, and the pair of blue lines is the result of a FOV scan in the direction of the rightmost lit room. If the first approach in step #3 above is used, the sectors to each lit room would be scanned. In the second approach, the maximum distance for each octant would be determined (6 for octants 0 and 1, 9 for octant 3, and 0 for the other octants, assuming a Chebyshev distance metric) and a FOV algorithm would be run for the octants with nonzero distances. If either of the further optimizations in item #4 above was used, the leftmost lit room would not be considered, and only octants 0 and 1 would be scanned.

Light sources

You can also have light sources, which are objects that emit light and illuminate the tiles around them, such as torches and magic gems. If a light source is wielded by the player, you can simply increase the player's minimum sight radius to match the radius of the light source, but if the light source is wielded by another monster or placed on the map, you can use the strategy of NetHack-style lighting described above. The main difference is that in addition to (or instead of) fixed lit areas generated with the map you also have temporary lit areas generated by light sources. The lit areas need not be rectangular, although their bounding boxes should be known. To determine the tiles lit by a light source, you simply run the FOV algorithm from the position of the light source with a maximum radius equal to the radius of the light source. The tiles "visible" to the light source are the ones lit by it.

────────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙o∙∙∙∙∙│
│∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
└────────────────────
Torches on the walls and a light carried by an orc

Light falloff

You may not want lit tiles, whether permanently lit or lit by a light source, to be visible from an infinite distance, since in a dark dungeon the light scattered from them would be attenuated over a distance. If all lit tiles have the same brightness and thus the same distance that they can transmit light, then this can be implemented by simply making the maximum sight radius used by the FOV algorithm (when finding distant lit tiles) no greater than the distance that a single tile can transmit its light. Alternately, if you have variable tile brightness, you can just check when finding a lit tile outside the player's sight radius whether the player is close enough to it, and when a light source illuminates a tile you can increase the tile's brightness based on the distance from the light source.

Colored lighting

If you have light sources then in addition to propagating light you can propagate the color of the light as well, and instead of simply marking tiles "lit", you can add the color of the light to the tile's color. The resolution of the color can be 1-16 bits per color channel, and the channels might be red, greed, blue, and possibly brightness. A brightness channel is useful if you're using 1-bit color channels, since the standard text display has 1-bit per color plus a brightness bit. With more bits per color channel you can infer brightness directly from the color intensities much as a grayscale image can be computed from a color image.

When adding a light source's color to a tile, there are four options for combining colors, but I think one is clearly preferable:

  • First, you can simply add and saturate. If bright yellow light is shone on a tile you may get the RGB color (255, 255, 0). If a bright red light is also shone onto the tile, the resulting color would still be (255, 255, 0), since the red channel has been saturated. This allows the color additions red + blue + green = white and medium yellow + medium red = bright orange, but not bright yellow + bright red = bright orange or medium yellow + medium red = medium orange. Saturation is not physically correct but it's simple and produces decent results in most cases.
  • Second, you can blend the light color into the tile color. If a bright yellow light and a bright red light are shone on a tile, you get the RGB color (255, 127, 0) which is bright orange. This is nice, but other combinations are not so nice. For example, bright red + bright green is not bright yellow but medium yellow, and red + green + blue is a blueish color, not white or even gray. Blending is not physically correct and simply doesn't work well with more than two colors. I'd only recommend it if you'll only blend up to two colors and you really want to favor dim colors.
  • The third option is to use high dynamic range and rescale based on the most intense color. For instance, you might use colors with 8 bits per channel in your game. You can then have 8-bits per channel in your light sources and 16-bits per channel in your tiles. Then, to take the same example, a bright yellow and bright red light shining onto a tile would add together to produce the RGB color (510, 255, 0). Then, to obtain the actual color you take the most intense channel (red: 510) and compare it to the maximum value allowed in the color channel (255). Since it's greater, you rescale the color by a factor of 255/510 = 50%, resulting in the RGB color (255, 127, 0), which is bright orange. (If the most intense channel is not out of range, don't rescale.) Bright red + bright yellow = bright orange and red + green + blue = white, although medium yellow + medium red = bright orange, which is physically correct but may not be what you want. This is the best option in general because it's the most physically correct.
  • The fourth option is to use high dynamic range and average the colors. This works much like a combination of the previous two options, and is really just a form of color blending that works with more than two colors (although even for two colors or less it's an improvement over basic color blending). You'll need to keep track of how many lights have been added together. Adding bright red and bright yellow produces RGB (510, 255, 0) and since two lights were added the result is divided by 2 to obtain to output color, yielding RGB (255, 127, 0). This allows bright red + bright yellow = bright orange and medium red + medium yellow = medium orange, but red + blue + green = gray rather than white. I'd only recommend this method if you want dim colors to add together into dim colors.

┌─────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙│
└─────────────┘
Three overlapping colored lights
with 1-bit color channels

Colored lights can allow for nice atmospheric effects when near lava or mana pools, or if your game has animated spell effects (in which case a wand of lightning or fire could generate colored light). However, the question arises as to whether lights should color monsters and items on the ground as well, or just floor and wall tiles. Physically speaking, any object illuminated solely by a red light must appear red or black, so that is an argument for coloring monsters and items. But I'm of the opinion that monster and item colors displayed in traditional roguelikes do not represent the actual colors of objects but rather the types of objects. A giant bee should still appear yellow even if the player's creature is seeing it with darkvision or infravision or under a red light, since the player's creature can identify the bee by its shape and the color yellow communicates to the player that his creature sees a bee. That said, if your roguelike uses graphics tiles that allow the player to recognize things by shape, then it might in fact be a nice effect to tint them by the color of the light illuminating the tile. A similar argument can be had about special floor tiles, such as tiles of ice. It may be worth displaying them as white or bright cyan rather than coloring them based on the light because colored ice is still recognizable as ice and that's worth communicating to the player.

Comments
.: Thanks! | 2015-03-31 06:13AM :.
Great article! Very useful! Thanks!
an anonymous JuaniT
.: RE: Thanks! | 2015-03-31 03:31PM :.
I'm glad you found it helpful. :-)
.: Is there a name for this algorithm? | 2015-05-26 01:40PM :.
I love your fov algorithm! I'm fooling around with making a Roguelike in GameMaker and did a GML implementation of it. I'm just making this game for fun as a hobby, nothing commercial, but I would still like to give you credit for the algorithm. Is it just called "My Algorithm"?
an anonymous Greg
.: RE: Is there a name? | 2015-05-29 03:47AM :.
Hi Greg. I haven't given the algorithm any fancy name. "My algorithm" works from my point of view. :-) But no credit is needed if you want to use it. However, if you want to anyway, you might just call it call it "Adam Milazzo's algorithm" or link to this page.
.: lol | 2015-11-11 05:30AM :.
Really interesting. Great job
an anonymous Mat
.: | 2015-11-12 03:47AM :.
Pretty thorough, but some of it was hard to follow ... For example, you don't really explain what your algorithm does in detail, other than say it's "similar to" diamond walls and throwing up a wall of overcommented code. It uses octants, so I assume it works more like shadow casting. You also didn't explain why the tile is subdivided into 12 or 13 points (I assume this is based on the slope between the tile XY and the player XY)

Still, useful. But it'll take some time to digest it all.
an anonymous Anonymous
.: | 2015-11-12 06:44AM :.
Also, in the private methods for BlocksLight and SetVisible, you could probably save a bit of performance if you just inlined the returns as part of the switch statement.

Eg:
>case 0: return GetAllowFlow(x1 + x2, y1 - y2);

Since I believe this method is called in a tight loop, assigning the nx/ny variables is a little wasteful. I also tried to use ref/out in my delegates for the construction, but this required a custom delegate type and did not support lambda expressions, making it harder to use, but if you can change these function calls so that they pass, rather than copy variables, again you should see a significant boost.
an anonymous Anonymous
.: RE: Vision algorithms | 2015-11-12 05:26PM :.
The primary difference with my algorithm is the use of the "inner square" and the selectively beveled walls, and I think I did explain them, even if briefly. I don't know whether you read that part and found my explanation insufficient, or whether you didn't read it at all, but it's certainly not true that all I do is "say it's 'similar to' diamond walls and throw up a wall of overcommented code". If you have a constructive criticism about the actual explanation that is there, I'd be glad to hear it.

The tile is divided up to allow all the corners of the tile geometry - beveled and unbeveled walls, and the inner square - to be referenced, since it's the corners that mark the boundaries where light begins to intersect the geometry.

Regarding the first potential optimization you mentioned, you may or may not be right but such things should be tested because the results are often unexpected. With a smart compiler it'd be the same either way, but I don't know if the .NET JIT compiler is smart enough. I recommend trying it out and seeing if there's a significant improvement. My suspicion is that it would be minor at best, but I haven't tried it myself.

Regarding the delegates passed to the constructor, you can use ref/out parameters with lambda expressions using the 'delegate' keyword (Func(1, 2, delegate(out int x) { x=5; });) or by specifying the type (Func(1, 2, (out int x) => { x=5; })). I don't think you'll see a performance improvement from that, though. The parameters are simple integers. In general, it's slower to use integers by reference. Even replacing two integers with a reference to a single Point structure is likely slower. (Obviously it depends on what the functions do, but I expect that using references would not be faster in any realistic function.)

Anyway I don't actually expect people to use delegates. I used them to remove extraneous information (such as the map representation and game logic) from the article so I could focus on the vision algorithms. You can just replace them with normal function calls and make the vision calculator a static class or singleton if that's suitable for your project. In my own project, the vision calculator is not even a class, but just a function.
.: | 2015-11-13 09:39AM :.
Alright, I mostly understand it now. I think I was just a little bit confused, lots to take in. Thanks!
an anonymous Anonymous
.: RE: Vision algorithms | 2015-11-13 02:21PM :.
No problem. But do let me know if you think some part of my explanation can be worded better, etc.
.: Thanks very much! | 2016-04-16 09:01PM :.
This is an amazingly detailed and thorough article. Thank you for taking the time to write it up so carefully!

The only omission I found was, you never actually say what language your code is in (as far as I can tell). It looks like C#, and you did mention .NET in nthe comments above, so I suspect that's what it is. But it'd be nice to be explicit.

Anyway, I'm going to try this out for an educational roguelike for iOS that my boys and I are working on. Thanks for the leg up!
an anonymous Joe Strout
.: RE: Thanks very much! | 2016-04-18 06:08PM :.
Hi Joe. It is C#, but it should be pretty easy to convert to other languages, and in fact I don't expect people to use the code as-is, although you're welcome to. Anyway, it's quite cool that you're working on a project with your children. Good luck with it and I hope you guys have fun!
.: Using your code in CSRogue | 2016-09-16 06:38PM :.
Hey - LOVE your page here! So good! I had my own FOV calculator but liked yours much better and pretty much cut and pasted without any problems. I just want to make sure you know. I've put a laudatory message regarding this in the code but I want to give full credit where it's due. You can find the project on Github under CSRogue. If there's some way you'd particularly like credit for this, just let me know. It's really nice code and I want to acknowledge that.
an anonymous Darrell Plank
.: RE: Using your code in CSRogue | 2016-09-19 03:12PM :.
Hi Darrell. I'm glad you found it useful! I don't need any additional credit. Sorry about my "very quirky commenting style". :-) Good luck with the game!
.: Great code/explanation! | 2016-11-24 11:46AM :.
I love your code and the comparisons you present here, it's fantastic! After playing around with my own FOV and experimenting with various tweaks I've settled my thoughts. Beveled walls are amazing!

However, I also have to balance my appreciation for flood-fill style FOV (some call it diamond FOV? http://www.oocities.org/temerra/los_rays.html). Diamond FOV has the nice property of diagonal spaces acting as connected diagonal walls, which is a modification I'd like to make to your algorithm as it is appropriate to my game.

Do you have any advice how you would modify your algorithm to account for diagonal spaces becoming connected diagonal walls that block light?
an anonymous Chris
.: RE: Great code/explanation! | 2016-11-26 11:55AM :.
Hi Chris,

If I understand you correctly, you want a string of tiles connected diagonally to act as a solid wall. Would characters be able to move diagonally along the wall? It seems like they should be able to, but then that introduces ambiguous cases where it's not clear how to turn a group of blocks into diagonal walls. (It's easy to draw such a case on a piece of paper, but I don't have time to do it on the computer.) Anyway, if you make sure to avoid ambiguous tile arrangements when generating the map, or treat them as impassible, then I think it's doable.

I don't have time to write any code write now, since it's the holiday and I'm about to go out, but I'll try to think about it relatively soon.
.: RE: Great code/explanation! | 2016-12-11 10:34AM :.
Hi Chris,

I finally got time to work on this. Since you didn't give me your email address, I just put the code into this pastebin link: http://pastebin.com/2nTK50sg It's something of a hack because I didn't try to fit the modifications in to the rest of the code and optimize them, but it should work.

Good luck!
.: Connected Diagonal Walls | 2016-12-11 02:47PM :.
...wow, you just went ahead and straight up did it! Thanks, it's well appreciated and works very well!

I do appreciate the simplicity in comparing the two variants. Besides, I can live with a handful of extra BlocksLight calls. It's okay since the algorithm is still the most robust vision algorithm I know of!

Thanks again!
an anonymous Chris
.: RE: Connected diagonal walls | 2016-12-11 05:36PM :.
I hope it has no bugs. :-) Some of those BlocksLight calls can probably be removed with some cleverness, but I didn't want to think too hard. The thing I like most about the link you gave (http://www.oocities.org/temerra/los_rays.html) is that according to the author it's simple to extend to 3D, which seems pretty hard to do with my algorithm, though I suspect it wouldn't perform well with multiple agents all looking around.
.: Shadow casting question | 2017-02-09 09:21PM :.
Hello,

I have a question about the code in Shadow casting.

Shouldn't GetDistance(x, y) in
bool inRange = rangeLimit < 0 || GetDistance(x, y) <= rangeLimit;

be GetDistance(tx, ty) instead? since x is always between 1 and rangeLimit regardless of the origin position.
an anonymous Rikami
.: RE: Shadow casting question | 2017-02-13 03:26PM :.
Yes, I think you're right and it was incorrectly copied and pasted without changing the variable names. Thanks for noticing!

Add a comment
Note: The information you enter (including your name and email address) will be displayed publicly.
Name:
Email (optional):
Type "human"
(without quotes, to
indicate that you're
not a spammer)
Subject:
Body:Line breaks are converted to <br>'s, and all HTML tags except b, u, i, tt, and pre are filtered out.
 
Copyright 2003-2016 Adam Milazzo. Verbatim copying and redistribution of this entire page are permitted without royalty in any medium provided this notice is preserved.