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

[Apromix]

Cfyz
Как успехи ?

[Cfyz]

Apromix
В этот сезон суббота и воскресенье свободным временем не являются. А еще я до этого случая не вникал в привычные (дискретные) алгоритмы FOV. А еще когда я сел был не день Брезенхема, а еще...

И прочее нытье.

Работаем. Вы просили эффективный FOV? Вы его получите. Проштудировав статьи по разным подходам, наиболее эффективным считаю алгоритм, описанный в этой статье (кстати, не забудьте потом напомнить запилить хотя бы перевод). У алгоритма несколько преимуществ (но понятность реализации к ним не относится), а в сети можно найти несколько реализаций, все страдающие рядом несущественных, но неприятных недочетов (чудовищный копипаст в коде и степень рекурсии, уходящая в небеса). Также, имхо неплохо бы адаптировать алгоритм к картам с "шестиугольными" клетками.

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

Ну и чтобы не разводить сопли дальше, до 16.09.11 23:59 по Москве либа будет. Даже если мне придется тупо обернуть в .dll libfov (что конечно печаль будет, так как убьет мою самооценку нахрен).

[Apromix]

ОК, будем терпеливо ждать Ты пили сколько нужно, а не до опр. даты, я знаю, что такое загруженность, сам сейчас взвалил на себя проект на PHP =)

[Cfyz]

Итак, обещал -- надо что-то показать.

Начнем с относительно хорошей новости. Собственно,

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

int CalcFOVC( FOV_MAP *map, int px, int py, int radius );

Немного не то, что я себе представлял, но работает и работает как положено. CalcLOS нет, об этом ниже.

Карта упакована в FOV_MAP

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

typedef struct
{
    int Width;
    int Height;
    FOV_CELL* Cells;
}
FOV_MAP;

где FOV_CELL

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

typedef struct
{
    unsigned char Flags;
    void* Reserved;
}
FOV_CELL;

Конкретные имена типов, полей вообще и поле Reserved в частности -- subject to change. Вполне очевидно, что только начали, сейчас соберемся, подискутируем, подеремся и сделаем хорошо. Идеально не сделаем, я ж пессимист.

Флаги для FOV_CEL::Flags наличествуют следующие: FOV_CELL_VISIBLE (клетка видна игроку), FOV_CELL_OPAQUE (клетка непрозрачна), FOV_CELL_VISITED (клетка была уже видна однажды). Полупрозрачных стен и неоднородного света нет.

К сообщению должен быть прикреплен архив, в нем проекты для Dev-Cpp и бинарные файлы библиотеки и демонстрационной программы. В демо, уж позвольте мне так громко ее называть, можно (и нужно) нажимать стрелки и нумпад, а также клавиши B, F, +, -- и Escape, результат действия каждой нагляден и в пояснениях не нуждается. При желании можно отредактировать файлик map.txt рядом с исполняемым файлом.


Теперь к разным мелочам.

Во-первых, я окончательно и бесповоротно демотивировался в дискретном FOV. Под дискретным я подразумеваю такой, в котором пространство разбито на клеточки и клеточки эти неделимы вообще никак. Ни в жисть не буду делать такой у себя. Я даже проиллюстрирую свою точку зрения:

На этом рисунке изображен кусочек из моих попыток сделать хороший и красивый FOV по клеточкам, но самостоятельно (то, что изображена 1/8 поля непринципиально, все легко масшатбируется зеркалированием и поворотом). Снизу-слева расположена стена с отверстием в одну клетку; серым полупрозрачным -- тени, отбрасываемые стенами. Коричневым отмечены клетки, у которых видна по меньшей мере половина (центр не попал ни в одну тень).

Теперь взгляните на клетки сразу за стеной -- они практически все в тени и не должны бы быть видны. Однако клетки далеко за стеной в немалом количестве попадают в "освещенное" пространство и видны быть уже должны. Клетки, которые видно через клетки, которые не видно o_O? Тени в данном примере специально построены максимально строго (из углов стен). Может показаться, что их можно было бы построить, скажем, от середин сторон проема, что дало бы более широкую освещенную площадь. Такое "решение" -- заблуждение, всегда можно найти такое положение среди комнат и колонн, которое даст узкий луч света. Кроме того, делая тени менее и менее строгими в итоге приходим к ситуации, когда можно заглядывать далеко за углы. Считать клетку освещенной если она на не более, чем на X% в тени? Дохлый номер. В принципе, при некоторой настройке можно пользоваться, но результат, который дают обкатанные опытными рогалико-разработчиками алгоритмы наподобие MRPAS, мне нравится больше.

