Към съдържанието
wannacode

Картата и гледането

Накратко: Полето на видимост е множеството клетки, които героят вижда: до всяка клетка в обхвата се прекарва линия на Bresenham, стената я спира, а видяното веднъж остава на картата като мъгла.

Проблем

Шефът се вижда от входа

Първото ниво на мината е 50 × 20 клетки, а картата на екрана е 40 × 13. Цялото ниво не се събира. И да се събираше, не бива да се вижда цялото: ако от входа виждаш Пазача на дълбините и всеки сандък, няма какво да откриваш.

Затова играта показва само това, което героят вижда, и помни видяното. Ето първия кадър, когато героят слезе в мината (от минаването, с което се проверява играта):

###                                      Горната галерия
#@.....#                                 Ниво 1 от 3
#......+
 ......#                                 Наоколо:
 ......                                  никой
 ######














Ива, варварин ур.1  опит 0/20  злато 5
Ж [############] 48/48   М [########] 4/4
Нов куест: „Кървавата следа“.
Нов куест: „Сребро за ковачката“.
Ти си в „Горната галерия“, ниво 1.

Стаята и вратата се виждат. Коридорът и залата зад вратата ги няма, макар че са на пет-шест клетки. За този кадър трябват пет неща: карта от текст, движение със сблъсък, камера, поле на видимост и мъгла. Урокът ги строи едно по едно на малко ниво 16 × 7, а после показва същото място в играта.

Идеята

Нивото е текст

Нивото на урока е 16 × 7:

################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################

Всеки знак е клетка: # стена, . под, + затворена врата, ~ вода, > стълби надолу, @ героят. Кодът не знае каква е формата на нивото. Той чете текста. Ново ниво е нов текст, без нито ред нов код.

За движението и гледането клетката трябва да отговори на два въпроса: минава ли се и спира ли погледа. Двата отговора не вървят заедно. През водата се вижда, но не се минава. Затворената врата и спира погледа, и не пуска. Затова плочката е запис със знак, име и двата отговора, а таблицата от плочки е данни:

record Tile(char Glyph, string Name, bool Walkable, bool Opaque);


class Level
{
    public static readonly List<Tile> Tiles =
    [
        new('#', "стена", false, true),
        new('.', "под", true, false),
        new('+', "врата", false, true),
        new('\'', "отворена врата", true, false),
        new('~', "вода", false, false),
        new('>', "стълби", 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("Непозната клетка: " + glyph);
    }


    public bool InBounds(int x, int y) => x >= 0 && y >= 0 && x < Width && y < Height;


    // Извън картата е стена: никой не излиза и никой не гледа навън.
    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("Нивото е " + level.Width + " × " + level.Height + ", героят е на (" + 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 ? "да" : "не";
    string sight = tile.Opaque ? "да" : "не";
    Console.WriteLine(tile.Glyph + " " + tile.Name + ": " + count + ", минава се: " + walk + ", спира погледа: " + sight);
}
Изход
Нивото е 16 × 7, героят е на (6, 3).
# стена: 46, минава се: не, спира погледа: да
. под: 60, минава се: да, спира погледа: не
+ врата: 1, минава се: не, спира погледа: да
~ вода: 4, минава се: не, спира погледа: не
> стълби: 1, минава се: да, спира погледа: не

At(x, y) връща стена за всичко извън картата. Така нито движението, нито гледането трябва да проверяват границите: никой не излиза от картата, защото навън е стена.

В C# решетката е Tile[,]: един правоъгълен масив с индекс [y, x]. Канонът ползва масив от масиви ([y][x]), както в другите езици; за програмите тук правоъгълният е по-кратък.
По-точно, за любопитните

В решетката има 112 клетки, но плочките са само шест обекта. Всяка клетка пази препратка към една от тях, затова броенето по-горе сравнява с ==. Когато вратата се отвори, клетката просто започва да сочи друга плочка. Това е шаблонът „споделени леки обекти“ (flyweight): общото (името, свойствата) е на едно място, а мястото на картата е в решетката.

В канона клетките са знаци, а свойствата са два малки метода: isWalkable и isOpaque. Идеята е същата, формата е по-проста, защото видовете са осем и свойствата са две. Ако добавиш още (цена на движение, шум, светлина), таблицата пак печели.

Идеята

Нивата в играта

Трите нива на мината са в един текст в кода на играта. Всяко започва с ред level|1|… (дълбочината и името на четирите езика), после идват редовете на картата, легендата и end. Ето първото ниво без заглавния ред:

##################################################
#<.....#............#........1.#..~~~~~.......2..#
#......+....r.......+......g...#..~~~~~..........#
#......#............#..........+..~~~~~..........#
#......#............#..........#.........,.......#
########.........r..############........,........#
########............############........,........#
##############.#########################,#########
##############.#########################.#########
##############.#########################,#########
###....#.3............#########.........,...######
###.4..?.........s....+..................,..######
###....#...g..........#########..........,..######
########..............###################+########
##############.###############........5555555....#
##......................######............,......#
##..................r...######..............,L...#
##.>....................######......w............#
##......7...............######.................6.#
##################################################
legend|1|item|potion_heal|1
legend|2|gold|25|0
legend|3|item|antidote|1
legend|4|item|ring_life|1
legend|5|marker|lair|0
legend|6|gold|30|0
legend|7|item|potion_heal|1
end

Освен плочките има още знаци. Буквите (r, g, s, L) са врагове от таблицата на враговете. Цифрите са от легендата под картата: предмет, злато, знак за куест. < е мястото, където героят слиза. ? е тайна врата, която изглежда като стена. , е кръв по пода.

// Картата е текст: редовете между „level|…“ и „legend|…“ са самата карта, легендата казва какво
// значи всяка цифра. Тук само се четат определенията; живото ниво се строи в 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);
            }
        }
    }
}

