Web Rarely

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

• 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

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).

───────────────────┤
∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
─────┬┬─∙┌┬──┐∙∙∙∙∙+
     ├┘∙∙└┤  └─────┤

∙∙∙∙∙∙∙∙∙∙∙∙
∙@∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙┼∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙@∙∙∙∙∙∙
∙∙∙∙┼∙┼∙┼∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙

─────────────────
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬──┐∙∙∙
     ├┘∙∙└┤  └───

─────────────────
∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬──┐∙∙∙
     ├┘∙∙└┤  └───

─────────────────
∙∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬──┐∙∙∙
     ├┘∙∙└┤  └───

Code to implement ray casting is below.

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

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).

∙∙∙@┼∙∙∙∙∙
∙∙∙┼∙∙∙∙∙∙
∙∙┼∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙
┼∙∙∙∙∙∙∙∙∙

∙∙∙@┼∙∙∙┼∙
∙∙∙∙∙∙∙∙∙∙
∙∙∙∙┼∙∙∙┼∙
∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙│ 
∙∙∙∙┼∙│∙∙│ 
∙∙∙∙∙∙│∙∙│ 
∙∙∙∙∙∙∙∙∙└─
∙@∙∙∙│∙∙∙∙∙

∙│                   │∙∙∙∙∙∙∙∙∙∙∙
∙└───────────────────┤∙∙∙∙∙∙∙┼∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─∙┌┬────────┤∙∙∙∙∙∙∙┼∙∙∙
       ├┘∙∙└┤        │∙∙∙∙∙∙∙∙∙∙∙

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.

───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└

    ┌──────
    │∙∙∙∙∙∙
    │∙∙∙∙∙∙
    │∙∙∙∙∙∙
    │@∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙│ 
∙∙∙∙┼∙│∙∙│ 
∙∙∙∙∙∙│∙∙│ 
∙∙∙∙∙∙∙∙∙└─
∙@∙∙∙│∙∙∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

Code to implement basic shadow casting is below.

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

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.

   │∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙┼
∙∙∙■∙∙∙∙∙┼@

@┼∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙∙

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

           │∙∙∙∙∙∙∙∙∙∙∙
───────────┤∙∙∙∙∙∙∙┼∙∙∙
@∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙
∙┌┬────────┤∙∙∙∙∙∙∙┼∙∙∙
∙└┤        │∙∙∙∙∙∙∙∙∙∙∙

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.

───────────
@∙∙∙∙∙∙∙∙∙∙
─────┬┬─∙┌┬
     ├┘∙∙└┤
    ┌┘∙∙│∙└

──────────┐
∙∙∙∙∙∙∙∙∙∙│
@∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

├───∙──────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙┼∙┼∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙│∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

Code to implement diamond walls is below.

Half-width walls

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)

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.

   │∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙
∙∙∙■∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼@
   │∙∙∙∙∙∙∙∙∙

@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

─┴─────────■───
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@┌─────────■───
∙│∙∙∙∙∙∙∙∙∙∙∙∙∙
+┤∙∙∙∙∙∙∙∙│∙∙∙∙

│∙│                 ┌┬───┐
│∙├┬────────────────┴┘∙∙∙│
│∙└┘∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙┌─┘
│@∙∙∙┌─────────────────┘  
└────┘                    

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

Digital field of view (diamond-to-diamond)

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

• 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

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.

∙∙∙@┼∙∙∙∙∙
∙∙∙┼∙∙∙∙∙∙
∙∙┼∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙
┼∙∙∙∙∙∙∙∙∙

@┼∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙
∙┼∙∙∙∙∙∙∙∙

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙┼∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

         │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
┬────────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
┤        │∙∙∙∙∙∙∙∙∙∙∙∙∙

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.

           
───────────
@∙∙∙∙∙∙∙∙∙∙
┬┬─∙┌┬─────
├┘∙∙└┤     

──────────┐
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
@∙∙∙∙∙∙∙∙∙│

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙┼∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

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.

           
───────────
@∙∙∙∙∙∙∙∙∙∙
┬┬─∙┌┬─────
├┘∙∙└┤     

──────────┐
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙│
@∙∙∙∙∙∙∙∙∙│

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙┼∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

Code to implement my algorithm is below.

Comparison

Corner peeking

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

───────────
∙∙∙∙∙∙∙∙∙∙∙
──┬┬─@┌┬───
  ├┘∙∙└┤   
 ┌┘∙∙│∙└┐  

Corridor asymmetry

∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       

∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       

∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       

∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       

∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       