Что за фигня, во всяких адомах же все спокойненько считается, да? Просто есть момент, когда заканчивается математика и начинается колдунство. Тени, отбрасываемые не по законам оптики; клетки, видимость которых рассчитывается по отвернутой от игрока стороне квадрата, и даже по трем точкам этой стороны; построчный подсчет клеток; проверки, не видны ли еще пара определенных клеток рядом с проверяемой -- и прочее хакерское веселье. От красивого геометрического алгоритма остается вот такенная шелуха:

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

if (visible && (m->cells[c-(m->width*dy)].fov == 0 || !m->cells[c-(m->width*dy)].transparent) && (x-dx >= 0 && x-dx < m->width && (m->cells[c-(m->width*dy)-dx].fov == 0 || !m->cells[c-(m->width*dy)-dx].transparent))) visible = false;

Это кусочек из libtcod (забавно, что и в stable, и в beta libtcod в этой процедуре расчета FOV течь; ненамного, примерно 2*mapWidth*mapHeight байт на все время выполнения программы, но все же >_<). Даже приведенный к божескому виду такой код совершенно неочевиден и намертво привязан к квадратным клеткам и выбранному компромиссу между точностью и красотой результата. Какие там шестиугольники =_=

Btw, именно TCOD_map_compute_fov_restrictive_shadowcasting взят мною за основу CalcFOVC. Данный метод итеративного FOV на основе теней дает хороший предсказуемый результат при отличной вычислительной сложности. Исходные тексты на сайте автора алгоритма повторяют код из libtcod вплоть до именования структур и переменных, что тоже лол. Текст функции я как мог причесал, сократив его в два раза (понятности не добавило, но хоть править проще будет, в оригинале он состоит из 2-4-8 практически полностью идентичных кусков) и немного пожертвовал производительностью, заменив конструкции типа m->cells[c-(m->width*dy)-dx].fov на внятное CellVisible( map, x-dx, y-dy ).

Чем же так фундаментально мне не нравится клеточный FOV? Да тем простым фактом, что как ни крути, а клетка считается освещенной или неосвещенной (или освещенной на столько-то процентов) -- но ЦЕЛИКОМ. Тяжкое наследие консольных приложений в век, когда даже в BIOS уже можно найти Hi-Color и лигатуры. Я ни в коем случае не утверждаю, что old school плохо, но желать всего и сразу не всегда разумно. Я вот пожелал и планомерно набил шишек, потратив время не то чтобы зря, но непродуктивно это уж точно =) По моему скромному мнению, проще сделать честный графический режим с тенями правильной формы (а в программе просто считать освещение в нечеткой логике), нежели методом проб и ошибок подбирать набор условий и постобработок ]:-> Также я теперь понимаю, откуда у идеи libtcod сделать клеточки-из-четырех-клеточек ноги растут, только уж по мне не стоит останавливаться на полпути и следует сразу до пикселей их раздробить =)


Неочевидным следствием из вышесказанного становится следующая проблема: когда видимость ячейки определена по нетривиальному и неочевидному алгоритму, быстро повторить его для простой проверки видно или нет "вот отсюда вот туда" иногда невозможно. Например, тот же брезенхем упорно задевает за стенку, а прямая геометрическая линия либо проходит мимо, либо также пересекает и "невидимую" ячейку. Иными словами, LOS становится какой-никакой, а задачей. Но с этим разберемcя, просто поработать придется. В самом крайнем случае "LOS для монстров, ляляля, ничего не знаю" ^_^.


Оппоненты, ваш ход.

В идеале все три библиотеки должны использовать один и тот же массив. Чтобы сгенерил карту и сразу можешь использовать на ней и ФОВ и поиск пути, остается только монстров добавить. Так что подожду FOV от Cfyz и сделаю вызываемую функцию такой же.

В принципе, как-никак, но для расчета пути можно использовать и текущую FOV_MAP (хотя назвать, наверное, придется по-другому тогда), однако для учета веса проходимости клеток придется добавить еще поле в ячейку. Reserved я оставил впрок с прицелом хранения там указателя (потому и void*) на внутриигровые объекты, которые потом можно будет учитывать/искать/возвращать в разных LOS или подобных.

[Cfyz]

Обалдеть, при сборке MSVC все точненько, при сборке GCC (MinGW) в результатах FOV иногда появляются злющие артефакты. В итоге прикрепленная к предыдущему сообщению дема демонстрирует всякую фигню.
Отставить панику, это разница в округлении. Практически опечатка, спать пора.

