Shadow casting

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

Аватара пользователя
Чёрствый Рогалик
Сообщения: 48
Зарегистрирован: 13 фев 2009, 14:35
Откуда: Санкт-Петербург

Shadow casting

Сообщение Чёрствый Рогалик » 20 мар 2009, 11:01

Нашёл в интернете интересную статью http://www.geocities.com/temerra/los_rays.html
Развивающую идею расчёта FOV с помощью Shadow casting, но без необходимости делить FOV на 8 участков.
Попробовал этот алгоритм с некоторыми изменениями (производительность выше, конечный результат немного хуже) – работает, при этом весьма шустро, легко кодится и читается.
Может стоит адаптировать статью для нашего клуба?
Анимэшницы и Велосипеды

Аватара пользователя
Alver
Сообщения: 80
Зарегистрирован: 27 дек 2006, 17:20
Откуда: Москва
Контактная информация:

Re: Shadow casting

Сообщение Alver » 20 мар 2009, 11:11

адаптируй конечно, чем больше будет материала, тем лучше!

Аватара пользователя
Чёрствый Рогалик
Сообщения: 48
Зарегистрирован: 13 фев 2009, 14:35
Откуда: Санкт-Петербург

Re: Shadow casting

Сообщение Чёрствый Рогалик » 20 мар 2009, 11:15

Я попробовал её перевести, но больно она укуренная. :lol:
Сделаем так, я её потихоньку буду переводить, с коментариями.
Максим проверит на предмет грамотности,
таким образом сделаем толковую статью.
Анимэшницы и Велосипеды

Аватара пользователя
Чёрствый Рогалик
Сообщения: 48
Зарегистрирован: 13 фев 2009, 14:35
Откуда: Санкт-Петербург

Re: Shadow casting

Сообщение Чёрствый Рогалик » 20 мар 2009, 12:13

вот, что пока сделал(докидаю по кускам):
Modelling Rays for Line of Sight in an Object-Rich World
Зрение – наше самое эффективное чувство при построении модели окружающего мира. Если мы не сможем воссоздать эту способность надлежащим образом, то управляемые ИИ персонажи никогда не смогут понять мир, так как это делаем мы с вами. Их знание об окружающем мире будет чем-то средним между простейшими предположениями и фиксированном знании, не основанном на мышлении.
Но расчёт настоящей LOS – это весьма сложная в вычислительном отношении операция, и попытка осуществлять постоянные расчёты для большого количества персонажей ляжет тяжелым ярмом на любую машину. Во многих симуляциях (таких как игровой мир игры) используются упрощения (фиксировано маленький радиус обзора, отсутствие препятствий блокирующих зрение) и другие серьёзные допущения предназначенные для снижения затрат машинных ресурсов при расчётах LOS. Но подобная скорость не даётся задаром, мир, в котором реализованы такие методы расчётов для ИИ, слабо детализован и узконаправлен.
По большому счёту, существую два варианта обработки зрения. Так как зрение симметрично (для наших целей, естественно), вы можете спросить себя «Что я могу увидеть?» или же «Что может увидеть меня?». Метод, отвечающий на первый вопрос, сильно зависит от размеров исследуемой площади, так как нам придётся провести проверку последовательно во всех направлениях, пока не наткнёмся на (непрозрачный) объект. В тоже время как способы реализации ответа на второй вопрос сильно зависят от количества объектов, так как нам придётся «взглянуть» на игрока с каждого имеющегося объекта.
Мне не нравится вариант: «Что может видеть меня?», по причине неизбежной неполноты проверки (Собственно из-за чего и достигается преимущество в скорости работы). У персонажа, получающего визуальную информацию посредством прочерчивания «луча» от одного объекта к другому, интересующие объекты могут волшебным образом появляться и исчезать из картины мира. Более того, эти объекты могут исчезать весьма шустро, не сообщая персонажу приемлемого обоснования такого безобразия. Такая информация не сопровождается дополнительными данными об остальной его окружающей среде – вся остальная информация для персонажа поступает из других источников, например «поиск пути» (который тоже может быть весьма мистическим действом, с точки зрения такого персонажа).
«Что я могу видеть?» - куда лучше описывает сам принцип зрения, что вполне очевидно. Обратной стороной этой системы, является то, что она куда более ресурсоёмкая, чем просто проверка отдельных, интересующих нас объектов, но с другой же стороны, мы получаем куда больше информации. Line of sight в таком случае может снабдить нас данными обо всём в пределах видимости, от земли под ногами до здания куда только, что зашел другой персонаж. Так как, непрозрачные участки считаются непроходимыми (прим. пер. Не всегда, конечно, деревья или дым могут быть проходимы, хотя и блокируют LOS, но в большинстве случаев, таки да.) мы можем использовать полученные данные для наших расчётов «поиска пути» и тем самым сэкономить ресурсы на расчётах, the same goes for formulating positional strategy (что это значит?).
Анимэшницы и Велосипеды