Четенето е на две стъпки. loadMaps само разделя текста на определения. Живото ниво се строи с buildLevel при нова игра (и при зареждане): буквите стават врагове, цифрите стават предмети, а под тях остава под. Затова в решетката на нивото няма гоблин. Съществата са отделен списък и се движат по картата, а картата стои.

Идеята

Ходът е молба

Най-простият ход е heroX += dx. С него героят минава през стени и излиза от картата. Ходът трябва да е молба: „искам да вляза там“. Клетката, в която иска да влезе, решава:

// Ходът е молба: клетката, в която искаш да влезеш, решава.
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 "Вратата изскърцва и се отваря.";
    }
    if (!target.Walkable) return "Не минаваш: " + target.Name + ".";
    level.HeroX = x;
    level.HeroY = y;
    return "";
}
  • стена или вода: не, и казва защо;
  • затворена врата: отваря се (става '), но героят остава на мястото си. Отварянето е ходът;
  • всичко друго: героят влиза.

Програмата чете команди w a s d (горе, ляво, долу, дясно), по една на ред, и след всяка рисува нивото. Входът е 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  Не минаваш: стена.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> a  Не минаваш: вода.
################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.#.......#
#......#.......#
################
> w
################
#......#.......#
#.....@+.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d  Вратата изскърцва и се отваря.
################
#......#.......#
#.....@'.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......@.......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################
> d
################
#......#.......#
#......'@......#
#...~~.#....>..#
#...~~.#.......#
#......#.......#
################

Първите два хода са в стена и във вода: героят стои. После тръгва нагоре, отваря вратата и минава.

В играта стъпката прави повече неща и редът им е важен:

// Стъпка на героя: бой, разговор, врата, тайник, стена или движение.
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";
}

Първо се пита за враг: врагът стои върху под, и ако плочката решаваше първа, героят щеше да влезе в него. После за човек (разговор), врата, тайна врата, и чак тогава за плочката. Когато героят наистина се премести, кърви ли, оставя кръв по пода, събитието TileEntered казва на куестовете къде е, а накрая светът прави своя ход.

