BeaRLibPF - поиск пути

Форум библиотеки BeaRLib

Модератор: Apromix

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

BeaRLibPF - поиск пути

Сообщение Apromix » 21 сен 2011, 08:24

Обсуждаем дальше тут поиск пути, как сделать его лучше, оптимизацию алгоритма.

Аватара пользователя
kipar
Сообщения: 2119
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF

Сообщение kipar » 21 сен 2011, 16:32

Во имя байтоптимизаций отказался от ненужных модулей. Теперь библиотека весит 22кб.
Ну и исправил демку. После перевода вывода на conioengine JustHarry (да, я знаю что это просто обертка над Video) монстры стали бегать намного шустрее, еще раскрасил их и сделал реакцию на клавиатуру.
Ходить - клавишами 2,4,6,8. Выход - esc.
BearLibPF.zip
(152.04 КБ) 133 скачивания
Последний раз редактировалось kipar 09 фев 2016, 13:05, всего редактировалось 1 раз.

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF

Сообщение Apromix » 21 сен 2011, 17:06

kipar писал(а):Во имя байтоптимизаций отказался от ненужных модулей. Теперь библиотека весит 22кб.
Супер :) То, что надо :)
kipar писал(а):Ну и исправил демку. После перевода вывода на conioengine JustHarry (да, я знаю что это просто обертка над Video) монстры стали бегать намного шустрее, еще раскрасил их и сделал реакцию на клавиатуру.
Ходить - клавишами 2,4,6,8. Выход - esc.
Немного побродил, нашел точку, когда все монстры стекались в одну реку и подбирались к @ сложным заковыристым маршрутом. Алгоритм работает просто на ура!!!
kipar писал(а):Когда будет время, переделаю чтобы использовать FOV_MAP Cfyz. Тогда и из C# можно будет вызывать.
Гуд :)

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF

Сообщение Apromix » 22 сен 2011, 09:31

Вот еще один алгоритм в копилку...

Аватара пользователя
alexbard
Сообщения: 670
Зарегистрирован: 22 апр 2011, 17:15
Откуда: Украина
Контактная информация:

Re: BeaRLibPF

Сообщение alexbard » 22 сен 2011, 09:37

Apromix писал(а):Вот еще один алгоритм в копилку...
Хах, по-ссылке: "различные варианты волнового алгоритма придумывал каждый нормальный программист, перед которым вставала задача поиска пути на карте из квадратиков"

Именно с помощью этого метода реализован поиск пути в Ignite :)

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF

Сообщение Apromix » 24 сен 2011, 19:55

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

Аватара пользователя
alexbard
Сообщения: 670
Зарегистрирован: 22 апр 2011, 17:15
Откуда: Украина
Контактная информация:

Re: BeaRLibPF

Сообщение alexbard » 24 сен 2011, 20:03

Apromix писал(а):Нашел баг в демке: когда @ оказывается в недоступном для врагов месте, они останавливают свое движение, как и положено, но в этот момент сама карта начинает медленно перестраиваться: одни ячейки заменяются на другие...
Это прямо идея для 7DRL, а не баг)

Аватара пользователя
kipar
Сообщения: 2119
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF

Сообщение kipar » 25 сен 2011, 08:20

Да, это не баг а фича. Карта медленно перестраивается в любом случае, чтобы показать что поиск пути работает на меняющейся карте. Просто когда монстры мельтешат перед глазами этого не заметно :) .

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF

Сообщение Apromix » 29 сен 2011, 06:53

Посмотрел код - да, действительно не ошибка :D

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF

Сообщение Apromix » 06 окт 2011, 12:37

kipar писал(а):Когда будет время, переделаю чтобы использовать FOV_MAP Cfyz. Тогда и из C# можно будет вызывать.
Свободное время появилось выполнить обещание?

Аватара пользователя
kipar
Сообщения: 2119
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF

Сообщение kipar » 06 окт 2011, 20:33

Ну, сейчас активно допиливаю свой WitchRL, так что особо нет времени.

Насчет адаптации, появилась такая идея:
Скрытый текст: ПОКАЗАТЬ
Есть объект CellObject - любой видимый или участвующий в поиске пути объект. Т.е. и кусок пола и монстр и игрок.
Он обладает следующими свойствами:
- Прозрачность - 1 байт, от непрозрачного до пустого. (пока используем только один бит)
- Проходимость - 1 байт, от непроходимого до ровного пола (пока тоже используем один байт).
- 4 байта - глиф, т.е. рисуемая картинка. Рисование реализуется самой игрой или другой библиотекой, так что не конкретизируем его, просто Pointer\void*.
- 4 байта - маркер для поиска, который будет использоваться при поиске цели. Интерпретация тоже зависит от игры, например так:
0 - пустое место
1 - игрок или его союзник
2 - еда
3 - враг игрока
и т.д.
------------------------

Карта TMap - двумерный массив, в каждой клетке находится список этих объектов плюс дополнительная инфа, соответствующая им, типа флага видел ли игрок эту клетку, видна ли она сейчас.