[Apromix]

Итак, обещал -- надо что-то показать.

О, потестил, карту изменял - работает Продолжай кодить, не останавливайся, подозреваю, идей еще много

У меня пока только одно пожелание - уменьшить размер файла библиотеки (163 кб - это много) Пробовал ужать UPX'ом - не получилось.

[ADB]

FOV от Cfyz порадовал, достаточно быстрый, и что самое главное, без артефактов.

[Apromix]

Осталось доработать и уменьшить размер библиотеки

[Cfyz]

Осталось доработать и уменьшить размер библиотеки

Доработать -- это да, не спорю. Угол обзора, гексы и LOS. То есть чуть меньше, чем все =)

Размер -- тонкий момент. Если выцарапать из исполняемого файла вообще все, то он начнет сильно зависеть от всяких msvcrt10.dll, которые еще пойди собери у пользователя на компе. Сегодня только видел у одного человека с кучей дизайнерского софта штук десять разных установленных версий Microsoft Visual C++ Runtime.

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

И немного "наоборот" -- если вам нужен минимальный суммарный размер исполняемых файлов, то необходимо использовать статическую сборку, которая включит в .exe только тот код, который реально используется, а не все барахло впрок. Но идея ведь в том, что использовать можно в проектах на разных языках? Тогда придется мириться с тем, что game.exe требует msvcrt80.dll, а BeaRLsmth.dll -- другую версию и этот код придется тащить с собой. Либо внутри самой .dll, либо отдельно в инсталляторе (или, упаси боже, на сайте в инструкции по установке). Учитывая ЦА, мне кажется лучше перестраховаться и получить 200 кб .dll, нежели 20 кб. и отдельный пункт в FAQ "почему же именно у меня ни черта не работает?!1".

[Apromix]

Убедительный довод А как с либой, ее уже можно считать завершенной? Нововведений больше не будет и не планируется?

[Cfyz]

А как с либой, ее уже можно считать завершенной? Нововведений больше не будет и не планируется?

Завершенной считать нельзя ни в коем случае. Нововведения будут, сейчас просто дату назвать не могу. Не бойтесь, у меня нету комплексов на эту тему, если станет не по зубам или надоест, я сообщу ]:->

Там есть косячок-с с тем, что FOV в общем виде несимметричен и LOS становится неочевидным. Элегантного решения не нашел пока.

[kipar]

Например так - для игрок vs монстр LOS определяется по FOV - т.е. освещена ли клетка монстра. Для монстр vs монстр - считать обычным способом. Пока у игрока не появится союзников проблем не будет.

[Cfyz]

Например так - для игрок vs монстр LOS определяется по FOV - т.е. освещена ли клетка монстра. Для монстр vs монстр - считать обычным способом. Пока у игрока не появится союзников проблем не будет.

Надо передавать в LOS для кого именно считаем. Невелика проблема, в принципе, но хак же. Тем более, что смысл вообще считать два раза одни и те же клетки, FOV же уже построен.

Хотите еще логически-техническую проблемку? Идея с хранением в исходной для FOV/LOS структуре указателей на объекты в игре (чтобы LOS их просто списком вернул и не надо было всю карту обходить) -- что делать с дохлыми указателями? Слишком много остается на совести пользователя библиотеки, легко что-то где-то забыть и получить указатель в никуда.

[kipar]

Надо передавать в LOS для кого именно считаем. Невелика проблема, в принципе, но хак же. Тем более, что смысл вообще считать два раза одни и те же клетки, FOV же уже построен.

В этом и идея. Т.е. если надо определить видимость монстра (или видение монстром игрока) - мы просто смотрим, освещена ли клетка.
Точнее для видимости игрока монстром не прокатит - а то будет "ослеп, значит меня никто не видит".

Хотите еще логически-техническую проблемку? Идея с хранением в исходной для FOV/LOS структуре указателей на объекты в игре (чтобы LOS их просто списком вернул и не надо было всю карту обходить) -- что делать с дохлыми указателями? Слишком много остается на совести пользователя библиотеки, легко что-то где-то забыть и получить указатель в никуда.

Думаю над тем же самым по отношению к PF. Пока есть вариант - переложить все управление удалением\созданием на совесть библиотеки.
Т.е. пользователь будет вызывать BearCreateObject\BearDeleteObject для всех игровых объектов. Правда встает вопрос, как красиво хранить в них пользовательскую информацию.

[ADB]

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