# `$.nav` — навигация и поиск пути

Подсистема поиска пути: прямоугольная сетка препятствий, A* (8 направлений),
сглаживание маршрута и агент, который идёт к цели по кадрам. Аналог
`AStarGrid2D` + `NavigationRegion2D`/`NavigationAgent2D` из Godot 4.

Путь можно строить двумя способами:

* **клеточная сетка** (`$.nav.grid`) — препятствия задаются клетками, A* по
  клеткам, сглаживание «видимостью»;
* **навигационный меш** (`$.nav.mesh`) — свободное пространство режется на
  **прямоугольники** (не треугольники!), соседи связываются порталами, путь
  идёт по графу прямоугольников и натягивается воронкой. Прямоугольников
  меньше, чем клеток, а путь получается глаже — навмеш лучше подходит для
  больших арен со сложной геометрией.

Ядро (A*, сглаживание, декомпозиция, порталы, воронка) — чистая математика
над массивами и экспортируется наружу; всё остальное — обвязка над
`$.world`/физикой.

```js
$.ready(() => {
    $.nav.clear();
    const grid = $.nav.grid({ x: 0, y: 0, w: 2048, h: 1024, cell: 32, diagonal: true });

    // Стены уже в мире — превращаем их в препятствия сетки.
    grid.buildFromWalls({ tags: ['wall'], inset: 2 });

    $('#guard').navigateTo('#hero', { speed: 180, grid, repathEvery: 300 });
});
```

---

## 1. Сетка

### `$.nav.grid(opts) → grid`

Создаёт сетку. `x`/`y` — **левый верхний угол** в мировых пикселях, `w`/`h` —
размеры. Возвращает объект сетки либо `null`, если размеры не заданы.

| Поле | Тип | По умолчанию | Смысл |
|---|---|---|---|
| `x`, `y` | число | `0` | Левый верхний угол сетки в мире |
| `w`, `h` | число | — | Размер области в пикселях (обязательны) |
| `cell` | число | `32` | Сторона клетки |
| `diagonal` | bool | `true` | Разрешить шаги по диагонали |
| `heuristic` | `'manhattan'`\|`'euclidean'`\|`'octile'` | `'manhattan'` | Эвристика A* |
| `weights` | массив/число/функция | — | Добавочная стоимость клетки (0 — непроходимо) |

Первая созданная сетка становится сеткой **по умолчанию** для `$.nav.path`
без `opts.grid`. Переключить — `$.nav.use(grid)`.

При `diagonal: true` берите `heuristic: 'octile'` (или `'euclidean'`):
манхэттенская оценка на диагоналях завышена и путь перестаёт быть
оптимальным.

### Методы сетки

| Метод | Что делает |
|---|---|
| `.blockAt(worldX, worldY)` | Закрыть клетку под мировой точкой |
| `.freeAt(worldX, worldY)` | Открыть клетку под мировой точкой |
| `.setBlocked(cx, cy, bool)` | Закрыть/открыть клетку по индексам |
| `.isBlocked(cx, cy)` | Стена ли клетка (за границей сетки — всегда стена) |
| `.worldToCell(wx, wy)` | Мир → `{ cx, cy }` |
| `.cellCenter(cx, cy)` | Центр клетки в мировых координатах |
| `.inBounds(cx, cy)` | Внутри ли сетки |
| `.nearestFreeCell(cx, cy, maxRadius)` | Ближайшая свободная клетка или `null` |
| `.buildFromWalls({ tags, inset })` | Собрать препятствия из узлов мира |
| `.rebuild()` | Повторить последнюю сборку |
| `.clear()` | Снять все препятствия |
| `.lineOfSight(from, to)` | Прямая видимость по этой сетке |
| `.path(from, to, opts)` | Путь в мировых точках |

### `buildFromWalls({ tags, inset })`

Собирает препятствия двумя способами сразу:

1. узлы по селекторам `tags` (по умолчанию `['wall']`) — включая узлы **без
   физического тела**, по их габаритам (`nodeBounds`);