Блъскането в стена връща blocked и не вика worldTurn: грешката на играча не струва ход и враговете не се приближават. Вратата струва ход.

По-точно, за любопитните

Тук водата просто не пуска. В много игри плитката вода пуска, но бавно: всяка плочка има цена на движение (подът 1, плитката вода 2, блатото 3), и героят трупа енергия, докато стигне цената, като енергията в боя (урокът за бойната система). Тогава walkable става число вместо да/не. Търсенето на път също трябва да знае цените: тогава BFS не стига и трябва Dijkstra.

Идеята

Камерата

Нивото на играта е 50 × 20, а изгледът е 40 × 13. Камерата е светът, видян през прозорец: cameraX и cameraY са клетката от света, която е в горния ляв ъгъл на екрана. От тях двете посоки са едно събиране:

  • от света към екрана: screenX = x − cameraX;
  • от екрана към света: x = cameraX + screenX.

Камерата следва героя: героят е в средата, затова cameraX = heroX − VIEW_W / 2. Близо до ръба на картата това дава отрицателно число или изглед, който излиза от картата. Затова камерата се затяга (clamp) между 0 и width − VIEW_W. Там изгледът спира, а героят тръгва към ръба на екрана.

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($"герой ({level.HeroX}, {level.HeroY}), камера ({cameraX}, {cameraY}), на екрана ({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));
    }
}

Програмата ползва изглед 9 × 5 върху нивото 16 × 7 и печата изгледа след всяка отсечка от пътя на героя:

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);
}
Изход
герой (6, 3), камера (2, 1), на екрана (4, 2)
.....#...
.....+...
..~~@#...
..~~.#...
.....#...
герой (9, 2), камера (5, 0), на екрана (4, 2)
#########
..#......
..'.@....
~.#....>.
~.#......
герой (14, 2), камера (7, 0), на екрана (7, 2)
#########
#.......#
'......@#
#....>..#
#.......#
герой (14, 5), камера (7, 2), на екрана (7, 3)
'.......#
#....>..#
#.......#
#......@#
#########

Първите два изгледа са центрирани: героят е на (4, 2) на екрана. В третия камерата е стигнала дясното ограничение 16 − 9 = 7 и спира, а героят продължава към ръба. В четвъртия камерата е спряла и отдолу.

VIEW_W / 2 е цяло деление: 9 / 2 = 4.
int cameraX = Clamp(level.HeroX - VIEW_W / 2, 0, );
По-точно, за любопитните

Ако нивото е по-тясно от изгледа, width − VIEW_W е отрицателно, и според мястото на героя clamp връща 0 или отрицателно число: камерата скача или излиза отляво на картата. В канона това не се случва, защото и трите нива са 50 × 20, но в игра с малки стаи нивото се центрира в изгледа: cameraX = (width − VIEW_W) / 2.

Камерата, която се мести с всяка стъпка, кара целия екран да подскача. Много игри държат мъртва зона: камерата мърда едва когато героят излезе от правоъгълник в средата. В конзолата, ход по ход, това рядко трябва; в игра с плавно движение е задължително.

В играта е същото с 40 × 13. Ето кадър по-надолу в първото ниво: камерата е слязла, затова горните редове на нивото не се виждат:

########............############........ Горната галерия
       #............#          #........ Ниво 1 от 3
       #######.#####           #########
                                       # Наоколо:
                 ######       ########## никой
              ........#########.........
              ...%.%@.'.................
              ........#########.........
              ........#       ##########
               ########                .
                                     ...
                                    ....
                                    ....
