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

BeaRLibPF - поиск пути

Добавлено: 21 сен 2011, 08:24
Apromix
Обсуждаем дальше тут поиск пути, как сделать его лучше, оптимизацию алгоритма.

Re: BeaRLibPF

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

Re: BeaRLibPF

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

Re: BeaRLibPF

Добавлено: 22 сен 2011, 09:31
Apromix
Вот еще один алгоритм в копилку...

Re: BeaRLibPF

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

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

Re: BeaRLibPF

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

Re: BeaRLibPF

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

Re: BeaRLibPF

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

Re: BeaRLibPF

Добавлено: 29 сен 2011, 06:53
Apromix
Посмотрел код - да, действительно не ошибка :D

Re: BeaRLibPF

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

Re: BeaRLibPF

Добавлено: 06 окт 2011, 20:33
kipar
Ну, сейчас активно допиливаю свой 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 не проблема, но хочется сделать ее универсальной для всех остальных библиотек (имеющих дело с картой).

Re: BeaRLibPF

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

Re: BeaRLibPF

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

Re: BeaRLibPF

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

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

Re: BeaRLibPF

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