2. все **статические/кинематические тела**, попавшие в габарит сетки
   (`$.world.bodiesIn`) — поэтому препятствием становится и стена без тега
   `<wall>`.

`inset` (пиксели) сжимает габарит каждого препятствия с каждой стороны —
удобно заложить радиус агента. Если препятствие тоньше `2*inset`, стеной
остаётся хотя бы его центральная клетка.

```js
grid.buildFromWalls({ tags: ['wall', '.obstacle'], inset: 4 });
```

`buildFromWalls` и `rebuild()` сбрасывают ручные пометки, поставленные
`setBlocked`/`blockAt` **до** вызова. Ставьте их после пересборки.

### `$.nav.clear()`

Убирает все сетки (и сетку по умолчанию). Уже созданные игрой ссылки на
объекты сетки продолжают работать — просто они больше не находятся в реестре.

---

## 2. Поиск пути

### `$.nav.path(from, to, opts) → [ {x, y}, … ] | null`

Путь по сетке по умолчанию (или `opts.grid`) в мировых координатах.
Первая точка — ровно `from`, последняя — ровно `to`. Если путь не найден —
`null`.

| `opts` | По умолчанию | Смысл |
|---|---|---|
| `grid` | сетка по умолчанию | По какой сетке искать |
| `smooth` | `true` | Убрать лишние изломы |
| `allowPartial` | `false` | Дойти до ближайшей достижимой клетки, если цель недостижима |
| `maxIterations` | `cols*rows` | Предохранитель от долгого поиска |
| `startSearch` | `8` | Радиус поиска свободной клетки, если старт оказался в стене |

`from`/`to` принимают `{ x, y }`, узел, id/строку-селектор или обёртку.

```js
const p = $.nav.path('#guard', { x: 900, y: 400 }, { smooth: true });
```

### `$.nav.pathOn(grid, from, to, opts)`

То же, но сетка задаётся первым аргументом. Без сглаживания и с явным лимитом:

```js
$.nav.pathOn(grid, a, b, { smooth: false, maxIterations: 2000, allowPartial: true });
```

### `$.nav.lineOfSight(from, to, grid) → bool`

Прямая видимость по клеткам, без физики. Стартовая клетка не считается (агент
может стоять вплотную к стене), конечная — считается. Отрезок, проходящий
ровно через угол между двумя стенами, видимости не даёт.

```js
if ($.nav.lineOfSight('#guard', '#hero', grid)) $('#guard').lookAt('#hero');
```

`grid` можно не передавать — возьмётся сетка по умолчанию.

### Чистые функции (экспортируются из `nav.js`)

Их гоняет qjs-тест без движка — см. `tests/js/nav_test.mjs`.

```js
import { astar, smoothPath, lineOfSight, makeGrid, heuristicValue } from './nav.js';
```

* **`astar(spec, start, goal)`** — `spec = { cols, rows, blocked, cell,
  diagonal, heuristic, weights }`; `blocked` — массив/Uint8Array длины
  `cols*rows` или функция `(cx, cy) ⇒ bool`; `weights` — массив/число/функция
  стоимости. `start`/`goal` — **клетки** `{ cx, cy }`/`[cx, cy]`. Возвращает
  массив клеток или `null`. При `spec.partial` (то же, что `allowPartial`)
  отдаёт путь до ближайшей достижимой клетки.
* **`smoothPath(points, blockedFn)`** — `blockedFn(x1, y1, x2, y2) ⇒ bool`
  (истина = отрезок перекрыт). Возвращает новый массив точек.
* **`heuristicValue(name, dx, dy)`** — значение эвристики в клетках.

---

## 3. Агент

### `.navigateTo(target, opts) → wrapper`

Ставит узел на маршрут к цели. `target` — узел, обёртка, id/селектор или
`{ x, y }`; цель пере-разрешается при каждом пересчёте. Возвращает ту же
обёртку, поэтому метод цепной.

