BeaRLibFOV - поле зрения

[Apromix]

Переношу обсуждение библиотеки с FOV в эту тему

[Jesus05]

Cfyz тут
Предложил делать FOV вместе с LOS мне кажется это очень логичным.
и я тут подумал, а ведь FOV из LOS-а по важным объектам используя принцип теней можно довольно легко сделать (если забыть пока про интенсивности света)
в процедуру FOV`а передается список теоретически видимых объектов в пределах видимости (это будут монстры, стены, предметы и т.д.) главное что-бы с объектами прилагалась информация прозрачны ли они для света (в 99% рогаликов сквозь монстров можно видеть)
1-вым проходом алгоритму надо будет посчитать тени от стен(ну или других закрывающих свет объектов) считать надо от героя (т.е. центра отданой на посчет области) до края просчитываемой области. (при чем считать надо только те клетки который еще не в тени).
2-рым проходом надо заполнить от героя все клетки не попавшие в тень как светлые. (т.е. по сути тут надо использовать какой-нить алгоритм залития при этом не трогая клетки между которыми и героем нет прямого пути без теней).


блин сижу и думаю... по сути описал свой-же алгоритм тока залитие делалось параллельно расстановке теней.

[Apromix]

По аналогии с тем, как делалась библиотека с генератором карт нужно передавать простой динамический массив из целых чисел (0 - не видно, 1 - видно) и радиус обзора и получать такой же массив, но обработанный алгоритмом FOV. Перед вызовом метода определять, что у нас будет видно/невидно, например, стены могут быть прозрачные, стеклянные и не прозрачные, обычные, вобщем все сводить к нулям и единицам

[Jesus05]

По аналогии с тем, как делалась библиотека с генератором карт нужно передавать простой динамический массив из целых чисел (0 - не видно, 1 - видно) и радиус обзора и получать такой же массив, но обработанный алгоритмом FOV. Перед вызовом метода определять, что у нас будет видно/невидно, например, стены могут быть прозрачные, стеклянные и не прозрачные, обычные, вобщем все сводить к нулям и единицам

грубо говоря я вижу 2 способов.
а. передать процедуре массив(матрицу) с минимум 2-мя битами.
1бит значимый объект.
2бит пропускает свет.
на возврат нужна одно битный массив(матрица) где содержится информация о том светлая или темная клетка.
б. на входе массив из N значимых объектов каждый объект содержит:
координаты своего места относительно героя (от -радиус до +радиус)
булевая "пропускает ли свет?"
на возврат может быть как массив(матрица) из варианта а.
так и массив значимых объектов (но тогда будет косяк с полом, но тут можно сделать ту самую заливку и вернуть то-же что и возвращал бы вариант а).

опять-же я не размышляю о степени освещенности здесь.

[kipar]

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

[Jesus05]

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

думаю хороший вариант, тока мне кажется, это уменьшит скорость выполнения одной отдельно взятой проверки, но надо тестить что-бы точно сказать что больше потеря на вызове калбэков или шерстение памяти с созданием и удалением массивов. (думаю для больших ФОВов (100 и более клеток) потери на создание удаление массивов будут медленнее чем колбэки).

[Jolly Roger]

Один вопрос, FOV будет для каждого существа расчитываться или один на всех?

[Jesus05]

Один вопрос, FOV будет для каждого существа расчитываться или один на всех?

я как-то не представляю себе "один на всех".

[Apromix]

Один вопрос, FOV будет для каждого существа расчитываться или один на всех?

Я так думаю в либу будут передаваться либо координаты существа, либо уже в самой либе будет вычисляться центр (в котором находится существо), исходя из размеров матрицы массива.

[Cfyz]

Имхо лучше передавать не массив, а коллбеки.

думаю хороший вариант, тока мне кажется, это уменьшит скорость выполнения одной отдельно взятой проверки

Я тоже не тестил, но мне кажется это не просто уменьшит, а убьет ее в хлам. Вызов функции (стек туда-сюда, лишние временные переменные), проверка переменных, отсутствие возможности закешировать хоть что-то и т. д.

потери на создание удаление массивов будут медленнее

Массивы даже удалять незачем, все равно его же еще не раз передавать.

Один вопрос, FOV будет для каждого существа расчитываться или один на всех?

Все прочитанное и продуманное мною про FOV я могу просуммировать так: FOV для игрока, LOS для всех остальных. Поле зрения монстров неважно, мы все равно его не рисуем.

Я так думаю в либу будут передаваться либо координаты существа, либо уже в самой либе будет вычисляться центр (в котором находится существо), исходя из размеров матрицы массива.

Я немного повторюсь:

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

// mapWidth, mapHeigth -- размеры уровня
// visibilityMap -- массив, карта прозрачности уровня
// (px, py) -- позиция игрока
// (dx, dy) -- направление зрения, (0, 0) для круга
// angle -- угол зрения
// radius -- радиус видимости "в вакууме"
// result -- карта видимости, 0 невидимо, 255 видимо полностью

int CalcFOV( int mapWidth, int mapHeight, int **visibilityMap, int px, int py, float dx, float dy, float angle, float radius, unsigned char **result );

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

// objectMap -- массив, карта идентификаторов объектов
// resultSize -- размер массива result
// result -- список идентификаторов видимых объектов, не более resultSize записей (т. е. resultSize должно быть равно количеству идентификаторов в objectMap, иначе LOS будет неполным)

int CalcLOS( int mapWidth, int mapHeigth, int **visibilityMap, int **objectMap, int px, int py, float dx, float dy, float angle, float radius, int resultSize, int *result );

Такой вариант (который я в блищайшее чуть свободное время набросаю) мне кажется наиболее гибким. Никакие из массивов не надо удалять до выхода из игры, большинство массивов изменяются редко или вообще не изменяются. В частности, при вычислении LOS монстров, в вызовах CalcLOS меняются только точка откуда и, опционально, куда.

[Apromix]

Уточни несколько вещей :
1. Нужно будет передавать (ну и получать соотв.) часть карты вокруг игрока по самый радиус, квадратную естественно, или всю карту уровня?

Мне кажется, вычислительная нагрузка была бы меньше, если передавать/получать часть карты

2. Зачем в конце CalcFOV используется массив unsigned char **result ?

В BeaRLibMG теперь массив не из символов, а из целых натуральных чисел. Хотелось бы, чтобы библиотеки как бы совмещались на уровне тайлов и не нужно было бы переводить тайлы из чаров в числа и наоборот.

3. В CalcLOS зачем int **objectMap?

4. Карта видимости, я так понимаю либа будет хранить и ячейки, которые посетил игрок? Или я ошибаюсь?

[Jesus05]

не нужно было бы переводить тайлы из чаров в числа и наоборот.

наконец до меня дошло что ты имеел ввиду под похожей фразой парой сообщение назад.
char в C++ это 1 байт памяти и там совсем не обязательно находится символ это число от -127 до 128 (или в случае unsigned char от 0 до 255)
в паскале такой тип данных называется shortint если мне не врет гугл.

[Cfyz]

Нужно будет передавать (ну и получать соотв.) часть карты вокруг игрока по самый радиус, квадратную естественно, или всю карту уровня? Мне кажется, вычислительная нагрузка была бы меньше, если передавать/получать часть карты

Размер и количество (в разумных пределах) массивов на вычислительную нагрузку не влияет никак, в конце концов в функцию передается лишь указатель, т. е. просто целое беззнаковое число. Даже если массив размером в сто тысяч миллионов ячеек, но используется только две, то разницы в скорости исполнения по сравнению с использованием массива в две ячейки не будет (проблемы поддержки виртуального адресного пространства и механизма подкачки оставляю читателю в качестве домашнего задания). Mассив 512x512 четырехбайтных (int) чисел занимает один мегабайт ровно, что конечно излишне (на кой черт я там именно int поставил?), но совсем не смертельно.

В то же время, использование массива специального размера приведет к куче последствий. Прямоугольник ячеек в радиус видимости размером необходимо будет выделять и удалять при изменении того самого радиуса. Его нужно будет постоянно заполнять заново, каждый раз выбирая из карты в зависимости от положения игрока. Результат надо будет мапить обратно на карту, вероятно с учетом используемого способа скроллинга. И все это в количестве монстров (потому что им тоже считать надо). В то же время заранее заготовленные массивы для моих CalcFOV/CalcLOS меняются редко, visibilityMap так может вообще не меняться ни разу за все время нахождение игрока на уровне.

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

Зачем в конце CalcFOV используется массив unsigned char **result
В BeaRLibMG теперь массив не из символов, а из целых натуральных чисел.

result не имеет отношения к тайлам вообще и генераторам карт в частности, это массив-результат работы FOV, где я с потолка определил значения 0 как невидимую ячейку, а 255 как видимую полностью с теоретической возможностью получить и значения между, если когда-нибудь функция будет рассчитывать видимость с затуханием. Тип char выбран лишь потому, что в С это число с минимальным размером (в один байт), а то, что в нем еще и символы хранят, нам без разницы.

В CalcLOS зачем int **objectMap

Это карта идентификаторов сколько-нибудь интересных объектов на уровне -- монстров, предметов. Так как результатом LOS является список видимых объектов для конкретной ситуации, objectMap представляет собой исходный набор всех объектов, что можно на уровне увидеть. Опять же, целый массив потому, что так его проще составлять, а меняется он в процессе игры потихоньку. Очевидным слабым местом здесь является то, что (по крайней мере, без небольшого трюка) такой механизм не может отработать ячейки с несколькими предметами, но давайте вспомним, что во-первых, CalcLOS предназначен для невидимой работы и небольшие огрехи допустимы, во-вторых кто запрещает подготовить отдельно карту монстров и отдельно карту предметов?

Мне кажется, или механизм возврата результата в CalcLOS неочевиден публике? Легкая иллюстрация:

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

  5  ...
    ..2.. 4
   ...@...
    .1...
     ..3   6

На данном рисунке приведен кусочек массива objectMap, где точками отмечены видимые ячейки. В приведенном случае resultSize = 7, а result, соответственно, имеет размер в семь элементов. После выполнения функции result имеет следующее содержимое { 2, 1, 3, -1, ?, ?, ? }, что позволяет утверждать, что игрок или монстр из данной позиции видит предметы (или других монстров) с идентификаторами 1, 2 и 3. Если сильно не жмотиться и оставить в качестве типа элемента массива objectMap тип-указатель (так уж получилось, на 32-битных системах это и есть int, только без знака, но это неважно), то можно оперировать непосредственно указателями на внутриигровые объекты, тем самым убирая необходимость сопоставления объектов и идентификаторов и выигрывая в скорости еще больше.

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

Карта видимости, я так понимаю либа будет хранить и ячейки, которые посетил игрок? Или я ошибаюсь?

Честно говоря, даже не думал над этим. Информация о том, посетил или не посетил ячейку игрок для FOV непринципиальна, поэтому и не включалась в рассмотрение. Вообще, предполагаю, что у игры где-то должна быть и структура самого уровня и наверняка в ней ячейки не простые int, а как водится с динамическими списками и прочими плюшками. Добавить туда флаг видимости нетрудно. Ну или оставить visibilityMap знакового типа и считать непроницаемой для взгляда как 0, так и меньше ноля, позволяя сохранить минус-единицами информацию о разведанности уровня.

[Apromix]

не нужно было бы переводить тайлы из чаров в числа и наоборот.

наконец до меня дошло что ты имеел ввиду под похожей фразой парой сообщение назад.
char в C++ это 1 байт памяти и там совсем не обязательно находится символ это число от -127 до 128 (или в случае unsigned char от 0 до 255)

Да, паскалисты - они такие

в паскале такой тип данных называется shortint если мне не врет гугл.

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

ShortInt = -127 .. 128
Byte = 0 .. 255

Cfyz

Теперь более чем понятно

[Jolly Roger]

Один вопрос, FOV будет для каждого существа расчитываться или один на всех?

я как-то не представляю себе "один на всех".

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