[Из песочницы] Поиск пути через NavMesh на ActionScript – CrossBridge-порт Recast Navigation
В этой статье я расскажу об опыте переноса C++ кода на ActionScript с помощью FlasCC компилятора и покажу, как с его помощью мне удалось портировать довольно большой объем полезного кода, решающего задачу поиска пути. В конце будет демо и ссылка на репозиторий с кодом. А пока пара слов о том, с чего вообще все началось.Я работаю над индипроектом. Это шутер с видом сверху (похоже на Crimsonland). Пишу проект на AS3. Игровое пространство непрерывно (не по клеточкам) и основано на физическом движке Nape. Непроходимые участки (стены) описываются набором выпуклых многоугольников. Возникает задача навигации агентов (монстров) по такой карте.
Какие вообще существуют идеи для решения такой задачи?
1. Пространство можно разбить на клетки и свести ее к задаче поиска пути на клетчатом поле. Для этого уже существуют готовые решения на Флеше. Но такой вариант мне не понравился тем, что он принуждает агента двигаться всегда из некоторой клетки в некоторую соседнюю. Еще это решение никак не учитывает размер агента, который может быть разным.
2. Можно построить граф проходимости. Если агент не может дойти до цели по прямой, то алгоритм находит ближайшие к агенту цели, пару узлов графа и строит между ними маршрут по графу. Такой подход я реализовал в своем проекте в качестве временного. Устроен он был так: в редакторе уровней задавались узлы (вэйпоинты), без указания связей. Во время загрузки уровня система определяла прямую проходимость между всевозможными парами узлов и таким образом задавала связи между ними. Это решение какое-то время меня устраивало, но вскоре стали раздражать некоторые недостатки: — Размер агентов все еще никак не учитывался. Было бы здорово, чтобы на основе проходимости для агентов разного размера можно было строить ситуации в игре.— Узлы приходится задавать в редакторе вручную. Неприятно, что вообще к этой теме приходится постоянно возвращаться. А от того как хорошо расставлены узлы зависит качество маршрутов.— Маршруты получаются не оптимальными. Часто стала возникать ситуация, когда агент сначала идет «от цели» к ближайшему узлу и только от него начинает следование, т.к. других узлов в прямой проходимости не было.— Агенты никак не учитывают существование друг друга. При движении толпы монстров, линейность их перемещения очень заметна и выглядит не реалистично.
3. Еще один подход — navigation mesh. Идея такая: проходимая область карты покрывается набором выпуклых многоугольников, примыкающих друг к другу. Внутри каждого многоугольника агент может перемещаться свободно. Это очень хорошее решение для моего случая, я стал искать, какие существуют инструменты на Флеше. Оказалось, что ничего в общем-то и нет. Но есть на C++. Набор инструментов называется Recast Navigation — это довольно серьезная вещь и в ней есть абсолютно все необходимое. Справедливости ради отмечу, что на Гитхабе есть портированная через Алхимию демка Рекаста, но это лишь демка, использовать которую повторно не получится.
И тогда я понял, что мне это надо. Я стал думать, как мне перенести это на AS3. Отходя немного в сторону скажу, что до использования физического движка Nape, я пробовал использовать Box2D, который на Флеше есть в двух вариантах: переписанный на AS3 и портированный с помощью Алхимии. Переписанный на AS3 вариант обладал тем недостатком, что каждое изменение, будь то исправленная ошибка или новый функционал, требовал ручного перенесения соответствующего кода во Флеш-версию движка. В какой-то момент его просто забросили. А вот порт через Алхимию мне в принципе понравился. Кроме просто набора функций, повторяющих API оригинального движка, автор добавил набор AS3 классов-оберток для соответствующих классов и структур в C++. Таким образом, API во Флеш-версии скрывал от разработчика необходимость следить за передачей указатей, оперируя просто классами-обертками.
Решил портировать все через CrossBridge (бывш. Алхимия). CrossBridge — это среда, основанная на Cygwin, в которой имеется свой gcc компилятор. Компилятор называется FlasCC и на выходе он выдает ActionScript-байткод. Общий ход работы такой: Каждому методу в C++ сопоставляется метод в AS3, который максимально точно повторяет прототип C++ функции. Набор таких функций компилируется с помощью FlasCC в swc. Далее эта swc подключается к проекту, в котором создается другая swc с финальным API (с документацией), скрывающим от AS3-разработчика указатели, аллокейт памяти и т.д.
Как и оригинальный код, данный порт я решил сделать открытым. Весь код находится вот тут: github.com/Rokannon/Crossbridge-Recast-NavigationРепозиторий с оригинальным кодом на C++ добавил в качестве подмодуля.
Небольшое демо того, что получилось, вы можете посмотреть тут: work.rokannon.com/navmesh_demoВ панели справа необходимо выбрать исходный меш, описывающий геометрию уровня. Далее надо прокрутить панель вниз, нажать «Build» и подождать немного пока построится NavMesh. В панели слева есть два инструмента, демонстрирующие возможности тулсета: поиск пути и навигация толпы агентов.
Перенесены еще не все функции, но очень многие. Так что кодом уже можно пользоваться. Подписывайтесь на репозиторий, чтобы следить за обновлениями.
На этом официальная часть закончена. Спасибо за внимание. Если у кого-то возникли какие-то вопросы — спрашивайте.
Ну, а далее, для тех, кому интересны тонкости реализации, я расписал приемы, которые использовал при портировании C++ кода в AS3.
Простейший пример
#include
// Функция, которую требуется портировать в AS3. float testFunc (x: float, y: float): float { return x + y; }
void _testFunc () __attribute__((used, annotate («as3sig: public function internal_testFunc (x: Number, y: Number): Number»), annotate («as3package: ctest»)));
void _testFunc () { float x; AS3_GetScalarFromVar (x, x); // Первый аргумент это Си-переменная, второй — AS3.
float y; AS3_GetScalarFromVar (y, y);
AS3_Return (x + y); } Запустив CrossBridge, такой код можно скомпилировать:
/cygdrive/c/Crossbridge_1.0.1/sdk/usr/bin/g++ «main.cpp» -emit-swc=ctest -o «out.swc» В результате в получившейся swc будет функция internal_testFunc (x: Number, y: Number): Number, выполняющая то же, что и testFunc в С++. Абсолютно все функции портированы по такому шаблону. Приставка internal_ выбрана специально, т.к. полностью скрыть этот метод из финальной swc не получится.Структуры Данный класс используется в качестве базового для классов-оберток структур: package ctest { use namespace c_internal;
public class CBase { c_internal var ptr: int;
public function alloc (): Boolean { return false; }
public function free (): void { CModule.free (ptr); } } } На что здесь имеет смысл обратить внимание? Класс-обертка хранит адрес структуры или класса, который оборачивает. В AS3 нет указателей. Вместо них используется просто int. Переменная ptr должна быть доступна везде, кроме финального API, поэтому она скрыта специальным кастомным неймспейсом c_internal.Рассмотрим вот такую структуру в C++:
struct MyStruct { int x, int y }; Такой структуре в качестве класса-обертки будет соответствовать: package ctest { use namespace c_internal;
public class MyStruct extends CBase { c_internal static var SIZE: int = 0; c_internal static const OFFSET_X: int = offset (4); c_internal static const OFFSET_Y: int = offset (4);
private static function offset (size: int): int { return (SIZE += size) — size; }
public function get x (): Number { return CModule.read32(ptr + OFFSET_X); }
public function set x (value: Number): void { CModule.write32(ptr + OFFSET_X, value); }
public function get y (): Number { return CModule.read32(ptr + OFFSET_Y); }
public function set y (value: Number): void
{
CModule.write32(ptr + OFFSET_Y, value);
}
public override function alloc (): Boolean
{
ptr = CModule.alloc (SIZE);
return ptr!= 0;
}
}
}
Здесь небольшой трикс позволяет в удобной форме посчитать отступы всех полей и в качестве бонуса получить размер структуры. Но есть один питфол, связанный с memory alignment: Грубо говоря, если данные не помещаются полностью в одно слово (4 байт), то их отступ должен быть кратен 4 байт. Например, структура:
struct ExampleStruct
{
char x,
char y,
int z
}
Расположится по байтам так: X Y 0 0 Z Z Z Z. И sizeof (ExampleStruct) равен 8, а не 6 байт.Функции с указателями в аргументах
#include
void addNum (MyStruct* s, int n) { s→x += n; s→y += n; }
void _addNum () __attribute__((used, annotate («as3sig: public function internal_addNum (s_ptr: int, n: int): void»), annotate («as3package: ctest»)));
void _testFunc () { MyStruct* s; AS3_GetScalarFromVar (s, s_ptr);
int n; AS3_GetScalarFromVar (n, n);
addNum (s, n); } Чтобы скрыть от разработчика необходимость прокидывать указатель, в финальном API будет такая функция: package ctest { use namespace c_internal;
public function addNum (s: MyStruct, n: int): void
{
internal_addNum (s.ptr, n);
}
}
Функции возвращающие указатель
#include
MyStruct* sum (MyStruct* s1, MyStruct* s2) { s1→x += s2→x; s1→y += s2→y; return s1; }
void _sum () __attribute__((used, annotate («as3sig: public function internal_sum (s1_ptr: int, s2_ptr: int): int»), annotate («as3package: ctest»)));
void _testFunc () { MyStruct* s1; AS3_GetScalarFromVar (s1, s1_ptr); MyStruct* s2; AS3_GetScalarFromVar (s2, s2_ptr); AS3_Return (sum (s1, s2)); } Поскольку обертка не хранит в себе никаких данных об оборачиваемой структуре\классе кроме адреса, удобно добавить ее в качестве необязательного аргумента в API-метод: package ctest { use namespace c_internal;
public function sum (s1: MyStruct, s2: MyStruct, resultMyStruct: MyStruct = null): MyStruct { if (resultMyStruct == null) { resultMyStruct = new MyStruct (); } resultMyStruct.ptr = internal (s1.ptr, s2.ptr); return resultMyStruct; } } Аналогичный прием используется для обращения к элементам массива.