| `opts` | По умолчанию | Смысл |
|---|---|---|
| `speed` | `100` | Скорость, пиксели/с |
| `grid` | сетка по умолчанию | По какой сетке идти |
| `mesh` | навмеш по умолчанию | Идти по навмешу (приоритетнее `grid`); см. §4 |
| `stopDistance` | `6` | На каком расстоянии считать, что цель достигнута |
| `smooth` | `true` | Сглаживать маршрут |
| `repathEvery` | `500` | Период проверки цели, мс; `0` — не пересчитывать |
| `allowPartial` | `false` | Идти до ближайшей достижимой точки при недостижимой цели |
| `repathTolerance` | `4` | На сколько пикселей должна сдвинуться цель для пересчёта |
| `waypointRadius` | `max(4, cell/4)` | Радиус «точка пройдена» |
| `avoid` | — | `true`, селектор или обёртка — узлы для мягкого расталкивания |
| `avoidRadius` | `48` | Радиус расталкивания |
| `maxIterations` | — | Лимит итераций A* |
| `radius` | `agentRadius` источника | Габарит агента для поиска пути в пикселях |
| `onArrive`, `onBlocked` | — | Колбэки, получают событие (как `node.on`) |

Методы управления:

| Метод | Что делает |
|---|---|
| `.stopNav()` | Остановить агента и обнулить скорость тела |
| `.repath()` | Пересчитать путь прямо сейчас |
| `.navPath()` | Текущий маршрут `[ {x, y}, … ]` или `[]` |
| `.navTarget()` | Цель `{ x, y }` или `null` |
| `.isNavigating()` | Идёт ли агент к цели (bool) |

События узла: `arrive` (цель достигнута) и `blocked` (путь не найден или
цель стала недостижимой). У события в `data` есть `target`, а у `arrive` —
ещё и `path`.

Пока агент идёт, его узел **не** трогайте через `.moveTo`/`.moveTowards` —
они перебивают скорость. Двигайте цель, а не агента; при сдвиге цели маршрут
пересчитается сам (`repathEvery`).

### Движение

`tickNav(dt)` вызывается движком раз в кадр (подключён в `api.js`):

* у узла есть тело — агенту задаётся скорость (`engine.setVelocity`), тело
  ведёт физика;
* тела нет — узел смещается на `speed * dt` за кадр.

При достижении узел останавливается и получает событие `arrive`. Если путь
построить нельзя — событие `blocked`, навигация завершается. Один узел ведёт
не более одного маршрута: повторный `navigateTo` заменяет старый.

```js
$('#guard')
    .on('arrive',  () => $.log('дошёл'))
    .on('blocked', () => $.log('не могу пройти'))
    .navigateTo('#hero', { speed: 160, grid, repathEvery: 250, avoid: '.guard' });
```

---

## 4. Навигационный меш (`$.nav.mesh`)

Честно о терминах: это **прямоугольная декомпозиция**, а не триангуляция
(ни Делоне, ни «эрце»-триангуляция из Recast). Свободные клетки режутся
жадным проходом на непересекающиеся **прямоугольники**; соседние
прямоугольники с общей стороной связываются **порталами** (общий отрезок);
путь ищется по графу прямоугольников, а затем натягивается **воронкой**
(funnel / string pulling).

Что это значит на практике:

| | Прямоугольная декомпозиция | Триангуляция Делоне |
|---|---|---|
| Примитивы | прямоугольники (оси координат) | треугольники любой формы |
| Число примитивов | больше (диагонали — «ступеньки») | меньше, форма ближе к геометрии |
| Сложность построения | O(клеток), детерминировано | сложнее, есть вырожденные случаи |
| Вырожденные полигоны | невозможны | возможны, нужны эпсилоны |
| Путь | сглаживается воронкой | сглаживается воронкой |