Аватара пользователя
BreakMT
WANDER Team
Сообщения: 933
Зарегистрирован: 27 ноя 2006, 12:16

Re: Shadow casting

Сообщение BreakMT » 20 мар 2009, 21:01

вариант "что может видеть меня?" вообще самый глупый... не понимаю зачем нужна эта часть статьи :?

Dmiry
Сообщения: 168
Зарегистрирован: 14 июн 2007, 10:32

Re: Shadow casting

Сообщение Dmiry » 21 мар 2009, 03:41

BreakMT писал(а):вариант "что может видеть меня?" вообще самый глупый... не понимаю зачем нужна эта часть статьи :?
Вот тут http://roguecentral.org/libtcod/fov/fov.pdf есть сравнение алгоритмов FOV, в том числе на симметричность.

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

..........
..@.......
..###z....  Кто кого видит или не видит здесь?
..###.....
Первая заповедь фотолюбителя: Проявил себя - закрепи!

Аватара пользователя
Чёрствый Рогалик
Сообщения: 48
Зарегистрирован: 13 фев 2009, 14:35
Откуда: Санкт-Петербург

Re: Shadow casting

Сообщение Чёрствый Рогалик » 23 мар 2009, 07:25

Я думаю, автор исходил из посылки о расчёте LOS не только для 2D, хотя кто знает, мне тоже не совсем понятно.

