Страница 2 из 3

Re: BeaRLibPF - поиск пути

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

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

Re: BeaRLibPF - поиск пути

Добавлено: 09 фев 2016, 14:55
Cfyz
kipar писал(а):и вообще я каким-то образом пропустил момент выхода BearLibMap. Надо будет на него библиотеку перевести, и демку тоже объединить с его FOV
Я чуть было не забыл, что там такое было >_<.

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

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

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

Re: BeaRLibPF - поиск пути

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

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

Re: BeaRLibPF - поиск пути

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

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

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

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

Re: BeaRLibPF - поиск пути

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

Re: BeaRLibPF - поиск пути

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

Re: BeaRLibPF - поиск пути

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

Re: BeaRLibPF - поиск пути

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

Re: BeaRLibPF - поиск пути

Добавлено: 10 фев 2016, 19:03
Jesus05
Cfyz писал(а):Так-то в C# неплохо с прямым доступом, но с оговоркой: надо помечать код unsafe и в настройках компилятора указывать флаг /unsafe. Т. е. это не то, что можно незаметно использовать во враппере.
а с shared memory тоже можно работать только в unsafe ? http://blogs.msdn.com/b/salvapatuel/arc ... net-4.aspx
адд: хотя это не мультиплатформенно.

Re: BeaRLibPF - поиск пути

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

Re: BeaRLibPF - поиск пути

Добавлено: 30 мар 2016, 16:19
Феникc
Jesus05 писал(а):Если никто не против оставлю эту статью тут... поиск пути в стратегии... http://astralax.ru/articles/pathway
что-то отдельной темы по поиску пути не нашел :( а алгоритм для DF подобных "рогаликов" может сработать :)
Это не с хабра случаем, из статейки про РТС? Там вообще интересные вещи рассказаны, хотя и устаревшие уже лет пятнадцать как.

Re: BeaRLibPF - поиск пути

Добавлено: 30 мар 2016, 16:23
kipar
Скорее наоборот - на хабре оттуда. В общем, автор один и тот же.

Re: BeaRLibPF - поиск пути

Добавлено: 30 мар 2016, 18:05
Феникc
Ну я вот и предполагаю что Jesus05 про этот сайт из статьи на хабре узнал :)

Re: BeaRLibPF - поиск пути

Добавлено: 31 мар 2016, 06:33
Jesus05
Феникc писал(а):Ну я вот и предполагаю что Jesus05 про этот сайт из статьи на хабре узнал :)
Да и решил что-б не потерялось оставить тут :)

Re: BeaRLibPF - поиск пути

Добавлено: 21 сен 2016, 09:31
Apromix
Заметил одну нестыковку в коде PF: массив карты там начинается с 1, хотя удобнее с 0.
Скрытый текст: ПОКАЗАТЬ

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

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