Практический итог: навмеш на прямоугольниках описывает **диагональные и
скруглённые** коридоры ступеньками, поэтому граф больше, чем при
триангуляции. Зато построение простое и предсказуемое, прямоугольники
выпуклые (прямая внутри одного прямоугольника всегда свободна), а воронка
убирает ступеньки из итогового маршрута. Для 2D-игр этого достаточно; если
нужны «настоящие» полигоны — это уже другая подсистема.

### `$.nav.mesh(opts) → mesh | null`

Создаёт пустой навмеш. `x`/`y` — левый верхний угол, `w`/`h` — размеры в
пикселях, `cell` — сторона клетки (по умолчанию `32`), `agentRadius` — запас
на габарит агента. Прямоугольной декомпозиции снаружи не видно — она
строится **лениво**, при первом обращении, а не в конструкторе.

Навмеш сам по себе не становится источником пути для агента: вызовите
`$.nav.useMesh(mesh)` либо передавайте `{ mesh }` в `.navigateTo`/`$.nav.meshPath`.

### Методы навмеша

| Метод | Что делает |
|---|---|
| `.buildFromWalls({ tags, agentRadius, inset })` | Собрать препятствия из узлов мира |
| `.rebuild()` | Повторить последнюю сборку |
| `.clear()` | Снять все препятствия и сбросить декомпозицию |
| `.inflate(radius)` | Задать запас на габарит агента в пикселях |
| `.setBlocked(cx, cy, bool)`, `.blockAt(x,y)`, `.freeAt(x,y)` | Ручные препятствия |
| `.isBlocked(cx, cy)`, `.worldToCell(x,y)`, `.inBounds(cx,cy)` | Как у сетки |
| `.rects()` | Прямоугольники декомпозиции в мировых координатах |
| `.portals()` | Порталы (общие отрезки) в мировых координатах |
| `.rectAt(x, y)` | Прямоугольник под точкой или `null` |
| `.contains(x, y)` | Проходима ли точка (лежит ли в прямоугольнике) |
| `.lineOfSight(from, to)` | Прямая видимость по «сырым» препятствиям |
| `.path(from, to, opts)` | Путь по этому навмешу в мировых точках |

`rects()` отдаёт `{ index, cx, cy, cw, ch, x0, y0, x1, y1, x, y, w, h }`:
`cx/cy/cw/ch` — в клетках, `x0..y1` — мировые границы, `x/y` — центр, `w/h` —
размер. `portals()` — `{ index, a, b, x0, y0, x1, y1 }`, где `a`/`b` — индексы
прямоугольников. Массивы — копии, но объекты внутри общие с кэшем: не
изменяйте их.

### `buildFromWalls({ tags, agentRadius })`

Работает как у сетки, но с той же граблей-предохранителем: **обязательно
задавайте `agentRadius`**. Декомпозиция режется по маске, раздутой на радиус
тела; без запаса путь проходит вплотную к стене и тело упирается. При смене
радиуса декомпозиция пересобирается (под каждый радиус — свой кэш).

```js
const mesh = $.nav.mesh({ x: 0, y: 0, w: 1600, h: 900, cell: 32, agentRadius: 20 });
mesh.buildFromWalls({ tags: ['wall', '.obstacle'], agentRadius: 20 });
$.nav.useMesh(mesh);
```

`buildFromWalls`/`rebuild()` сбрасывают ручные пометки, поставленные до
вызова; ставьте их после пересборки.

### `$.nav.meshPath(from, to, opts) → [ {x, y}, … ] | null`

Путь по навмешу по умолчанию (или `opts.mesh`). Первая точка — ровно `from`,
последняя — ровно `to`, если цель достижима и точки не в стене; точка в стене
притягивается к ближайшему прямоугольнику. `opts.smooth === false` отключает
воронку (возвращается ломаная через середины порталов), `opts.allowPartial` —
путь до ближайшего достижимого прямоугольника, `opts.radius` — габарит для
этого вызова (по умолчанию `mesh.agentRadius`).

```js
$.nav.meshPath('#guard', { x: 900, y: 400 }, { smooth: true });
$.nav.meshPathOn(mesh, a, b, { radius: 24, allowPartial: true });
```

