Навмеш: как боты узнают, где тут пол

Представьте: вы стреляете в врага, он убегает за угол — и продолжает преследование, хотя visually пути нет. Он знает, что за углом есть проход, потому что для него уровень — не мешок треугольников, а навигационная сетка. Navmesh. Разбираю, как она устроена и почему боты иногда тупят так, что стыдно за них, а не за себя.

Что такое navmesh

Это полигональная аппроксимация проходимых поверхностей. Движок берёт геометрию уровня и отвечает на один вопрос: где персонаж радиусом R и высотой H может стоять, не застревая. Результат — набор выпуклых полигонов, соединённых рёбрами-дверьми. Поиск пути — уже не по вершинам меша (сотни тысяч узлов), а по центрам полигонов (сотни). A* на таком графе считается за микросекунды, и тысяча ботов на карте перестают быть проблемой.

В Unreal это Recast-навмеш из коробки: ставишь NavMeshBoundsVolume, жмёшь Build, получаешь зелёную сетку. В Godot — NavigationRegion2D/3D с тем же Recast-бэкендом. В Blender движка нет, но есть аддоны и экспорт коллизий, по которым движок потом строит сетку сам.

Проходимое и непроходимое

Ключевое разделение — Walkable и Unwalkable. Не «есть пол» и «нет пола», а «персонаж здесь влезает» и «не влезает». Отсюда все нюансы:

• Agent radius. Бот с радиусом 40 см не пройдёт в щель 35 см, даже если стена визуально «дырявая». Увеличил agent radius — и навмеш внезапно перестал видеть половину дверей. Это не баг, это физика вашего капсюля.
• Максимальный подъём (Max Step Height). Ступенька 20 см — проходимая, 60 см — стена. Порог задаётся в конфиге, и всё, что выше, вырезается из сетки дырой.
• Наклоны. Плоскость под 45° обычно ещё пол, под 60° уже скалолазание. Движок режет наклонные поверхности по углу.

Дырки и артефакты

Навмеш строится рейкастом сверху вниз (или по вокселям), и вот где начинается фольклор:

1. Дырка под дверью. Порог выше Max Step Height — и в полу зияет разрыв. Бот упирается в невидимую стену ровно посреди коридора. Лечится ступенькой-невидимкой или правкой порога.
2. Навес съел пол. Козырёк над крыльцом проецируется вниз, и под ним навмеш становится уже, чем геометрия. Боты обходят лужу, которой нет.
3. Плавающие острова. Кусок навмеша на балконе без соединения с землёй — бот на нём застрянет навсегда, потому что маршрут до него существует, а маршрут обратно нет.
4. Склейки швов. Два региона, между ними зазор 1 см. Граф разорван, A* выдаёт «путь не найден», и бот начинает паниковать: крутиться, озираться, умирать стоя.

Отдельная радость — динамические объекты. Ящик, который бот толкает, в навмеше не дыра: сетка статична. Для «живых» препятствий есть dynamic obstacle avoidance (RVO/ORCA — боты обтекают друг друга локально) и NavModifier volumes в Unreal, которые вырезают зоны вручную.

Практический чек-лист

• Визуализируйте навмеш всегда. Зелёная сетка поверх уровня мгновенно показывает дыры, которых «в игре не видно».
• Стройте сетку от самого крупного агента: если тяжёлый бот с радиусом 50 проходит, мелкий с 30 пройдёт тем более.
• Проверяйте соединения регионов: любой остров — будущий тикет «бот завис на балконе, скрин прилагаю».

Хороший навмеш незаметен. Плохой — memorable, как тот сталкер, который до сих пор ходит кругами на моем старом уровне.