Ива, варварин ур.2  опит 40/55  злато 30
Ж [############] 57/57   М [########] 5/5
Гоблин копиеносец те забелязва!
Победа! Опит от боя: 21.
Ива стига ниво 2: ново умение: Вихър (клон Ярост).

Идеята

Първият опит: радиус

Героят трябва да вижда около себе си. Първата идея е радиус: виждаш всяка клетка, която е по-близо от 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 е „виждам сега“. seen е „виждал съм някога“ и се ползва по-късно за мъглата. Ето какво вижда героят от старта:

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);
Изход
герой (6, 3): виждаш 87, помниш 87
| ###########    |
|#......#.....   |
|#......+.....   |
|#...~~@#....>   |
|#...~~.#.....   |
|#......#.....   |
| ###########    |

Виждат се 87 клетки и сред тях стълбите (>) зад стената. Затворената врата не пречи. Радиусът знае колко е далеч клетката, но не и какво има между нея и героя. Това е шефът, който се вижда от входа.

По-точно, за любопитните

Защо условието е dx² + dy² ≤ R² + R, а не ≤ R²? При ≤ R² от кръга стърчат четири самотни клетки: (R, 0), (0, R) и симетричните им. Добавката + R го закръгля: за цели числа dx² + dy² ≤ R² + R е същото като разстояние до центъра на клетката под R + ½, защото (R + ½)² = R² + R + ¼. Без корен квадратен и без дробни числа.

Идеята

Права линия: Bresenham

Една клетка се вижда, ако правата линия от героя до нея не минава през стена. На решетка правата линия е поредица от клетки, и трябва да решиш кои. Алгоритъмът на Bresenham го прави само с цели числа: събиране, изваждане и умножение по 2.

Идеята: тръгваш от началото и на всяка стъпка правиш крачка по x, по y или и по двете. Коя, казва error: колко се е отклонила линията от истинската права. Когато отклонението по едната ос стане голямо, правиш крачка по нея и го намаляваш.

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;
        }
    }
}

Програмата чертае линията от A = (0, 0) до B = (8, 3), а после и обратно, от B до 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,3
B → A: 8,3 7,3 6,2 5,2 4,1 3,1 2,1 1,0 0,0
A*.......
..**.....
....***..
.......*B

Двете посоки минават почти през същите клетки, но не съвсем: отиване минава през 4,2, а връщане през 4,1. На средата грешката е точно наравно, и алгоритъмът избира едната страна. Обратно изборът е другата. Запомни това: ще ни трябва в слабостите на метода.

По-точно, за любопитните

Откъде е error = dx + dy (с dy отрицателно)? Правата през двата края е f(x, y) = 0, където f е линейна, а знакът на f казва от коя страна си. error е f, умножено така, че да е цяло число, в точката, която би била следващата. Проверките 2 · error ≥ dy и 2 · error ≤ dx питат дали крачката по x, съответно по y, приближава линията. Затова алгоритъмът върви и в осемте посоки и не дели никъде.

Джак Брезенхам го измисля в IBM през 1962 г. за плотер: машината мести писалката само с една стъпка, а деленето е скъпо. Днес деленето не е скъпо, но целите числа дават един и същ резултат на всеки компютър и всеки език, а това за нашата игра е задължително.

Виж го

Поле на видимост и мъгла

Сега двете се събират. За всяка клетка в радиуса тръгва линия на Bresenham. Линията проверява две неща на всяка крачка: стигнахме ли и стена ли е тук. Редът им е важен. Ако е стигнала целта, клетката се вижда, дори да е стена. Ако по пътя преди целта има стена, линията спира: клетката не се вижда.

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;
            }
        }
    }
}
Стъпка по стъпка, с думи
  1. Героят е на (6, 3). Полето се смята наново всеки ход и първо всяка клетка става невидима. Още нищо не е видяно: цялото ниво е непознато.
  2. Кандидатите са клетките в радиус 6: dx² + dy² ≤ 6² + 6. Те са 87, заедно със стаята зад стената. Радиусът не знае за стени.
  3. Към всеки кандидат тръгва права линия (Bresenham). Тя спира на първата стена по пътя, но стига до нея, затова самата стена се вижда. 37 линии спират по-рано (сивите).
  4. От (6, 3) виждаш 50 клетки и всички влизат в seen. Стаята вдясно е в радиуса, но затворената врата и стената я крият: стълбите остават непознати.
  5. Героят отваря вратата и минава (wdddddd). Всеки ход visible се чисти, а seen остава: видяното, което вече не виждаш, става мъгла.
  6. От (11, 2) линиите минават през отворената врата. В лявата стая се вижда само тесен клин: стената крие останалото.
  7. Виждаш 63, помниш 109 от 112 клетки. Мъглата пази формата на лявата стая, но не и какво става в нея сега.

