BeaRLibPF - поиск пути

[Apromix]

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

[kipar]

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

BearLibPF.zip

(152.04 КБ) 213 скачиваний

[Apromix]

Во имя байтоптимизаций отказался от ненужных модулей. Теперь библиотека весит 22кб.

Супер То, что надо

Ну и исправил демку. После перевода вывода на conioengine JustHarry (да, я знаю что это просто обертка над Video) монстры стали бегать намного шустрее, еще раскрасил их и сделал реакцию на клавиатуру.
Ходить - клавишами 2,4,6,8. Выход - esc.

Немного побродил, нашел точку, когда все монстры стекались в одну реку и подбирались к @ сложным заковыристым маршрутом. Алгоритм работает просто на ура!!!

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

Гуд

[Apromix]

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

[alexbard]

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

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

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

[Apromix]

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

[alexbard]

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

Это прямо идея для 7DRL, а не баг)

[kipar]

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

[Apromix]

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

[Apromix]

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

Свободное время появилось выполнить обещание?

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

[Cfyz]

Насчет адаптации, появилась такая идея

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

Потому что вызов функции по адресу в C# опять-таки работать не будет

Будет, будет. См. http://www.codeproject.com/KB/dotnet/Cd ... rp_VB.aspx.

[Apromix]

Однако все больше и больше идея приближается к большому и ужасному Bear Engine =)

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

[kipar]

Однако все больше и больше идея приближается к большому и ужасному Bear Engine =)

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

Потому что вызов функции по адресу в C# опять-таки работать не будет

Будет, будет. См. http://www.codeproject.com/KB/dotnet/Cd ... rp_VB.aspx.

А, ну тогда текущая версия также к C# подключается. Одной проблемой меньше

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

Надо посмотреть как T-engine сделан, правда объем кода в нем для тестового примера несколько пугает.

[Apromix]

А, ну тогда текущая версия также к C# подключается. Одной проблемой меньше

Это супер

Надо посмотреть как T-engine сделан, правда объем кода в нем для тестового примера несколько пугает.

Ну движков есть много разных Мне, например, love2d понравился