∙└───────────────────
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───────┬┬─@┌┬────────
       ├┘∙∙└┤        
      ┌┘∙∙│∙└┐       

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙+∙∙∙+∙∙∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙+∙∙∙+∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙+
∙∙∙∙∙∙+∙
∙∙∙∙∙+∙∙
∙∙∙∙+∙∙∙
∙∙∙+∙∙∙∙
∙∙+∙∙∙∙∙
@+∙∙∙∙∙∙

∙∙∙∙∙∙∙+
∙∙∙∙∙∙+∙
∙∙∙∙∙+∙∙
∙∙∙∙+∙∙∙
∙∙∙+∙∙∙∙
∙∙+∙∙∙∙∙
@+∙∙∙∙∙∙

∙∙∙∙∙∙∙+
∙∙∙∙∙∙+∙
∙∙∙∙∙+∙∙
∙∙∙∙+∙∙∙
∙∙∙+∙∙∙∙
∙∙+∙∙∙∙∙
@+∙∙∙∙∙∙

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
┤∙∙∙∙∙∙+
■∙∙∙∙∙+@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙+
┤∙∙∙∙∙+∙
■∙∙∙∙+∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙+
│∙∙∙∙∙∙+∙
│∙∙∙∙∙+∙∙
│∙∙∙∙+∙∙@

Rooms

 ┌───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────┘

 ┌───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────┘

 ┌───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────┘

 ┌───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────┘

 ┌───────────┐
 │∙∙∙∙∙∙∙∙∙∙∙│
┌┘∙──┬─────┐∙│
┤∙∙∙∙│     │∙│
┘∙∙∙∙│     │∙│
@∙∙∙∙└───┐ │∙│
┐∙∙∙∙∙∙∙∙└─┘∙│
│∙∙∙∙┌─┐∙∙∙∙∙│
│∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

────────┬
∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙

────────┬
∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙

────────┬
∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙

────────┬
∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙

────────┬
∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙│
∙∙∙+∙│∙∙│
∙∙∙∙∙│∙∙│
∙∙∙∙∙∙∙∙└
@∙∙∙│∙∙∙∙

─────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙

─────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙

─────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙

─────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙

─────┬
∙∙∙∙∙│
∙∙∙∙∙│
+∙│∙∙│
∙∙│∙∙│
∙∙∙∙∙└
@│∙∙∙∙

┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙│
   │∙└

┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙│
   │∙└

┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙│
   │∙└

┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙│
   │∙└

┌─┐   
│@└──┐
│∙∙∙∙│
└──┐∙│
   │∙│
   │∙└

┌─┘∙└┬─┐
│∙∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│∙│
│∙∙+∙∙∙│
│∙@∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│
└─┬+┬──┘

┌─┘∙└┬─┐
│∙∙∙∙│@│
│∙∙+∙∙∙│
│∙∙∙∙∙∙│
└─┬+┬──┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙│          
│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙+∙+∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

────────
∙∙∙∙∙∙∙∙
┬─∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│

────────
∙∙∙∙∙∙∙∙
┬─∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│

────────
∙∙∙∙∙∙∙∙
┬─∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│

────────
∙∙∙∙∙∙∙∙
┬─∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│

────────
∙∙∙∙∙∙∙∙
┬─∙┌┬───
┘∙∙└┤   
∙∙│∙└┐  
∙┌┴┐∙└┐ 
┌┘ └┐∙└┐
┘   └┐@│

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙

┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@

┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@

┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@

┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@

┌──────────
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙┼∙
│∙∙∙∙∙∙∙∙∙@

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙+∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙+∙@∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙+∙∙∙+∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴───────────────────┴

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙+∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
──────────────┤

+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+

+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+

+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+

+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+

+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙@∙∙∙∙∙
+∙+∙+∙+∙+∙+
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+
∙∙∙∙∙∙∙∙∙∙∙
∙∙+∙+∙+∙+∙∙
∙∙∙∙∙∙∙∙∙∙∙
+∙∙∙+∙+∙∙∙+

∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙

∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙

∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙

∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙

∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙+∙+∙+∙+∙

∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙

∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙

∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│

∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│

∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙+@+∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙+∙+∙+∙+∙+∙+∙+∙+∙+∙+∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙+∙+∙+∙+∙+∙+∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙+∙+∙∙∙+∙+∙∙∙+∙+∙∙∙│

Symmetrical versions

│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │

│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │

│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │

│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │

│∙└───────────────────┤
│∙∙∙∙∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙+
└───────┬┬─∙┌┬────────┤
        ├┘∙∙└┤        │
       ┌┘∙∙│∙└┐       │

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙

   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
@∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
───┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙
   │∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
   │∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙

     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
@∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙
─────┤∙∙∙∙∙∙∙┼∙∙∙┼∙
     │∙∙∙∙∙∙∙∙∙∙∙∙∙
     │∙∙∙∙∙∙∙┼∙∙∙┼∙

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│   ┌───────────┐
│   │∙∙∙∙∙∙∙∙∙∙∙│
│  ┌┘∙──┬─────┐∙│
└─┬┤∙∙∙∙│     │∙│
∙∙└┘∙∙∙∙│     │∙│
┐∙∙∙∙∙∙∙└───┐ │∙│
└──┐∙∙∙∙∙∙∙∙└─┘∙│
   │∙∙∙∙┌─┐∙∙∙∙@│
   │∙∙∙∙│ └─────┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│@└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│∙┌┤
└────────┴─┴┘

│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

│∙└─────────┐
│∙∙∙∙∙∙∙∙∙∙∙│
├───∙───────┤
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙┼∙┼∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙│@┌┤
└────────┴─┴┘

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙┼
┤∙∙∙∙∙∙┼∙
■∙∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙┼
┤∙∙∙∙∙∙┼∙
■∙∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙┼
┤∙∙∙∙∙∙┼∙
■∙∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙┼
┤∙∙∙∙∙∙┼∙
■∙∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@

┌────────
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙┼
┤∙∙∙∙∙∙┼∙
■∙∙∙∙∙┼∙∙
┤∙∙∙∙┼∙∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@

┌───────
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙∙
│∙∙∙∙∙∙┼
┤∙∙∙∙∙┼∙
■∙∙∙∙┼∙@

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴─────────+─────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴─────────+─────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴─────────+─────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴─────────+─────────┴

┌───────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┤∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
┤∙∙∙∙∙∙∙┼∙@∙┼∙∙∙∙∙∙∙■
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙├
│∙∙∙∙∙∙∙┼∙∙∙┼∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
┴─────────+─────────┴

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤

──────────────┐
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
@∙∙∙∙∙∙∙∙∙∙∙∙∙+
∙∙┼∙∙∙∙∙∙∙∙∙∙∙├
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
∙∙┼∙∙∙∙∙∙∙∙∙∙∙│
∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
────────+─────┤

Performance

• 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

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

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

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(x, y) <= 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

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(x, y) <= 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

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;
    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, 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, 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);
      return checkField(currentField, activeFields);
    }
    else if(currentField.Value.steep.isBelow(topLeft))
    {
      addSteepBump(bottomRight, currentField);
      return checkField(currentField, activeFields);
    }
    else
    {
      LinkedListNode<Field> steeper = currentField, shallower = activeFields.AddBefore(currentField, currentField.Value);
      addSteepBump(bottomRight, shallower);
      checkField(shallower, activeFields);
      addShallowBump(topLeft, steeper);
      return checkField(steeper, activeFields);
    }
  }
  
  static void addShallowBump(Offset point, LinkedListNode<Field> currentField)
  {
    Field value = currentField.Value;
    value.shallow.far = point;
    value.shallowBump = new Bump() { location = point, parent = 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)
  {
    Field value = currentField.Value;
    value.steep.far = point;
    value.steepBump = new Bump() { location = point, parent = 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

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 = (uint)origin.X, ny = (uint)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 = (uint)origin.X, ny = (uint)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

┌──────┐                ┌─────┐
│∙∙∙∙∙∙│       ┌───┐    │∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙@∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙│       └───┘    │∙∙∙∙∙│
└──────┘                └─────┘

┌──────┐                ┌─────┐
│∙∙∙∙∙∙│       ┌───┐    │∙∙∙∙∙│
│∙∙∙∙∙∙│       │@∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙│       └───┘    │∙∙∙∙∙│
└──────┘                └─────┘

┌──────┐                ┌─────┐
│∙∙∙∙∙∙│       ┌───┐    │∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙■∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙■∙∙∙∙∙│
│∙∙∙∙∙∙│       │∙∙∙│    │∙∙∙∙∙│
│∙∙∙∙∙∙│       └───┘    │@∙∙∙∙│
└──────┘                └─────┘

As you can see, lit tiles aren't 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

┌───────────────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙o∙∙∙∙∙│
│∙∙∙∙∙∙@∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙│
└───────────────────────┘

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

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.

┌─────────────┐
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
│∙∙∙∙∙∙∙∙∙∙∙∙∙│
└─────────────┘

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.