Всеки ход visible се чисти и се смята наново, а seen само се пълни. Програмата рисува видимото със знака му, видяното, което вече не се вижда, с :, а непознатото празно. Първо от старта, после след 7 хода (горе, вратата, пет пъти надясно):

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);
Изход
герой (6, 3): виждаш 50, помниш 50
| ######         |
|#......         |
|#......+        |
|#...~~@#        |
|#...~~.#        |
|#......         |
| ######         |
герой (11, 2): виждаш 63, помниш 109
| :::::::####### |
|:::::::#.......#|
|:::::..'...@...#|
|:::::::#....>..#|
|:::::::#.......#|
|:::::::#.......#|
| ::::::#########|

Отначало стълбите не се виждат: стената и затворената врата ги крият. След като героят мине, лявата стая е мъгла. Той знае каква е, но не вижда какво става в нея: враг, който влезе там, няма да се появи на екрана.

В играта полето е същият код, на същото място в хода:

// Поле на видимост: клетка се вижда, ако е в радиуса и линията до нея (Bresenham) не минава
// през стена или затворена врата. Видяното се помни: това е мъглата.
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 го вика в update, след всяка команда. Рисуването на картата пък показва камерата и мъглата наведнъж: клетка, която никога не е видяна, се прескача (continue), видимата е в цвета си, а видяната е сива:

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);
}

Ето кадъра, в който героят отваря вратата към голямата зала на първото ниво. През отворената врата се вижда клин от залата, а в него гигантски плъх:

########                                 Горната галерия
#<.....# ....                            Ниво 1 от 3
#.....@'....r
#......# ....                            Наоколо:
#......#   ..                            r гигантски плъх
########














Ива, варварин ур.1  опит 0/20  злато 5
Ж [############] 48/48   М [########] 4/4
Вратата изскърцва и се отваря.
Гигантски плъх те забелязва!
Виждаш: гигантски плъх.
По-точно, за любопитните

В обикновения терминал (--plain) видяното и видимото изглеждат еднакво: знакът е същият, а цветът липсва. В терминал с ANSI цветове видяното е сиво. Затова програмата в урока ползва : за мъглата: да се вижда разликата и без цветове.

Колко струва? Кръгът с радиус 6 има 137 клетки, а линията до всяка е най-много 6 крачки: под 1000 проверки на ход. Това е O(r³) на ход: r² клетки по r крачки.

Пробвай

Предвиди изхода

Малка стая с колона в средата. Героят е вляво от колоната, а радиусът стига до всяка клетка. Какво печата програмата?

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);
Отговор

Пробвай

Намери грешката

Колега пипна линията и сега от старта програмата печата това:

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;
        }
    }
}
Изход
герой (6, 3): виждаш 30, помниш 30
|                |
| ......         |
| ......         |
| ...~~@         |
| ...~~.         |
| ......         |
|                |

Подът се вижда, вратата и стените са изчезнали, а през водата е както преди. Кой ред проверява твърде рано?

Избери реда с грешката.

По-точно

Слабостите на простия метод

Линия до всяка клетка е най-простото поле на видимост. Има три известни слабости, и всичките се виждат в нашата игра.

