|
|
|
|
Канал Игры Мечты: «Алгоритмические вопросы.» |
|
|
|
Guest
 2075 EGP
           
Рейтинг канала: 5(167)
Репутация: 376
Сообщения: 27975
Откуда: Моск.
Зарегистрирован: 12.10.2004
   |
|
А есть известный на момент расчёта освещения набор координат ячеек с источниками света?
_________________
Трещит земля как пустой орех
Как щепка трещит броня |
|
|
|
Shirson
1605 EGP
   
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
Да, это можно организовать.
_________________
У меня бисера не доxеpа. |
|
|
|
Guest
2075 EGP
Рейтинг канала: 5(167)
Репутация: 376
Сообщения: 27975
Откуда: Моск.
Зарегистрирован: 12.10.2004
|
|
Насколько статично освещение?
Если нужно просто оптимизировать проход по массиву из угла в угол - идей сильных сходу нет. Разве что при изменении уровня освещения одной ячейки не на п.1 идти, а в обратную сторону по массиву, т.к. дальность воздействия изменившейся ячейки больше чем на 15 строчек не распространяется...
Если допустимо изменить направление расчёта, то
|
Cкрытый текст (кликните здесь для просмотра)
Я сейчас смотрю на алгоритм волновой трассировки.
И у меня есть смутная мысль.
Пустить волну от первого источника на поле. Начинать с яркости источника, каждую итерацию записывать в ячейки на 1 меньше предыдущей итерации, пока не станет 0. Судя по алгоритму назначения освещённости каждой ячейке их освещённость обратно пропорциональна расстоянию от источников света. Максимальная дальность прохода волны от источника не больше уровня яркости источника, т.к. каждый шаг дальности отнимает единицу. Это уже сэкономит проход по ячейкам, до которых свет не достаёт.
Далее, пустить волну от второго (следующего) источника - и в ячейке сравнивать текущее (от предыдущей волны) значение освещения в ячейке и новое. Назначать максимум из этих двух (это не ломает условие "максимум из окрестных ячеек -1", поскольку соответствует свету либо самой мощной из предыдущих волн, либо текущей).
Алгоритм распространения волны есть в Вики. Это окрестности фон Неймана возрастающих порядков от источника света.
Вышесказанное не работает, если по массиву нужно бежать из угла в угол...
Кроме этого я не уверен, что это будет быстрее, чем проход по исходному алгоритму, т.к. скорость волновой трассировки будет зависеть от количества источников и того, насколько часто будет меняться их положение. При изменении яркости или положения одного источника необходимо пересчитать здоровенную зону. Фактически, пересчитать всё освещение от всех источников в той зоне, куда доставал этот изменившийся источник. И потом ещё раз - зону нового освещения. Но это всё равно не весь массив целиком. Лампочка не может достать изменениями больше чем окрестность 15-го порядка.
|
_________________
Трещит земля как пустой орех
Как щепка трещит броня
Последний раз редактировалось: Guest (18:11 11-09-2014), всего редактировалось 1 раз |
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
Освещение идет исключительно от "источников света"?
Если да, то можно ли переформулировать задачу так:
Освещенность ячейки = clamp(15 - манхеттенское расстояние до ближайшего источника света, 0, 15);
?
_________________
MOV topka, C++ |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
Да, можно и так.
Суть вопроса от этого не сильно меняется, потому как нужно считать это самое расстояние и находить источники света.
Собственно, меня интересует этот алгоритм как раз из за того, что он ориентирован на просчёт от ячеек, а не от источников света. Если половина экрана будет залита светящейся лавой, этот алгоритм всё равно будет работать и не вильно медлнее, чем с пятком точечных.
Если же плясать от источников света, то всё сильно груснее (как в примере с лавой)
_________________
У меня бисера не доxеpа. |
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
Можно использовать 2d-tree (частный случай kd-tree) для поиска "ближайшего источника света ячейки". Такой поиск имеет сложность O_kd = O(h) + O(h log h), где h - высота дерева, что гарантированно меньше чем n. Где n - кол-во источников света.
Для каждой ячейки свет считается за O(n * O_kd). Плясать от источников света, да.
| Shirson : |
|
Собственно, меня интересует этот алгоритм как раз из за того, что он ориентирован на просчёт от ячеек, а не от источников света. Если половина экрана будет залита светящейся лавой, этот алгоритм всё равно будет работать и не вильно медлнее, чем с пятком точечных.
|
С условием что такой алгоритм кто-то напишет. Я вот не вижу способа не плясать от источников света.
_________________
MOV topka, C++ |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| Jurec : |
|
С условием что такой алгоритм кто-то напишет. Я вот не вижу способа не плясать от источников света.
|
Собственно, я алгоритм "от ячейки" и собираюсь написать 
Он будет кастить лучи из каждой видимой ячейки до "протухания" по видимости или дальности (скажем, при условии, что есть 16 уровней освещённости, дальше дистанции 16 трейсить смысла нет) и, натыкаясь на источники света, считая освещённость по дальности.
Заведомо стабильная скорость работы, независимо от количества источников света (хоть всю карту ими утыкай). Разве что меня смущает, это кастинг с каждой точки - может оказаться ресурсоёмкой штукой (а может и нет - сейчас РОС делаю)
А этот алгоритм (в вопросе) просто рассматриваю в качестве варианта и/или дополнения
_________________
У меня бисера не доxеpа.
Последний раз редактировалось: Shirson (19:06 11-09-2014), всего редактировалось 2 раз(а) |
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
Я не понял твой алгоритм. Можно как-то подробнее? Чтоб можно было прикинуть алгоритмическую сложность.
_________________
MOV topka, C++
Последний раз редактировалось: Jurec (19:16 11-09-2014), всего редактировалось 1 раз |
|
|
|
Minx
 979 EGP
  