### `$.nav.useMesh(mesh)`, `$.nav.meshes()`

`useMesh` назначает навмеш по умолчанию для агента и `$.nav.meshPath`.
Приоритет в `.navigateTo`: явный `opts.mesh` → явный `opts.grid` → навмеш по
умолчанию → сетка по умолчанию. Поэтому старые игры на `$.nav.grid`
продолжают работать без изменений, даже если в игре появился навмеш.
`meshes()` возвращает копию реестра; `$.nav.clear()` чистит и сетки, и
навмеши.

### Чистые функции навмеша (экспортируются из `nav.js`)

Их гоняет qjs-тест без движка — см. `tests/js/navmesh_test.mjs`.

```js
import { decomposeRects, buildPortalGraph, funnel, makeMesh, pathOnMesh } from './nav.js';
```

* **`decomposeRects(blocked, cols, rows) → [ {cx, cy, w, h}, … ]`** — жадная
  декомпозиция свободных клеток на прямоугольники (в клетках). `blocked` —
  массив/Uint8Array или функция `(cx, cy) ⇒ bool`; за границей — стена.
* **`buildPortalGraph(rects) → { portals, adjacency }`** — граф соседства:
  `portals[i] = { index, a, b, x0, y0, x1, y1 }` (в единицах `rects`),
  `adjacency[i] = [{ index, portal }, …]`.
* **`funnel(points, portals) → [ {x, y}, … ]`** — натягивание пути через
  упорядоченные порталы `{ x0, y0, x1, y1 }`; один линейный проход.

---

## 5. Полный пример

```js
$.ready(() => {
    $.world.gravity(0, 1200).color('#101820').bounds(0, 0, 1600, 900);

    // Сетка по всей арене, препятствия — из стен, с запасом под радиус тела.
    $.nav.clear();
    const grid = $.nav.grid({ x: 0, y: 0, w: 1600, h: 900, cell: 32,
                              diagonal: true, heuristic: 'octile' });
    grid.buildFromWalls({ tags: ['wall'], inset: 6 });

    $('#npc').navigateTo({ x: 1400, y: 700 }, {
        speed: 200, grid, repathEvery: 400, allowPartial: true,
        onArrive: (e) => $.emit('npcCameHome', {}),
        onBlocked: (e) => $.log('путь закрыт: ' + e.data.reason),
    });
});

// Стена появилась — пересобрать препятствия один раз, а не каждый кадр.
function addWall(x, y) {
    $('<wall>').at(x, y).size(64, 64).appendTo($.world);
    $.nav.grids()[0].rebuild();
}
```

---

## 6. Производительность и ограничения

* Путь **не** пересчитывается каждый кадр: `repathEvery` плюс проверка, что
  цель действительно сдвинулась. A* кэширует клеточный маршрут по
  `start|goal|версия препятствий`; навмеш кэширует и путь, и декомпозицию.
* Массив препятствий — плоский `Uint8Array`; любое изменение поднимает
  `grid.version`/`mesh.version` и делает старый кэш недействительным.
* Сетка — не навмеш: клетка либо проходима, либо нет, «выпуклых» регионов и
  порталов у неё нет. Навмеш — прямоугольная декомпозиция (не триангуляция),
  см. §4; он строится по вызову (лениво, при первом обращении), а не в кадре,
  и даёт более гладкий путь при меньшем числе узлов графа.
* `avoid` — простое расталкивание по соседям, а не полноценный локальный
  обход; для плотных толп стройте маршрут с `weights` (дорогие клетки) или
  разносите агентов.
* Внешние границы сетки/навмеша для A* — стена: цель за пределами области
  недостижима.
* `weights` поддерживаются только клеточной сеткой; у навмеша стоимость шага —
  расстояние между центрами прямоугольников.
* После смены `weights` вызовите `grid.rebuild()` (или меняйте их до первого
  поиска): кэш различает только версию препятствий.