The map and line of sight
In short: The field of view is the set of cells the hero can see: a Bresenham line is drawn to every cell in range, a wall stops it, and what was seen once stays on the map as fog.
Problem
The boss is visible from the entrance
The first level of the mine is 50 × 20 cells, and the map on the screen is 40 × 13. The whole level does not fit. Even if it did, you should not see all of it: if you can see the Warden of the Depths and every chest from the entrance, there is nothing left to discover.
So the game shows only what the hero can see, and it remembers what the hero has seen. Here is the first frame after the hero goes down into the mine (from the playthrough the game is checked with):
### The upper gallery#@.....# Level 1 of 3#......+ ......# Around: ...... nobody ######
Iva, barbarian lv1 xp 0/20 gold 5L [############] 48/48 M [########] 4/4New quest: The blood trail.New quest: Silver for the smith.You are in The upper gallery, level 1.You can see the room and the door. The corridor and the hall behind the door are not there, although they are five or six cells away. This frame needs five things: a map from text, movement with collision, a camera, a field of view and fog. The lesson builds them one by one on a small 16 × 7 level, and then shows the same place in the game.
The idea
The level is text
The level of this lesson is 16 × 7:
#################......#.......##......+.......##...~~@#....>..##...~~.#.......##......#.......#################Each character is a cell: # wall, . floor, + closed door, ~ water, > stairs down, @ the hero. The code does not know the shape of the level. It reads the text. A new level is new text, without a single new line of code.
For moving and looking, a cell has to answer two questions: can you walk on it and does it block sight. The two answers do not always go together. You can see across water, but you cannot walk through it. A closed door blocks sight and does not let you in. So a tile is a record with a character, a name and the two answers, and the table of tiles is data:
record Tile(char Glyph, string Name, bool Walkable, bool Opaque);
class Level{ public static readonly List<Tile> Tiles = [ new('#', "wall", false, true), new('.', "floor", true, false), new('+', "door", false, true), new('\'', "open door", true, false), new('~', "water", false, false), new('>', "stairs", true, false), ];
public readonly int Width; public readonly int Height; public readonly Tile[,] Cells; public int HeroX; public int HeroY;
public Level(string text) { string[] rows = text.Split('\n'); Height = rows.Length; Width = rows[0].Length; Cells = new Tile[Height, Width]; for (int y = 0; y < Height; y++) { for (int x = 0; x < Width; x++) { char glyph = rows[y][x]; if (glyph == '@') { HeroX = x; HeroY = y; glyph = '.'; } Cells[y, x] = TileOf(glyph); } } }
public static Tile TileOf(char glyph) { foreach (Tile tile in Tiles) { if (tile.Glyph == glyph) return tile; } throw new ArgumentException("Unknown cell: " + glyph); }
public bool InBounds(int x, int y) => x >= 0 && y >= 0 && x < Width && y < Height;
// Outside the map is wall: nobody walks out and nobody looks out. public Tile At(int x, int y) => InBounds(x, y) ? Cells[y, x] : Tiles[0];}const string MAP = """ ################ #......#.......# #......+.......# #...~~@#....>..# #...~~.#.......# #......#.......# ################ """;
var level = new Level(MAP);Console.WriteLine("The level is " + level.Width + " × " + level.Height + ", the hero is at (" + level.HeroX + ", " + level.HeroY + ").");foreach (Tile tile in Level.Tiles){ int count = 0; foreach (Tile cell in level.Cells) { if (cell == tile) count++; } if (count == 0) continue; string walk = tile.Walkable ? "yes" : "no"; string sight = tile.Opaque ? "yes" : "no"; Console.WriteLine(tile.Glyph + " " + tile.Name + ": " + count + ", walkable: " + walk + ", blocks sight: " + sight);}The level is 16 × 7, the hero is at (6, 3).# wall: 46, walkable: no, blocks sight: yes. floor: 60, walkable: yes, blocks sight: no+ door: 1, walkable: no, blocks sight: yes~ water: 4, walkable: no, blocks sight: no> stairs: 1, walkable: yes, blocks sight: noAt(x, y) returns a wall for everything outside the map. That way neither moving nor looking has to check the bounds: nobody leaves the map, because outside is wall.
Tile[,]: one rectangular array indexed with [y, x]. The canon uses an array of arrays ([y][x]), like the other languages; for the programs here the rectangular one is shorter.More precisely, if you are curious
The grid has 112 cells, but there are only six tile objects. Every cell holds a reference to one of them, which is why the counting above compares with ==. When the door opens, the cell simply starts to point to another tile. This is the flyweight pattern: what is shared (the name, the properties) is in one place, and the position on the map is in the grid.
In the canon the cells are characters, and the properties are two small methods: isWalkable and isOpaque. The idea is the same and the form is simpler, because there are eight kinds and two properties. If you add more (movement cost, noise, light), the table wins again.
The idea
The levels in the game
The three levels of the mine are in one piece of text in the game's code. Each one starts with a line level|1|… (the depth and the name in all four languages), then come the rows of the map, the legend and end. Here is the first level without its header line:
###################################################<.....#............#........1.#..~~~~~.......2..##......+....r.......+......g...#..~~~~~..........##......#............#..........+..~~~~~..........##......#............#..........#.........,.......#########.........r..############........,........#########............############........,........###############.#########################,#######################.#########################.#######################.#########################,############....#.3............#########.........,...#########.4..?.........s....+..................,..#########....#...g..........#########..........,..##############..............###################+######################.###############........5555555....###......................######............,......###..................r...######..............,L...###.>....................######......w............###......7...............######.................6.###################################################legend|1|item|potion_heal|1legend|2|gold|25|0legend|3|item|antidote|1legend|4|item|ring_life|1legend|5|marker|lair|0legend|6|gold|30|0legend|7|item|potion_heal|1endThere are more characters than tiles. The letters (r, g, s, L) are enemies from the enemy table. The digits come from the legend below the map: an item, gold, a quest marker. < is where the hero comes down. ? is a secret door that looks like a wall. , is blood on the floor.
// The map is text: the lines between "level|..." and "legend|..." are the map itself, the legend says what// each digit means. This only reads the definitions; the live level is built in BuildLevel.class LegendEntry{ public string Kind = ""; public string Value = ""; public int Amount;}
class MapDef : Named{ public int Depth; public List<string> Rows = new List<string>(); public Dictionary<char, LegendEntry> Legend = new Dictionary<char, LegendEntry>();}
static partial class Arcanum{ public static void LoadMaps() { MapDef? current = null; foreach (string rawLine in MAPS_DATA.Split('\n')) { string line = TrimSpaces(rawLine); if (line.Length == 0) continue; if (line.StartsWith("level|", StringComparison.Ordinal)) { string[] cells = line.Split('|'); current = new MapDef { Depth = ToInt(cells[1]), Bg = cells[2], En = cells[3], De = cells[4], Es = cells[5], Rows = new List<string>(), Legend = new Dictionary<char, LegendEntry>() }; } else if (line.StartsWith("legend|", StringComparison.Ordinal)) { string[] cells = line.Split('|'); current!.Legend[cells[1][0]] = new LegendEntry { Kind = cells[2], Value = cells[3], Amount = ToInt(cells[4]) }; } else if (line == "end") { MAP_DEFS.Add(current!); current = null; } else { current!.Rows.Add(line); } } }}Reading happens in two steps. loadMaps only splits the text into definitions. The live level is built with buildLevel on a new game (and on loading): letters become enemies, digits become items, and floor stays under them. That is why there is no goblin in the level's grid. Creatures are a separate list that moves over the map, and the map stays still.
The idea
A move is a request
The simplest move is heroX += dx. With it the hero walks through walls and off the map. A move has to be a request: "I want to go there". The cell the hero wants to enter decides:
// A move is a request: the cell you want to enter decides.static string Step(Level level, int dx, int dy){ int x = level.HeroX + dx; int y = level.HeroY + dy; Tile target = level.At(x, y); if (target.Glyph == '+') { level.Cells[y, x] = Level.TileOf('\''); return "The door creaks open."; } if (!target.Walkable) return "Blocked: " + target.Name + "."; level.HeroX = x; level.HeroY = y; return "";}- a wall or water: no, and it says why;
- a closed door: it opens (becomes
'), but the hero stays in place. Opening it is the move; - anything else: the hero walks in.
The program reads the commands w a s d (up, left, down, right), one per line, and draws the level after each one. The input is d a w d d d:
var level = new Level(MAP);string? line;while ((line = Console.ReadLine()) != null){ string command = line.Trim(); if (command.Length != 1) continue; int dir = MOVES.IndexOf(command[0]); if (dir < 0) continue; string message = Step(level, DX[dir], DY[dir]); Console.WriteLine(message == "" ? "> " + command : "> " + command + " " + message); PrintLevel(level);}> d Blocked: wall.#################......#.......##......+.......##...~~@#....>..##...~~.#.......##......#.......#################> a Blocked: water.#################......#.......##......+.......##...~~@#....>..##...~~.#.......##......#.......#################> w#################......#.......##.....@+.......##...~~.#....>..##...~~.#.......##......#.......#################> d The door creaks open.#################......#.......##.....@'.......##...~~.#....>..##...~~.#.......##......#.......#################> d#################......#.......##......@.......##...~~.#....>..##...~~.#.......##......#.......#################> d#################......#.......##......'@......##...~~.#....>..##...~~.#.......##......#.......#################The first two moves go into a wall and into water: the hero stays put. Then the hero goes up, opens the door and walks through.
In the game the step does more, and the order matters:
// A step of the hero: battle, talk, door, hidden cache, wall or movement.public string StepHero(int dx, int dy){ Level level = Level()!; Hero hero = Hero; int x = hero.X + dx; int y = hero.Y + dy; Enemy? enemy = level.EnemyAt(x, y); if (enemy != null) { StartBattle(enemy); return "stop"; } Npc? npc = level.NpcAt(x, y); if (npc != null) { Stack.Push(new DialogScreen(this, npc.Id)); return "stop"; } char tile = level.Tile(x, y); if (tile == '+') { level.Tiles[y][x] = '\''; Say(T("map.door")); WorldTurn(); return Stack.Changes.Count > 0 ? "stop" : "acted"; } if (tile == '?') { level.Tiles[y][x] = '+'; Say(T("map.secret")); WorldTurn(); return Stack.Changes.Count > 0 ? "stop" : "acted"; } if (!level.IsWalkable(x, y)) { Say(T(tile == '~' ? "map.water" : "map.wall")); return "blocked"; } if (hero.HasEffect("bleed")) level.AddBlood(hero.X, hero.Y); hero.X = x; hero.Y = y; Bus.Publish(new GameEvent { Type = "TileEntered", Depth = Depth, X = x, Y = y, Decor = level.Decor[y][x], Marker = level.Markers[y][x] }); List<FloorItem> here = level.ItemsAt(x, y); if (here.Count > 0) { List<string> names = new List<string>(); foreach (FloorItem item in here) names.Add(ItemLabel(item.Id, item.Count)); Say(T("map.itemsHere", ("items", string.Join(", ", names)))); } WorldTurn(); return Stack.Changes.Count > 0 ? "stop" : "moved";}First it asks about an enemy: the enemy stands on floor, and if the tile decided first, the hero would walk into the enemy. Then a person (a conversation), a door, a secret door, and only then the tile. When the hero really moves, a bleeding hero leaves blood on the floor, the TileEntered event tells the quests where the hero is, and at the end the world takes its turn.
Bumping into a wall returns blocked and does not call worldTurn: a player mistake costs no turn, and the enemies do not get closer. The door costs a turn.
More precisely, if you are curious
Here water simply does not let you through. In many games shallow water does, but slowly: every tile has a movement cost (floor 1, shallow water 2, swamp 3), and the hero builds up energy until it reaches the cost, like the energy in combat (the lesson on the combat system). Then walkable becomes a number instead of yes or no. Pathfinding has to know the costs too: BFS is no longer enough, and you need Dijkstra.
The idea
The camera
The game's level is 50 × 20, and the view is 40 × 13. The camera is the world seen through a window: cameraX and cameraY are the world cell in the top left corner of the screen. Both directions are one addition away:
- from the world to the screen:
screenX = x − cameraX; - from the screen to the world:
x = cameraX + screenX.
The camera follows the hero: the hero is in the middle, so cameraX = heroX − VIEW_W / 2. Near the edge of the map this gives a negative number, or a view that runs off the map. So the camera is clamped between 0 and width − VIEW_W. There the view stops, and the hero moves toward the edge of the screen.
const int VIEW_W = 9;const int VIEW_H = 5;
static int Clamp(int value, int low, int high){ if (value < low) return low; if (value > high) return high; return value;}
static void PrintView(Level level){ int cameraX = Clamp(level.HeroX - VIEW_W / 2, 0, level.Width - VIEW_W); int cameraY = Clamp(level.HeroY - VIEW_H / 2, 0, level.Height - VIEW_H); Console.WriteLine($"hero ({level.HeroX}, {level.HeroY}), camera ({cameraX}, {cameraY}), on screen ({level.HeroX - cameraX}, {level.HeroY - cameraY})"); for (int viewY = 0; viewY < VIEW_H; viewY++) { var row = new char[VIEW_W]; for (int viewX = 0; viewX < VIEW_W; viewX++) { int x = cameraX + viewX; int y = cameraY + viewY; row[viewX] = x == level.HeroX && y == level.HeroY ? '@' : level.At(x, y).Glyph; } Console.WriteLine(new string(row)); }}The program uses a 9 × 5 view on the 16 × 7 level and prints the view after each leg of the hero's walk:
var level = new Level(MAP);foreach (string leg in new[] { "", "wdddd", "ddddd", "sss" }){ foreach (char command in leg) { int dir = MOVES.IndexOf(command); Step(level, DX[dir], DY[dir]); } PrintView(level);}hero (6, 3), camera (2, 1), on screen (4, 2).....#........+.....~~@#.....~~.#........#...hero (9, 2), camera (5, 0), on screen (4, 2)#########..#........'.@....~.#....>.~.#......hero (14, 2), camera (7, 0), on screen (7, 2)##########.......#'......@##....>..##.......#hero (14, 5), camera (7, 2), on screen (7, 3)'.......##....>..##.......##......@##########The first two views are centered: the hero is at (4, 2) on the screen. In the third one the camera has reached the right limit 16 − 9 = 7 and stops, while the hero keeps walking toward the edge. In the fourth the camera has stopped at the bottom too.
VIEW_W / 2 is integer division: 9 / 2 = 4.int cameraX = Clamp(level.HeroX - VIEW_W / 2, 0, );The rightmost camera is the one where the right edge of the view is at the right edge of the map: width − VIEW_W. For 16 × 7 and a view of 9 that is 7: the view shows columns 7 to 15.
More precisely, if you are curious
If the level is narrower than the view, width − VIEW_W is negative, and depending on where the hero is, clamp returns 0 or a negative number: the camera jumps or goes off the map on the left. In the canon this does not happen, because all three levels are 50 × 20, but in a game with small rooms the level is centered in the view: cameraX = (width − VIEW_W) / 2.
A camera that moves with every step makes the whole screen jump. Many games keep a dead zone: the camera moves only when the hero leaves a rectangle in the middle. In a turn-based console game you rarely need it; in a game with smooth movement you do.
The game does the same with 40 × 13. Here is a frame further down the first level: the camera has moved down, so the top rows of the level are out of view:
########............############........ The upper gallery #............# #........ Level 1 of 3 #######.##### ######### # Around: ###### ########## nobody ........#########......... ...%.%@.'................. ........#########......... ........# ########## ######## . ... .... ....Iva, barbarian lv2 xp 40/55 gold 30L [############] 57/57 M [########] 5/5Goblin spearman notices you!Victory! Experience from the fight: 21.Iva reaches level 2: new skill: Whirlwind (Fury branch).The idea
First try: a radius
The hero should see the area around them. The first idea is a radius: you see every cell closer than 6.
const int RADIUS = 6;
static void RadiusOnly(Level level, bool[,] visible, bool[,] seen){ int originX = level.HeroX; int originY = level.HeroY; for (int y = 0; y < level.Height; y++) { for (int x = 0; x < level.Width; x++) visible[y, x] = false; } for (int y = originY - RADIUS; y <= originY + RADIUS; y++) { for (int x = originX - RADIUS; x <= originX + RADIUS; x++) { if (!level.InBounds(x, y)) continue; int dx = x - originX; int dy = y - originY; if (dx * dx + dy * dy > RADIUS * RADIUS + RADIUS) continue; visible[y, x] = true; seen[y, x] = true; } }}visible means "I see it now". seen means "I have seen it at some point", and it is used later for the fog. Here is what the hero sees from the start:
var level = new Level(MAP);var visible = new bool[level.Height, level.Width];var seen = new bool[level.Height, level.Width];RadiusOnly(level, visible, seen);Report(level, visible, seen);hero (6, 3): you see 87, you remember 87| ########### ||#......#..... ||#......+..... ||#...~~@#....> ||#...~~.#..... ||#......#..... || ########### |87 cells are visible, and among them the stairs (>) behind the wall. The closed door does not matter. The radius knows how far away a cell is, but not what is between it and the hero. This is the boss you can see from the entrance.
More precisely, if you are curious
Why is the condition dx² + dy² ≤ R² + R and not ≤ R²? With ≤ R², four lonely cells stick out of the circle: (R, 0), (0, R) and their mirror images. The extra + R rounds it off: for whole numbers, dx² + dy² ≤ R² + R is the same as a distance to the cell's center under R + ½, because (R + ½)² = R² + R + ¼. No square root and no fractions.
The idea
A straight line: Bresenham
A cell is visible if the straight line from the hero to it does not pass through a wall. On a grid a straight line is a sequence of cells, and you have to decide which ones. Bresenham's algorithm does it with whole numbers only: addition, subtraction and multiplying by 2.
The idea: you start at one end, and at every step you move along x, along y, or both. Which one is decided by error: how far the line has drifted from the true straight line. When the drift along one axis gets too big, you take a step along it and reduce the drift.
static List<(int X, int Y)> Line(int x0, int y0, int x1, int y1){ var cells = new List<(int X, int Y)>(); int dx = Math.Abs(x1 - x0); int dy = -Math.Abs(y1 - y0); int stepX = x0 < x1 ? 1 : -1; int stepY = y0 < y1 ? 1 : -1; int error = dx + dy; int x = x0; int y = y0; while (true) { cells.Add((x, y)); if (x == x1 && y == y1) return cells; int doubled = 2 * error; if (doubled >= dy) { error += dy; x += stepX; } if (doubled <= dx) { error += dx; y += stepY; } }}The program draws the line from A = (0, 0) to B = (8, 3), and then back, from B to A:
var there = Line(0, 0, 8, 3);var back = Line(8, 3, 0, 0);Console.WriteLine("A → B: " + Format(there));Console.WriteLine("B → A: " + Format(back));var picture = new char[4, 9];for (int y = 0; y < 4; y++){ for (int x = 0; x < 9; x++) picture[y, x] = '.';}foreach (var (x, y) in there) picture[y, x] = '*';picture[0, 0] = 'A';picture[3, 8] = 'B';for (int y = 0; y < 4; y++){ var row = new char[9]; for (int x = 0; x < 9; x++) row[x] = picture[y, x]; Console.WriteLine(new string(row));}A → B: 0,0 1,0 2,1 3,1 4,2 5,2 6,2 7,3 8,3B → A: 8,3 7,3 6,2 5,2 4,1 3,1 2,1 1,0 0,0A*.........**.........***.........*BThe two directions go through almost the same cells, but not quite: the way there passes through 4,2, and the way back through 4,1. Halfway the error is exactly even, and the algorithm picks one side. Going back it picks the other one. Remember this: you will need it for the weak spots of the method.
More precisely, if you are curious
Where does error = dx + dy (with dy negative) come from? The straight line through the two ends is f(x, y) = 0, where f is linear, and the sign of f tells you which side you are on. error is f, scaled to be a whole number, at the point that would come next. The checks 2 · error ≥ dy and 2 · error ≤ dx ask whether a step along x, or along y, brings you closer to the line. That is why the algorithm works in all eight directions and never divides.
Jack Bresenham came up with it at IBM in 1962 for a plotter: the machine moves the pen one step at a time, and division is expensive. Today division is not expensive, but whole numbers give the same result on every computer and in every language, and for our game that is a must.
See it
Field of view and fog
Now the two come together. A Bresenham line goes to every cell in the radius. At every step the line checks two things: have we arrived and is there a wall here. The order matters. If the line has reached the target, the cell is visible, even if it is a wall. If there is a wall on the way before the target, the line stops: the cell is not visible.
const int RADIUS = 6;
static bool LineOfSight(Level level, int x0, int y0, int x1, int y1){ int dx = Math.Abs(x1 - x0); int dy = -Math.Abs(y1 - y0); int stepX = x0 < x1 ? 1 : -1; int stepY = y0 < y1 ? 1 : -1; int error = dx + dy; int x = x0; int y = y0; while (true) { if (x == x1 && y == y1) return true; if ((x != x0 || y != y0) && level.At(x, y).Opaque) return false; int doubled = 2 * error; if (doubled >= dy) { error += dy; x += stepX; } if (doubled <= dx) { error += dx; y += stepY; } }}
static void ComputeFov(Level level, bool[,] visible, bool[,] seen){ int originX = level.HeroX; int originY = level.HeroY; for (int y = 0; y < level.Height; y++) { for (int x = 0; x < level.Width; x++) visible[y, x] = false; } for (int y = originY - RADIUS; y <= originY + RADIUS; y++) { for (int x = originX - RADIUS; x <= originX + RADIUS; x++) { if (!level.InBounds(x, y)) continue; int dx = x - originX; int dy = y - originY; if (dx * dx + dy * dy > RADIUS * RADIUS + RADIUS) continue; if (LineOfSight(level, originX, originY, x, y)) { visible[y, x] = true; seen[y, x] = true; } } }}static bool LineOfSight(Level level, int x0, int y0, int x1, int y1){ int dx = Math.Abs(x1 - x0); int dy = -Math.Abs(y1 - y0); int stepX = x0 < x1 ? 1 : -1; int stepY = y0 < y1 ? 1 : -1; int error = dx + dy; int x = x0; int y = y0; while (true) { if (x == x1 && y == y1) return true; if ((x != x0 || y != y0) && level.At(x, y).Opaque) return false; int doubled = 2 * error; if (doubled >= dy) { error += dy; x += stepX; } if (doubled <= dx) { error += dx; y += stepY; } }}
static void ComputeFov(Level level, bool[,] visible, bool[,] seen){ int originX = level.HeroX; int originY = level.HeroY; for (int y = 0; y < level.Height; y++) { for (int x = 0; x < level.Width; x++) visible[y, x] = false; } for (int y = originY - RADIUS; y <= originY + RADIUS; y++) { for (int x = originX - RADIUS; x <= originX + RADIUS; x++) { if (!level.InBounds(x, y)) continue; int dx = x - originX; int dy = y - originY; if (dx * dx + dy * dy > RADIUS * RADIUS + RADIUS) continue; if (LineOfSight(level, originX, originY, x, y)) { visible[y, x] = true; seen[y, x] = true; } } }}Step by step, in words
- The hero is at (6, 3). The field of view is computed again every turn, and first every cell becomes invisible. Nothing has been seen yet: the whole level is unknown.
- The candidates are the cells within radius 6: dx² + dy² ≤ 6² + 6. There are 87 of them, including the room behind the wall. The radius knows nothing about walls.
- A straight line (Bresenham) goes to every candidate. It stops at the first wall on the way, but it does reach that wall, so the wall itself is seen. 37 lines stop early (gray).
- From (6, 3) you see 50 cells, and they all go into seen. The room on the right is within the radius, but the closed door and the wall hide it: the stairs stay unknown.
- The hero opens the door and walks through (wdddddd). Every turn visible is cleared and seen stays: what you saw but no longer see turns into fog.
- From (11, 2) the lines pass through the open door. In the left room only a narrow wedge is visible: the wall hides the rest.
- You see 63, you remember 109 of 112 cells. The fog keeps the shape of the left room, but not what is going on in it now.
Every turn visible is cleared and computed again, while seen only fills up. The program draws visible cells with their character, seen cells that are no longer visible with :, and unknown cells as blanks. First from the start, then after 7 moves (up, the door, five times right):
var level = new Level(MAP);var visible = new bool[level.Height, level.Width];var seen = new bool[level.Height, level.Width];ComputeFov(level, visible, seen);Report(level, visible, seen);foreach (char command in "wdddddd"){ int dir = MOVES.IndexOf(command); Step(level, DX[dir], DY[dir]); ComputeFov(level, visible, seen);}Report(level, visible, seen);hero (6, 3): you see 50, you remember 50| ###### ||#...... ||#......+ ||#...~~@# ||#...~~.# ||#...... || ###### |hero (11, 2): you see 63, you remember 109| :::::::####### ||:::::::#.......#||:::::..'...@...#||:::::::#....>..#||:::::::#.......#||:::::::#.......#|| ::::::#########|At first the stairs are not visible: the wall and the closed door hide them. After the hero walks through, the left room is fog. The hero knows what it looks like, but does not see what is going on in it: an enemy that walks in there will not show up on the screen.
In the game the field of view is the same code, at the same point in the turn:
// Field of view: a cell is visible if it is within the radius and the line to it (Bresenham) does not go// through a wall or a closed door. What was seen is remembered: that is the fog.static partial class Arcanum{ public const int FOV_RADIUS = 6;
public static bool LineOfSight(Level level, int x0, int y0, int x1, int y1) { int dx = Math.Abs(x1 - x0); int dy = -Math.Abs(y1 - y0); int stepX = x0 < x1 ? 1 : -1; int stepY = y0 < y1 ? 1 : -1; int error = dx + dy; int x = x0; int y = y0; while (true) { if (x == x1 && y == y1) return true; if ((x != x0 || y != y0) && level.IsOpaque(x, y)) return false; int doubled = 2 * error; if (doubled >= dy) { error += dy; x += stepX; } if (doubled <= dx) { error += dx; y += stepY; } } }
public static void ComputeFov(Level level, int originX, int originY) { for (int y = 0; y < level.Height; y++) { for (int x = 0; x < level.Width; x++) level.Visible[y][x] = false; } for (int y = originY - FOV_RADIUS; y <= originY + FOV_RADIUS; y++) { for (int x = originX - FOV_RADIUS; x <= originX + FOV_RADIUS; x++) { if (!level.InBounds(x, y)) continue; int dx = x - originX; int dy = y - originY; if (dx * dx + dy * dy > FOV_RADIUS * FOV_RADIUS + FOV_RADIUS) continue; if (LineOfSight(level, originX, originY, x, y)) { level.Visible[y][x] = true; level.Seen[y][x] = true; } } } }}MapScreen calls it in update, after every command. Drawing the map shows the camera and the fog together: a cell that has never been seen is skipped (continue), a visible one is in its own color, and a seen one is gray:
public override void Draw(CellBuffer buffer){ Game game = Game; Level level = game.Level()!; Hero hero = game.Hero; int cameraX = Clamp(hero.X - VIEW_WIDTH / 2, 0, level.Width - VIEW_WIDTH); int cameraY = Clamp(hero.Y - VIEW_HEIGHT / 2, 0, level.Height - VIEW_HEIGHT); for (int viewY = 0; viewY < VIEW_HEIGHT; viewY++) { for (int viewX = 0; viewX < VIEW_WIDTH; viewX++) { int x = cameraX + viewX; int y = cameraY + viewY; if (!level.Seen[y][x]) continue; Glyph cell = CellLook(level, x, y); buffer.Put(viewX, viewY, cell.Ch, level.Visible[y][x] ? cell.Color : "gray"); } } buffer.Put(hero.X - cameraX, hero.Y - cameraY, '@', "white"); DrawSidePanel(buffer, level); DrawHud(buffer, game, VIEW_HEIGHT); DrawMessages(buffer, game, VIEW_HEIGHT + 2, 3);}Here is the frame where the hero opens the door to the big hall on the first level. Through the open door you see a wedge of the hall, and a giant rat in it:
######## The upper gallery#<.....# .... Level 1 of 3#.....@'....r#......# .... Around:#......# .. r giant rat########
Iva, barbarian lv1 xp 0/20 gold 5L [############] 48/48 M [########] 4/4The door creaks open.Giant rat notices you!You see: giant rat.More precisely, if you are curious
In a plain terminal (--plain), seen and visible cells look the same: the character is the same, and there is no color. In a terminal with ANSI colors, seen cells are gray. That is why the program in this lesson uses : for the fog: so you can see the difference without colors.
What does it cost? The circle with radius 6 has 137 cells, and the line to each one is at most 6 steps: under 1,000 checks per turn. That is O(r³) per turn: r² cells times r steps.
Try it
Predict the output
A small room with a pillar in the middle. The hero is to the left of the pillar, and the radius reaches every cell. What does the program print?
string room = """ ####### #.....# #@.#..# #.....# ####### """;var level = new Level(room);var visible = new bool[level.Height, level.Width];var seen = new bool[level.Height, level.Width];ComputeFov(level, visible, seen);PrintSight(level, visible, seen);The pillar casts a shadow: the cells behind it on the right are not visible, and the shadow spreads toward the corners. The walls are visible, except those where the line passes through the pillar or through another wall. The output where everything is visible is the radius alone; the output without walls has the swapped checks from the next exercise.
Try it
Find the bug
A colleague touched the line function, and now the program prints this from the start:
static bool LineOfSight(Level level, int x0, int y0, int x1, int y1){ int dx = Math.Abs(x1 - x0); int dy = -Math.Abs(y1 - y0); int stepX = x0 < x1 ? 1 : -1; int stepY = y0 < y1 ? 1 : -1; int error = dx + dy; int x = x0; int y = y0; while (true) { if ((x != x0 || y != y0) && level.At(x, y).Opaque) return false; if (x == x1 && y == y1) return true; int doubled = 2 * error; if (doubled >= dy) { error += dy; x += stepX; } if (doubled <= dx) { error += dx; y += stepY; } }}hero (6, 3): you see 30, you remember 30| || ...... || ...... || ...~~@ || ...~~. || ...... || |The floor is visible, the door and the walls are gone, and the water is as before. Which line checks too early?
Pick the line with the bug.
The wall check comes before the "have we arrived" check. When the line reaches a wall that is itself the target, it first asks "is there a wall here" and returns "not visible". That is why exactly the walls and the closed door disappear. The right order is: first "have we arrived", then "is there a wall on the way". Then the line reaches the wall and stops after it.
More precisely
The weak spots of the simple method
A line to every cell is the simplest field of view. It has three well-known weak spots, and all of them show up in our game.
Holes next to walls. Look again at the first frame from the start: the hero is next to the door, and the wall at (7, 1) and (7, 5) is not visible, although the floor next to it is. The line to (7, 1) takes its first step diagonally and lands on the door at (7, 2): it stops. The same thing is in the frame from the mine at the start of the lesson: the hero is next to the left wall, and it has a hole. When you look at a wall almost along its length, the line runs into the neighboring cell of the same wall.
Asymmetry. From A you see B, but from B you do not see A, because the line back passes through other cells (you saw it with 4,2 and 4,1). On the first level of the mine there are 89 such pairs of cells out of 17248: from (12, 4) you can see (14, 8), but not the other way around. In the canon this has consequences. An enemy looks with its own line, from itself to the hero (enemySeesHero, up to 8 cells), and you see with the field of view from the hero. So a goblin can notice you before you see it. At least the game does not reveal more than you see: the message that an enemy woke up is shown only if the enemy is visible.
The cheaper variant leaves holes in halls. Instead of a line to every cell, you can send lines only to the edge of the circle and mark everything along the way. That is O(r²) instead of O(r³). But the rays spread apart with distance, and cells between them are left uncovered: at radius 6 there are 8 of 137, and at radius 20 there are 80 of 1313. In a big hall these are holes in the floor and in the far walls.
Better algorithms. Shadowcasting walks the eight sectors around the hero row by row and keeps the "shadows" as ranges of slopes. Every cell is looked at once, there are no holes, and there is also symmetric shadowcasting, where A sees B exactly when B sees A. Permissive FOV says a cell is visible if some straight line from some point of the hero's cell to some point of the target is clear. It is symmetric by definition and sees more around corners.
Why the canon keeps the simple one. The levels are 50 × 20 and the radius is 6: under 1,000 checks per turn, nothing for any computer. Whole numbers give the same result in all four languages, and that is how the ports are checked. And it fits in one card. If the game ever gets big open areas and long sight lines, computeFov is replaced in one place.
Exercise
The secret door
Solve this in your editor.
A secret door. Add a tile ?: it looks like a wall (it is drawn as #), you cannot walk on it and it blocks sight. When the hero bumps into it, it becomes a closed door + and the program prints "The wall sounds hollow... A secret door!". The next bump opens it, like any door. The level is:
#################......#.......##......+.......##...~~@#....>..##...~~.?.......##......#.......#################With the input s d d d d (one per line) the output is:
> s#################......#.......##......+.......##...~~.#....>..##...~~@#.......##......#.......#################> d The wall sounds hollow... A secret door!#################......#.......##......+.......##...~~.#....>..##...~~@+.......##......#.......#################> d The door creaks open.#################......#.......##......+.......##...~~.#....>..##...~~@'.......##......#.......#################> d#################......#.......##......+.......##...~~.#....>..##...~~.@.......##......#.......#################> d#################......#.......##......+.......##...~~.#....>..##...~~.'@......##......#.......#################More exercises
- A torch. Make the radius a parameter. With a torch the hero sees 6 cells, without one 2. How much of the left room does the hero see from the start without a torch?
- The view and the fog together. Combine the camera and the field of view: a 9 × 5 view on the level that shows visible, seen (
:) and unknown cells, likedrawin the game. - Who sees whom. Write a program that counts, on this lesson's level, the pairs of floor cells where one sees the other but not the other way around.
Test