Дупки до стените. Погледни пак първия кадър от старта: героят е до вратата, а стената на (7, 1) и (7, 5) не се вижда, макар че подът до нея се вижда. Линията до (7, 1) прави първата си крачка по диагонал и стъпва на вратата (7, 2): спира. Същото е в кадъра от мината в началото на урока: героят е до лявата стена и тя има дупка. Когато гледаш стена почти по дължината ѝ, линията опира в съседната клетка от същата стена.

Асиметрия. От A виждаш B, а от B не виждаш A, защото линията обратно минава през други клетки (видя го с 4,2 и 4,1). На първото ниво на мината такива двойки клетки са 89 от 17248: от (12, 4) се вижда (14, 8), а обратно не. В канона това има последствия. Врагът гледа със своя линия, от себе си към героя (enemySeesHero, до 8 клетки), а ти виждаш с полето от героя. Затова гоблин може да те забележи, преди ти да го видиш. Играта поне не издава повече, отколкото виждаш: съобщението, че врагът се е събудил, се пише само ако той е във видимото.

По-евтиният вариант има дупки в залите. Вместо линия до всяка клетка може да пускаш линии само до ръба на кръга и да отбелязваш всичко по пътя им. Това е O(r²) вместо O(r³). Но лъчите се разминават с разстоянието и между тях остават непокрити клетки: при радиус 6 те са 8 от 137, а при радиус 20 са 80 от 1313. В голяма зала това са дупки в пода и в далечните стени.

По-добрите алгоритми. Shadowcasting обхожда осемте сектора около героя ред по ред и пази „сенките“ като интервали от наклони. Всяка клетка се поглежда веднъж, няма дупки, а има и симетрично shadowcasting, при което A вижда B точно когато B вижда A. Permissive FOV казва, че клетката се вижда, ако някоя права от някоя точка на клетката на героя до някоя точка на целта е свободна. Той е симетричен по определение и вижда повече около ъглите.

Защо канонът пази простия. Нивата са 50 × 20, а радиусът е 6: под 1000 проверки на ход, нищо за който и да е компютър. Целите числа дават един и същ резултат на четирите езика, а това е проверката на портовете. И се обяснява в една карта. Ако играта стане с големи открити пространства и далечно гледане, тогава смяната на computeFov е на едно място.

Упражнение

Тайната врата

Реши задачата в редактора си.

Тайна врата. Добави плочка ?: изглежда като стена (рисува се #), не се минава и спира погледа. Когато героят се блъсне в нея, тя става затворена врата + и програмата пише „Стената кънти на кухо... Тайна врата!“. Следващото блъскане я отваря, както всяка врата. Нивото е:

################
#......#.......#
#......+.......#
#...~~@#....>..#
#...~~.?.......#
#......#.......#
################

С вход s d d d d (по един на ред) изходът е:

Изход
> s
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@#.......#
#......#.......#
################
> d  Стената кънти на кухо... Тайна врата!
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@+.......#
#......#.......#
################
> d  Вратата изскърцва и се отваря.
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~@'.......#
#......#.......#
################
> d
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~.@.......#
#......#.......#
################
> d
################
#......#.......#
#......+.......#
#...~~.#....>..#
#...~~.'@......#
#......#.......#
################

Още задачи

  • Факла. Направи радиуса параметър. Героят с факла вижда на 6, без факла на 2. Каква част от лявата стая вижда от старта без факла?
  • Изгледът и мъглата заедно. Събери камерата и полето: изглед 9 × 5 върху нивото, който показва видимото, видяното (:) и непознатото, както draw в играта.
  • Кой кого вижда. Напиши програма, която за нивото на урока брои двойките подови клетки, от които едната вижда другата, а обратното не.

Тест

Провери се

1. В играта героят се блъска в стена и нищо не става. Отваря врата и враговете правят ход. Защо е различно?
2. Нивото е 50 × 20, изгледът е 40 × 13, героят е на x = 47. Колко е cameraX?
3. Стената спира погледа. Защо тогава самата стена се вижда?
4. Кое е вярно за visible и seen?
5. В играта от клетка A виждаш клетка B, а от B не виждаш A. Как е възможно?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·