BeaRLibPF - поиск пути

[kipar]

Минибамп. Перевел для одного своего проекта astar с несортированного массива на двоичную кучу, ускорилась раза в полтора-два (в зависимости от карты), ну и еще немножко оптимизировал. И для компенсации этого сделал "честную" эвристику (та что была в изначальной версии генерила неоптимальные пути, в среднем процентов на 10 длиннее оптимальных), что замедлило поиск раза в три.
Я подозреваю что она все равно не блещет скоростью, так что не буду против если кто-то свой поиск пути в либу оформит. Я, к примеру, так и не понял зачем может понадобиться связный список в этом алгоритме, хотя видел в двух местах как его используют.

В общем, перезалил файл во втором сообщении темы.
Интерфейс пока не менял, но демка Cfyz с освещением офигенна, да и вообще я каким-то образом пропустил момент выхода BearLibMap. Надо будет на него библиотеку перевести, и демку тоже объединить с его FOV, а для тестирования скорости отдельный режим сделать.

[Cfyz]

и вообще я каким-то образом пропустил момент выхода BearLibMap. Надо будет на него библиотеку перевести, и демку тоже объединить с его FOV

Я чуть было не забыл, что там такое было >_<.

Да, у библиотеки карты есть возможность унифицировать работу нескольких модулей BearLib: поиск пути, расчет FOV/LOS и, что чуть менее очевидно, генерация уровня. Но основным минусом остается то, что работа с картой через динамическую библиотеку негативно сказывается на производительности: доступ через вызов невстраиваемой функции много дороже, чем чтение ячейки памяти прямо по месту использования. Собственно, на попытке разрешить эту проблему (или хотя бы оптимизировать) я и завяз. Как я отмечал в той ветке, для некоторых языков (С/С++, вероятно Pascal) можно извернуться через хитрый (очень хитрый на самом деле) враппер, который выспросит у библиотеки адреса памяти и будет работать с ними сам напрямую. В то же время для других языков (Lua, C#) составить такой враппер невозможно.

Быстрый доступ к карте со стороны клиента (приложения-игры) нужен в основном FOV/LOS -- это там надо обходить всю видимую область раз за разом во время отрисовки и рассчета AI. При работе с поиском пути карта обратно клиенту не передается, а научить одну библиотеку оптимально работать с другой библиотекой куда проще. Ну а для генерации уровней, как мне кажется, скорость доступа к ячейкам и вовсе не так критична. Все равно это будет один-два прохода и не во время самой игры.

Нутром чую, абстрагированное представление карты это правильный путь, но над деталями думать и думать еще.

[kipar]

При поиске пути есть еще одна оптимизация - надо возвращать пользователю весь путь, чтобы он не дергал библиотеку каждый раз если карта и цель не изменились.
Но в целом в поиске пути большую часть времени занимает не вызов коллбека а всякие перетасовки узлов, у меня (на карте 500*500) получилось 8.3мс если проверять ячейки и 9.3мс если вызывать коллбек из dll.

Т.к. FOV\LOS все равно твоя библиотека - разве ты не можешь не реализовывая враппера на уровне интерфейса просто передать "void*" в FOV, а он зная детали реализации будет работать напрямую с памятью?

[Cfyz]

Пока библиотеки "наши", действительно можно передать ей указатель на память, разве что вместе с описанием структуры памяти, мы же про абстрактное представление карты говорим. Именно этой возможностью и должен пользоваться гипотетический враппер. Проблемы возникают только если задуматься о подобной работе прямо со стороны приложения-игры, которое будет писаться неизвестно кем и неизвестно на каком языке. Требования к этому хаку получаются совсем другие.

Очень важно как обратно передается результат FOV и поиска пути. Если предполагается, что приложение будет забирать его через опрос той же самой карты, то оптимизацией библиотеки алгортима всю проблему не решить. В частности, чтобы отрисовать уровень нужно разок пробежаться по большому куску карты. Чтобы сделать динамическое освещение, придется аналогично пробежаться еще и для каждого источника света. Чтобы проверить кого видно, опять нужно просканировать карту. Вот по таким интуитивным прикидкам набегает весьма немало обращений к карте (неплохо бы это просимулировать и померять, чтобы не рассуждать голословно).

Альтернативой этому является использование коллбеков. Весьма вероятно, что библиотеки библиотеками, а как минимум одну копию уровня игра все равно будет держать у себя. Соответственно, пусть как хочет, так результатами и распоряжается: сохраняет в список, помечает прямо на карте или еще что. Вот, к примеру, ты говоришь "надо возвращать пользователю весь путь, чтобы он не дергал библиотеку" -- как раз сохранить докладываемый список точек пути в массив это тривиальная задача, path[i++] = p; практически.

Но с коллбеками надо уточнить, мы в этом разговоре вообще задумываемя об использовании библиотек из Python/Lua/Befunge/etc.? Потому что тогда неплохо бы освежить память на тему потенциальных проблем.

[kipar]

А вообще - как на самом деле там данные в памяти лежат? Каждый слой это просто прямоугольный массив записей с выравниванием? Тогда по-моему проблема надумана - дать пользователю указатель на него и всё.
Для низкоуровневых языков этого достаточно, а в скриптовых все равно по виртуальной функции на каждый чих, ну добавится еще несколько вызовов на клетку.

[Cfyz]

Хм, в текущей (и единственной) реализации данные зачем-то перемешаны, т. е. как расположены как будто массив структур. Почему так сделано -- не помню, хотя логичнее расположить каждый "слой" карты отдельным блоком. По поводу скриптовых языков там все немного тяжелее выходит (потому что еще проверки всякие каждый вызов), но наверное ты прав. Меня только отдельные случаи смущают (типа C#, где язык вроде огого, а по указателю просто так шастать не дают), но тут уж что поделать.

[kipar]

В шарпе надо уточнить, но вроде бы какая-то возможность работать с голыми массивами там есть. Да она даже в javascript есть (ради webgl), хотя он пока в список поддерживаемых платформ и не входит.

[Cfyz]

Так-то в C# неплохо с прямым доступом, но с оговоркой: надо помечать код unsafe и в настройках компилятора указывать флаг /unsafe. Т. е. это не то, что можно незаметно использовать во враппере.

[Jesus05]

Так-то в C# неплохо с прямым доступом, но с оговоркой: надо помечать код unsafe и в настройках компилятора указывать флаг /unsafe. Т. е. это не то, что можно незаметно использовать во враппере.

а с shared memory тоже можно работать только в unsafe ? http://blogs.msdn.com/b/salvapatuel/arc ... net-4.aspx
адд: хотя это не мультиплатформенно.

[Jesus05]

Если никто не против оставлю эту статью тут... поиск пути в стратегии... http://astralax.ru/articles/pathway
что-то отдельной темы по поиску пути не нашел а алгоритм для DF подобных "рогаликов" может сработать

[Феникc]

Если никто не против оставлю эту статью тут... поиск пути в стратегии... http://astralax.ru/articles/pathway
что-то отдельной темы по поиску пути не нашел а алгоритм для DF подобных "рогаликов" может сработать

Это не с хабра случаем, из статейки про РТС? Там вообще интересные вещи рассказаны, хотя и устаревшие уже лет пятнадцать как.

[kipar]

Скорее наоборот - на хабре оттуда. В общем, автор один и тот же.

[Феникc]

Ну я вот и предполагаю что Jesus05 про этот сайт из статьи на хабре узнал

[Jesus05]

Ну я вот и предполагаю что Jesus05 про этот сайт из статьи на хабре узнал

Да и решил что-б не потерялось оставить тут

[Apromix]

Заметил одну нестыковку в коде PF: массив карты там начинается с 1, хотя удобнее с 0.

Скрытый текст: ПОКАЗАТЬ

Код: Выделить всё

// Так сейчас:
Map: array[1..MAXX, 1..MAXY] of char;
// А так удобней:
Map: array[0..MAXX-1, 0..MAXY-1] of char;