Конспект: карта мира

Понятия

Случайный остов - остов, который строит Крускал по рёбрам в случайном порядке: связен, без циклов, ровно V − 1 ребро. Генератор пещер на нём обещает связность по построению.

Критический мост - ребро, после удаления которого граф распадается. Остров-узел (точка сочленения) - вершина с тем же свойством.

Честная эвристика - оценка остатка пути не больше настоящей; при ней A* находит кратчайший путь.

Метки компонент - номер компоненты у каждой клетки, один обход на карту; «достижима ли цель» - сравнение двух чисел.

Прямая Брезенхема - клетки «прямой» на сетке: шаг по длинной оси, целочисленная ошибка решает шаг по короткой.

Что унести

ГЕНЕРАЦИЯ
стены в случайном порядке, ломать только между несвязанными залами
6 × 10 залов: 104 стены, сломано 59 = 60 - 1, компонента одна
мосты между 9 островами: к ближайшему 232 (две группы!),
          случайный остов 654, Крускал 311
кольца для игры: после остова сломать ещё несколько стен

КРИТИЧЕСКИЕ МОСТЫ И УЗЛЫ
tin - время входа, low - самое раннее, куда дотянется поддерево
мост v - to критичен:  low[to] >  tin[v]
остров v - узел:       low[to] >= tin[v] (корень - если детей >= 2)
пропускать РЕБРО, по которому пришли, а не вершину
15 мостов: наивно 378 проверок, один DFS 30
большая карта: обход со стеком, не рекурсией

ПУТЬ ОТРЯДА
f = g + h; h честна, если не больше остатка
клетки: манхэттен × цена САМОЙ ДЕШЁВОЙ клетки
20 × 20: Дейкстра 359 раскрыто, A* 258, оба цена 46
h × 3: 41 раскрыто, цена 52 (не дороже 3 · кратчайшего)
цель недостижима: A* обходит всю компоненту (337) - метки до поиска

ТУМАН ВОЙНЫ
видно, если на прямой между нет гор; гору саму видно
обзор радиуса R: (2R + 1)² прямых длиной до R ~ R³
R = 6: 169 клеток, видно 83, 728 клеток прямых
несимметрично: 36 пар из 374; от меньшего номера к большему - 0

Ловушки джокера

Связность вероятностью. Генератор «ломает стены с вероятностью 1/2» - и где-то зал замурован.

«Мост к ближайшему». Дёшево и связно на вид, а архипелаг из двух частей.

Пропуск вершины вместо ребра. Двойная переправа объявлена стратегическим мостом.

Эвристика по типичной клетке. Дорога ценой 0,5 появилась - отряды перестали ею пользоваться.

Поиск в отрезанную цель. Каждый клик по острову за проливом обходит материк.

Брезенхем в одну сторону. Лучник стреляет из невидимости - игроки зовут это читом.