В алгоритмах, отвечающих сразу на оба вопроса, эффективность использования памяти приносится в жертву скорости работы (предварительные расчёты). Но это не будет хорошим решением, в случае если у нас есть масса всеразличных условии при обработке зрения или же они постоянно меняются.
В этой статье мы рассмотрим очень быстрый и эффективный алгоритм моделирования «лучей» для ответа на вопрос «Что я могу увидеть?».
Для миров с большим количеством объектов – это в принципе наилучший подход к разрешению вопроса, а также выглядящий наиболее естественный, способ реализации зрения.
Для простоты описания нашего алгоритма используем двухмерный мир с чётко определёнными участками, назовём их «tiles»(как это лучше перевести? Тайлы, квадраты?). Также, будем считать, что у нас есть заранее созданная карта, из которой мы легко можем понять какой участков не является прозрачным.
Самым прямолинейным способом проверить установить зону видимости, в случае с вариантом «Что я могу увидеть?» - это для каждого потенциально видимого участка (tile) (с учётом заранее заданного радиуса), проверить прозрачен он или нет. Стандартным подходом для реализации такого метода будет программно «пройтись» до этого участка используя, что-то вроде алгоритма рисования линий Bresenham`а (Bresenham line-drawing algorithm),и и проверить: встретим ли мы на пути какие-нибудь объекты блокирующие зрение (которые мы будем называть препятствия). Такой способ очевидно неэффективен, так как большая часть наших «проходов» по карте взаимосвязаны (прим. те. в ходе проверки мы будем регулярно проверять уже ранее проверенные участки), но при этом никакого обмена информацией между операциями не осуществляется.
Куда лучше было бы выяснить для каждого участка, находящегося на границе видимой зоны, как далеко мы можем видеть в это направлении. Technically, these walks are really rays that are being cast through a medium that only allows for very discrete measurements. (Текст понятен, но смысл. Мне как гуманитарию не понятно.) Так как мы знаем, что все «лучи» исходят из одного источника мы можем использовать единую для всех максимальную длину во всех направлениях.
Это куда более эффективный подход, но с учётом дискретной природы нашего мира, многие лучи будут проходить через те же самые участки, что и соседние лучи. Используя (Cartesian- помню, что по русски такая система координат называлась по другому) систему координат, в случае если мы источником будет точка (0:0), то до 25% всех наших лучей пройдут через точку (1:0). Даже если у нас будет очень быстрый механизм определяющий - посещали ли мы обрабатываемый участок или нет, то общее количество проводимых проверок, с учётов радиуса видимости и плотности мира, означает, что в любом случае такой алгоритм будет значительно хуже идеального О(n) в части затрат времени и ресурсов.
В этой статье мы рассмотрим алгоритм, который рассчитывает настоящую LOS с высочайшей эффективностью в части расходов времени и ресурсов. Это алгоритм не будет заглядывать в каждую клетку больше одного раза, также он не будет проверять участок за препятствиями, полностью блокирующими направление с точки зрения смотрящего. Для сравнения, на моём 1.6Hz ноутбуке с Java, потребовало примерно 50-60ms, чтобы рассчитать LOS с произвольной точки на карте 600х600 с 5000 случайно расставленных препятствий.
Анимэшницы и Велосипеды

Dmiry
Сообщения: 168
Зарегистрирован: 14 июн 2007, 10:32

Re: Shadow casting

Сообщение Dmiry » 23 мар 2009, 08:33

Cartesian - декартова система координат.
Bresenham - алгоритм Брезенхема
Tiles - тайлы
Первая заповедь фотолюбителя: Проявил себя - закрепи!

Аватара пользователя
Чёрствый Рогалик
Сообщения: 48
Зарегистрирован: 13 фев 2009, 14:35
Откуда: Санкт-Петербург

Re: Shadow casting

Сообщение Чёрствый Рогалик » 23 мар 2009, 10:05

Автор в статье разделяет понятия tiles – те участки на карте (системе координат) и serch nodes – непосредственно проверяемые участки, с одной стороны это логично, так как мы не проверяем сразу всю карту, хотя имхо – только добавляет путаницы.
Дмитрий, огромное спасибо! декартова система координат, конечно же. Всё же я подлый гуманитарий, всё забыл. :lol:


[Картинка] На картинке слева показана основа нашего алгоритма, мы проходим по координатам, проверяя все потенциально видимые участки. Наши графически отображаемы участки (или узлы, как будет лучше?) поиска представляют собой изучаемые в настоящий момент тайлы, а также дочерние участки обрабатываемых тайлов (участки, находящиеся на соседних, максимально удалённых от источника, позициях). Анимированный GIF слева показывает процесс поиска на пустой сетке координат. Синяя точка - источник (точка, по отношению к которой и рассчитывается LOS), а зелёная – граница, расширяющийся периметр нашего поиска (или исследования, как тут красивее написать).
[Картинка] Пока, что это всё выглядит достаточно обыденно, простой алгоритм заливки работает точно также. Отличия станут заметны, когда мы добавим препятствия. Вместо того, чтобы вслепую осуществлять поиск за препятствиями, проверяемые участки нашего алгоритма, запомнят ранее встреченные препятствия (прим. и эта информация будет передана дочерним участкам/узлам) и таким образом мы сможем установить видимость каждого конкретного тайла в пределах текущего периметра. В примере слева имеется одно препятствие, оно отмечено красным, розовым отмечены тени.
Предположим, что мы можем запомнить препятствия и сохранить эту информацию в связанных с ними участках в пределах (изучаемого) периметра, таким образом, мы достигнем очень многого. Мы никогда не посетим один и тот же участок больше чем один раз, и нам потребуется сохранять в памяти текущий периметр, также только один раз.
Но что касается нашей второй задачи – избежать прочерчивания лучей за вытянутыми препятствиями (больше одного тайла)? Любая совокупность препятствий, которая будет шире, чем наш луч (прим. с учётом ранее принятого допущения, что толщина нашего луча равна одному тайлу) – заблокирует все лучи, проходящие за ними. Если бы могли избежать необходимости прочерчивать эти лучи, мы могли бы существенно снизить затраты машинных ресурсов.

[Картинка] Слева показан алгоритм обрабатывающий карту с совокупностью расположенных рядом препятствий (или, если хотите, одним большим препятствием).
Серым отмечены тайлы, хотя и лежащие в пределах исследуемой поверхности, но которые мы никогда не будем проверять, так как точно знаем, что они за пределами нашей линии взгляда.
Как мы знаем, это основано на том, что в изучаемом нами очередном периметре сохраняется информация о всех ранее встреченных препятствиях. В итоге, ресурсоёмкость алгоритма, напрямую зависит от размеров фактически видимой области (прим. автор имел в виду, что за счёт игнорирования гарантированно невидимых участков, достигается экономия машинных ресурсов).
Так как нам в любом случае придётся проверить (нарисовать их и.т.д.) видимые участки, такой вариант будет очень близок к идеальному.
Анимэшницы и Велосипеды

Аватара пользователя
Xecutor
Мастер
Сообщения: 758
Зарегистрирован: 25 мар 2008, 08:32

Re: Shadow casting

Сообщение Xecutor » 06 апр 2009, 07:47

Товарищ Mingos работающий над рогаликом Umbrarum Regnum
разродился очень интересным алгоритмом FoV.
http://groups.google.com/group/rec.game ... e22892e113

Аватара пользователя
Чёрствый Рогалик
Сообщения: 48
Зарегистрирован: 13 фев 2009, 14:35
Откуда: Санкт-Петербург

Re: Shadow casting

Сообщение Чёрствый Рогалик » 20 апр 2009, 08:56

Как это работает.
Метод, с помощью которого мы заминаем встреченные нами в ходе расширения периметра поиска препятствия – является альфой и омегой нашего алгоритма. Как мы помним участки (узлы) поиска создают новые участки на соседних клетках, с координатами, предельно удалёнными от источника (синяя точка). Например, участок с координатами (5:3) создаст участки (6:3) и (5:4). Конечно, (5:4) мог быть уже создан участком (4:4), в таком случае мы не создаём новый. Назовём (4:4) и (5:3) родительскими участками для (5:4). Дочерние узлы наследуют информацию о препятствиях от своих родителей (прим. Кстати, именно этот участок и можно было бы упростить, см ниже.).
[картинка]
На Диаграмме А показан наш периметр до встречи с препятствиями. Ни один из участков не содержит информацию о препятствиях и все клетки видимы. На диаграмме B показан периметр в момент встречи с препятствиями. Участок относящийся к препятствию теперь содержит данные – направление от источника к препятствию, представленное вектором.
На диаграмме С показано, как мы передаём данные о препятствии (полученные на диаграмме В). Заметьте, что два препятствия не являются частью периметра (на диаграмме С), их данные представлены просто для сравнения. Числа в левой стороне квадрата содержать вектор препятствия (X сверху, Y снизу).Заметьте, что новые участки унаследовали векторы родительских участков (участок (3:2) имеет два родительских вектора, но мы разрешим эту проблему чуть позже). Так что, пока, давайте скажем, что мы передаём данные о векторах препятствий, когда инициируем проверку нового периметра.
The numbers on the right represent the offset from the obstruction vector. Препятствия, что не удивительно, начинаются точно точно на векторе препятсвия, так что мы используем одинаковые значения. Как только мы заполним позицию (4,1) информацией, мы также отметим, что это шаг по оси Х. Так как мы продвинулись по оси Х, то нам следует привести данные в соответствие: значение Х уменьшается вектором Y, и значение Y увеличивается вектором Х. Или же, раз мы продвинулись по направлению Х, то наше желание двигаться в направлении Х будет уменьшаться, а желание двигаться в направлении Y – увеличиваться (в объёмах необходимых, чтобы следовать по лучу).
По сути, узлы содержат как информацию о векторе препятсвия, так и error data (нужен адекватный вариант перевода, естественно это не информация об ошибке, мне кажется, было бы правильно перевести это как погрешность.). Это минимальная информация, которая требуется нам для работы, так как нам нужно помнить направление препятсвия, а также нам нужна погрешность, так как в силу дискретности нашего мира мы не можем гарантировать, что будем двигаться точно по вектору.
Узлы не наследуют данные о препятствиях, если находятся слишком далеко от вектора. Узел считается «затенённым» если погрешность укажет, что узел находится достаточно близко к вектору.
Это всё, что требуется для обработки одной линии взгляда с учётом препятствия. Кроме того, если два луча пройдут рядом, то мы получим коллизию, как например в узле (3,2) на диаграмме (с). Мы назовём такие коллизии 'cut' case (завершающими, отрезающими? Как красиво назвать?). В таком случае нам нет необходимости продвигать наш луч в этот узел, так как мы уже знаем всё об этой ветви. В этом случае, как (3,1), так и (2,2) достаточно близки к вектору препятствия, чтобы стать затенёнными.
Можно сказать, что лучи проходящие через обе эти точки наталкиваются на препятствие (n this non-special case the points are the obstructions). Из этого, мы можем логически заключить, что между этими препятствиями нет места для луча, так как под таким углом, с позиции смотрящего, все отбрасывающие тень объекты расположены близко друг к другу.
Следуя этой логике мы можем игнорировать узел (3,2). Мы просто не будем двигаться тута и позволим лучу обойти его по сторонам, очерчивая границы дуги (тени м.б. лучше). Также, мы может оказаться от узлов, что имеют препятствие (и соответственно луч(вектор) за этим препятствие) с одной стороны, так как нам точно известно, что они находятся внутри края тени за препятсвием. Как и обычные узлы препятствий, мы обозначим удалённые узлы розовым цветом на GIFке, так как они всё ещё проверяются алгоритмом, и являются прозрачными. При этом узлы не создаются для позиций у которых оба родительских узла относятся к удалённым (обрезающим), так как они банально находятся в пределах тени за препятствием, такие непроверяемые участки отмены на GIFке серым.
Анимэшницы и Велосипеды

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Shadow casting

Сообщение Максим Кич » 20 апр 2009, 12:39

Чёрствый Рогалик писал(а): По сути, узлы содержат как информацию о векторе препятсвия, так и error data (нужен адекватный вариант перевода, естественно это не информация об ошибке, мне кажется, было бы правильно перевести это как погрешность.).
«Значение ошибки», судя по аналогичным материалам. Хотя «погрешность» мне нравится больше, я не уверен, применим ли этот термин в данном случае.
Dump the screen? [y/n]

Аватара пользователя
Чёрствый Рогалик
Сообщения: 48
Зарегистрирован: 13 фев 2009, 14:35
Откуда: Санкт-Петербург

Re: Shadow casting

Сообщение Чёрствый Рогалик » 20 апр 2009, 16:19

Хмм... За перевод статьи, который ещё ого-го как нужно доработать, я сел после того как опробовал алгоритм на практике. imho, "погрешность" и правда лучше отражает то, что хотел сказать автор. Более того, как думаю Вы заметили, статью я переводил относительно вольно, стараясь сделать её понятнее чем у автора. :lol:

EDIT: думаю завтра закончу с переводом статьи на русский и начну перевод с русского на русский человеческий, а то это больше похоже на перевод сократом :roll:
Анимэшницы и Велосипеды

Аватара пользователя
Savaro
Сообщения: 16
Зарегистрирован: 05 авг 2009, 12:39
Откуда: Губкин
Контактная информация:

Re: Shadow casting

Сообщение Savaro » 05 авг 2009, 12:58

Это... если многие реализовывали этот метод...

зачем переводить...
можете на "пальцах" по шагам его обьяснить? :oops:

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Shadow casting

Сообщение Максим Кич » 06 авг 2009, 06:46

Savaro писал(а):Это... если многие реализовывали этот метод...

зачем переводить...
можете на "пальцах" по шагам его обьяснить? :oops:
Вообще-то, насколько я понимаю, его здесь никто не реализовывал, кроме автора. Потом, в любом случае количество лосей, фактически, равняется количеству рогаликов, потому что остальная часть проекта всё равно наложит свои ограничения и выдвинет свои требования. И зачастую просто нет смысла воротить сверхбыстрый абсолютно симметричный алгоритм там, где достаточно подобия адомовской «клюшки».

Юмор же данной конкретной ситуации заключается в том, что статья как раз и содержит пошаговое описание «на пальцах».
Dump the screen? [y/n]

Ответить

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

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