Рейтинг канала: 6(328)
Репутация: 135
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| Shirson : |
|
Он будет кастить лучи из каждой видимой ячейки до "протухания" по видимости или дальности (скажем, при условии, что есть 16 уровней освещённости, дальше дистанции 16 трейсить смысла нет) и, натыкаясь на источники света, считая освещённость по дальности.
|
Даже если наткнулся на источник света, то все равно придется идти дальше, пока не будет расстояние 16, т.к. там дальше может быть ещё один источник света.
Итого операций: 16*16/2 * (общая площадь)
Если устраивает, то проще так и оставить (т.к. простой вариант). Но можно и подумать над ускорением.
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| Jurec : |
|
Я не понял твой алгоритм. Можно как-то подробнее? Чтоб можно было прикинуть алгоритмическую сложность.
|
У меня задачи решаются для рогалика, т.е. пространство дискретезировано, условно, можно представить, что работаешь в двумерном массиве.
1. Вычисляются ячейки, видимые из ячейки наблюдателя.
2. Для каждой такой ячейки кастятся лучи на дистанцию (макс уровень света)
* Луч, двигаясь по массиву, собирает данные о среде (поглощение)
* Наткнувшись на источник света, до него считается дистанция (честная), к нему применяентся затухание от дистанции и накладывается собранное поглощение. Если текущий уровень освещённости ячейки меньше полученного, ей приписывается новый.
* (тут можно оптимизировать, обрывая луч, если дистанция, которую он уже прошёл, заведомо предотврящает увеличение текущей освещённости ячейки).
* Наткнувшить на непрозрачное препятствие, луч останавливается.
Всё.
_________________
У меня бисера не доxеpа.
Последний раз редактировалось: Shirson (19:30 11-09-2014), всего редактировалось 1 раз |
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
| Shirson : |
|
Для каждой такой ячейки кастятся лучи на дистанцию (макс уровень света)
|
Как именно кастятся лучи? От ячейки, во всех направлениях на длинну 16?
А сколько милисекунд занимает просчет всего? Я просто не пойму что оптимизировать тогда.
При таких небольших данных на первое место выходит вопрос - насколько код дружит с кешем процессора, а не кол-во итераций алгоритма или другая его алгоритмическая сложность.
_________________
MOV topka, C++ |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| Jurec : |
|
Как именно кастятся лучи? От ячейки, во всех направлениях на длинну 16?
|
Да. Линиями Брезенхема из ячейки в каждую точку окружности Брезенхема с радиусом 16.
| Цитата: |
|
А сколько милисекунд занимает просчет всего? Я просто не пойму что оптимизировать тогда.
|
А я и не спрашиваю, что тут оптимизировать У меня совсем другой вопрос, по совсем другому алгоритму.
_________________
У меня бисера не доxеpа. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 135
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| Minx : |
Итого операций: 16*16/2 * (общая площадь)
Если устраивает, то проще так и оставить (т.к. простой вариант). Но можно и подумать над ускорением.
|
Могу предложить более менее простой алгоритм, который побыстрее этого. Наверное в 32 раза.
Каждый источник света рассмотрим отдельно в четвертьплоскости. Например если света 4, и вправо-вниз 1/4-плоскость, то он светит так:
| Код: |
000000
043210
032100
021000
010000
000000 |
Считаем освещение для всех источников в этой 1/4-плоскости. Для этого перебираем циклом бегущей диагонали (с верхнего левого угла в правый нижний). Как-то так:
| Код: |
.0000 0.000 00.00 000.0
00000 .0000 0.000 00.00
00000 00000 .0000 0.000
00000 00000 00000 .0000
00000 00000 00000 00000
|
Если во время перебора встречается источник, то он поджигает элемент бегущей диагонали. Например если встретили 4-ку ниже, то получим следующее:
| Код: |
.0000 04000 04300 04320 04321 04321 04321
00000 .0000 03000 03200 03210 0321. 03210
00000 00000 .0000 02000 02100 021.0 0210.
00000 00000 00000 .0000 01000 01.00 010.0
00000 00000 00000 00000 .0000 0.000 00.00
|
Соответственно, если по ходу есть другие источники, то они также поджигают диагональ. Например 5-ка в центре:
| Код: |
.0000 04000 04300 04320 04321 04321 04321 04321 04321
00000 .0000 03000 03200 03210 0321. 03210 03210 03210
00000 00000 .0000 02000 02500 02540 02543 02543 02543
00000 00000 00000 .0000 01000 01400 01430 01432 01432
00000 00000 00000 00000 .0000 0.000 00300 00320 00321
|
Т.о. мы посчитали все, что светит вправо-вниз. (не стоит смущаться неестественностям).
Теперь достаточно тжс сделать для остальных 3-х четвертьплоскостей. Далее наложить друг на друга и посчитать максимальное.
Ускорение засчет того, что множество операций с перебором в 16 шагов сливаются в одну операцию.
Ещё может понадобиться то, что число 16 уже не влияет на сложность. Можно сделать больше градаций при необходимости.
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (19:53 11-09-2014), всего редактировалось 2 раз(а) |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
Вообще интересная метода.
А как заглаживать косяки, что около пятёрки единицы? Выровняется при остальных прогонах, видимо?
Еще не очень понятно, как сюда включить поглощение среды, препятствия и пр.
_________________
У меня бисера не доxеpа.
Последний раз редактировалось: Shirson (20:04 11-09-2014), всего редактировалось 2 раз(а) |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 135
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| Shirson : |
|
А как заглаживать косяки, что около пятёрки единицы? Выровняется при остальных прогонах, видимо?
|
Исправится после обработки всех 4-х четвертьплоскостей. Прогон только один (прогон это одна такая операция на каждую четвертьплоскость).
| Shirson : |
|
Еще не очень понятно, как сюда включить поглощение среды, препятствия и пр.
|
Поглощение среды такое же, как и в других методах. Здесь взял минус один для каждого перехода по горизонтали и вертикали.
Препятствие оно облетает не всегда. Точнее, могу предложить два варианта (не факт что оба устроят):
1 Госим диагональ при проходе:
| Код: |
8**00
7**00
65432
54321 |
2 Рисуем, но препятствие не рисуем:
| Код: |
8**54
7**43
65432
54321 |
Если нужно чтобы свет "заворачивал за угол" (облетал препятствие):
| Код: |
8**10
7**21
65432
54321 |
то это нужно уже несколько прогонов делать (число поворотов + 1 для сравнения).
Для 16 у меня получилось максимум 5 прогонов (без +1).
добавлено спустя 33 минуты:
| Minx : |
|
то это нужно уже несколько прогонов делать (число поворотов + 1 для сравнения).
|
Как вариант, можно ещё идентифицировать факт поворота и решать проблему локальной заливкой (если уж так хочется скорости).
Т.е. если мы делаем при четвертьплоскости вправо-вниз и движение вправо, то можем понять, что препятствие сверху переходит в непрепятствие. Соответственно, это поворот и здесь можно запустить локальную заливку.
Это оставит скорость на уровне 1 прогона, но значительно усложнит сам алгоритм. По-моему, лучше попробовать сначала чего-нибудь попроще (тем же 5 прогонов) и посмотреть на скорость, т.к. преждевременная оптимизация.
---
Вообще, мне это все очень напоминает заливки, но при них изменяется цвет. С этими мыслями мне вспомнился один алгоритм, но кодить его ещё сложнее. Пока что в обсуждении думаю он излишен.
И ещё пришло в голову то, что обычная заливка из источников света на самом деле работать будет быстро и в случае с лавой. Особенность в том, что если мы заливаем из источника света, и наткнулись на другой источник света, то обратная волна уткнется в первый источник света и быстро захлебнется. Поэтому заливка волной должна отработать относительно быстро.
Боюсь даже, что в данном рогаликовом случае самой быстрой и простой будет эвристика. Например, берем все поле 49х49 и в каждом квадрате 7x7 (в каждом из 49-ти шт) ищем самый сильный источник света. Это стартовые точки заливок. И далее заливка, где практически нет обратной волны. Ну, и не забыть потом долить в области, которые недолились (закрытые от заливок).
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (20:58 11-09-2014), всего редактировалось 6 раз(а) |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 135
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| Minx : |
1 Госим диагональ при проходе:
| Код: |
8**00
7**00
65432
54321 |
|
Ещё есть третий вариант, который по-моему, даже более естественный:
| Код: |
456787**00
345676**00
2345650000
1234540000
0123430000
45678**00
34567**00
**4560000
003450000
002340000 |
Все те же 4 прохода по диагонали, усложнение алга небольшое.
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| Minx : |
| Minx : |
1 Госим диагональ при проходе:
| Код: |
8**00
7**00
65432
54321 |
|
Ещё есть третий вариант, который по-моему, даже более естественный:
| Код: |
456787**00
345676**00
2345650000
1234540000
0123430000
45678**00
34567**00
**4560000
003450000
002340000 |
Все те же 4 прохода по диагонали, усложнение алга небольшое.
|
Если 8ка это источик света, то в обоих случаях его распространение посчитано неверно.
456787**00
345676**00
2345650000
1234540000
0123430000
45678**00
34567**00
**4560000
003450000
002340000
_________________
У меня бисера не доxеpа. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 135
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| Shirson : |
Если 8ка это источик света, то в обоих случаях его распространение посчитано неверно.
456787**00
345676**00
2345650000
1234540000
0123430000
45678**00
34567**00
**4560000
003450000
002340000
|
Тогда это противоречит исходной постановке алгоритма: http://www.elite-games.ru/conference/viewtopic.php?p=3152599#3152599 ..
И только "заворачивал за угол" подходит..
Поопределиться бы, чего хочется..
Например не понятно, чего рисовать в следующем случае:
8987*00
7876*00
67654??
565432?
454321
А то как-то начинаем с одной задачи, а внезапно появляется Брезенхем..
Или имеется ввиду что виден-невиден по Брезенхему, а то что видно яркость определяется по ищуемому алгоритму? Тогда могу предложить "1 Госим диагональ при проходе" (т.к. он захыватывает все, что видимо и даже больше), и нулями записывать невидимое по Брезенхему (отсекает чего там напрямую невидимо). Т.к. тогда получается, что яркость и видимость это две разные задачи.
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (17:07 12-09-2014), всего редактировалось 1 раз |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
Твоя метода ему противоречит Заливка - нет.
| Цитата: |
|
Поопределиться бы, чего хочется..
|
Как минимум наличие света там, где оно должно быть.
| Цитата: |
Например не понятно, чего рисовать в следующем случае:
8987*00
7876*00
67654??
565432?
454321
|
Очевидно
8987*00
7876*00
676543
5654322
454321
| Цитата: |
|
А то как-то начинаем с одной задачи, а внезапно появляется Брезенхем..
|
Решение противоречит изначальной задаче.
Меня интересовал способ получить быстрый и "халявный" алгоритм "от ячейки", а не "от источника света". Вариант с бегучей диагональю интерсен, при варианте с работаботающим затеканием. Буду тыкать палочкой и смотреть, что получится.
Скорее всего появится кадаврик, включающий в себя части всякого
_________________
У меня бисера не доxеpа. |
|
|
|
Guest
2075 EGP
Рейтинг канала: 5(167)
Репутация: 376
Сообщения: 27975
Откуда: Моск.
Зарегистрирован: 12.10.2004
|
|
| Shirson : |
8987*00
7876*00
676543
5654322
454321
|
А почему 2?  А разве не 1?
_________________
Трещит земля как пустой орех
Как щепка трещит броня |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «Алгоритмические вопросы.» |
|
|