Этот TMap используется и в генерации карты, и в FOV, и в PF, и в AI. И в рисовании карты.
Преимущества например такие:
- в простой игре клеток могут указывать на один и тот же CellObject, т.е. не нужно создавать 100*100 объектов с прозрачностью 0, проходимостью 0, картинкой "#", а достаточно чтобы все клетки со стенами ссылались на один экземпляр стены.
- а если понадобиться сделать разрушаемость стен, то вуаля - создаем 100*100 объектов стен и можем разрушать их по отдельности, изменяя их проходимость, прозрачность и картинку, при этом на алгоритмах поиска пути и прочем это не скажется.

Далее, монстры - тоже являются такими объектами. Потому что непрозрачные монстры это экзотика, а вот непроходимые - норма. Так что в поиске пути их надо учитывать. Соответственно для них можно в библиотеке сделать процедуры перемещения на одну клетку (которая будет удалять его из списка текущей клетки и добавлять в другую) и потому на долю программиста рогалика останется только создание этих самых объектов.

Рисование тоже частично автоматизируем - просто для каждой клетки в определенной области последовательно вызываем пользовательские процедуры рисования, передавая им картинки объектов. И игра нарисует сначала клетку пола, потом лежащее там барахло, потом стоящих там монстров, потом всякие облака тумана. Правда есть два ньюанса - во первых добавим к CellObject еще 4 байта, определяющие его порядок в отрисовке (в нашем пример для пола это будет 1, для предметов 2, для монстров 3. А могло быть наоборот, в зависимости от исп-мого графического движка).
И второй ньюанс - придумать механизм коллбеков. Т.е. как вызывать пользовательскую функцию рисования. Потому что вызов функции по адресу в C# опять-таки работать не будет. А привязываться к внутреннему механизму рисования как в libtcod имхо нехорошо.
tl'dr: Пытаюсь придумать идеальнуюправильную архитектуру. Потому что адаптировать к ней pf не проблема, но хочется сделать ее универсальной для всех остальных библиотек (имеющих дело с картой).

Аватара пользователя
Cfyz
Сообщения: 771
Зарегистрирован: 30 ноя 2006, 10:03
Откуда: Санкт-Петербург
Контактная информация:

Re: BeaRLibPF

Сообщение Cfyz » 07 окт 2011, 08:08

kipar писал(а):Насчет адаптации, появилась такая идея
Надо обдумать. Выглядит сложновато на первый взгляд (не реализация, сама система), но что-то в этом есть. Однако все больше и больше идея приближается к большому и ужасному Bear Engine =)
kipar писал(а):Потому что вызов функции по адресу в C# опять-таки работать не будет
Будет, будет. См. http://www.codeproject.com/KB/dotnet/Cd ... rp_VB.aspx.
Пытается раскуклиться

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF

Сообщение Apromix » 07 окт 2011, 08:56

Cfyz писал(а):Однако все больше и больше идея приближается к большому и ужасному Bear Engine =)
Я за движок, но кто возьмется его написать? Я предпринял 2 попытки, первая на паскалевских скриптах (неудобно, нет сессий, чтобы запоминать переменные, а предложенный мной способ оказался неудобен), вторая на lua-скриптах (слишком медленно). Но, как мне кажется, это тупиковая ветвь. Нужно что-то другое. В поисках :)

Аватара пользователя
kipar
Сообщения: 2119
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF

Сообщение kipar » 07 окт 2011, 09:11

Cfyz писал(а):Однако все больше и больше идея приближается к большому и ужасному Bear Engine =)
Ну, все алгоритмы работающие с картой в любом случае должны использовать какую-то общую форму ее представления. С точки зрения инкапсуляции можно было бы скрыть это представление от них, но это будет плохо по производительности.
Cfyz писал(а):
kipar писал(а):Потому что вызов функции по адресу в C# опять-таки работать не будет
Будет, будет. См. http://www.codeproject.com/KB/dotnet/Cd ... rp_VB.aspx.
А, ну тогда текущая версия также к C# подключается. Одной проблемой меньше :)

Apromix писал(а):Я за движок, но кто возьмется его написать? Я предпринял 2 попытки, первая на паскалевских скриптах (неудобно, нет сессий, чтобы запоминать переменные, а предложенный мной способ оказался неудобен), вторая на lua-скриптах (слишком медленно). Но, как мне кажется, это тупиковая ветвь. Нужно что-то другое. В поисках
Надо посмотреть как T-engine сделан, правда объем кода в нем для тестового примера несколько пугает.

Аватара пользователя
Apromix
Мастер
Сообщения: 1197
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF

Сообщение Apromix » 07 окт 2011, 16:07

kipar писал(а):А, ну тогда текущая версия также к C# подключается. Одной проблемой меньше :)
Это супер :)
kipar писал(а):Надо посмотреть как T-engine сделан, правда объем кода в нем для тестового примера несколько пугает.
Ну движков есть много разных :D Мне, например, love2d понравился :D

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 1 гость