Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / кластеризация пикселей оО (3 стр)

кластеризация пикселей оО (3 стр)

Поделиться
Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 5 Следующая

MiraПостоялецwww13 ноя. 201719:55#30
MrShoor
всмысле, кластеризация хорошо сработает для луж. путь до них можно обычным А* найти быстро.

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

MiraПостоялецwww13 ноя. 201720:01#31
что я думаю, нам по сути хранить все точки не обязательно. достаточно знать периметры, их мы можем вычислить из собранных кластеров.
если надо дойти до "лужи" . каким то образом считаем расстояние до ближайшей. у этой лужи делаем квиксорт периметральных пикселей и идем к ближнему... 
MrShoorУчастникwww13 ноя. 201720:12#32
Mira
> достаточно знать периметры, их мы можем вычислить из собранных кластеров.
Но это же ускорит дейкстру, ты же понимаешь?
Mira
> у этой лужи делаем квиксорт
Квиксорт то зачем? Чтобы найти ближайший пиксель сортировка не нужна.

Если у тебя в карте куча куча пространства, то можно хранить карту как я уже говорил в sparse quad tree. Вот рисуночек того о чем я говорю:
Изображение
Тогда и памяти меньше уйдет, и дейкстра будет пошустрее.

Правка: 13 ноя. 2017 20:13

skalogryzПостоялецwww13 ноя. 201720:15#33
Mira
> что я думаю, нам по сути хранить все точки не обязательно. достаточно знать
> периметры, их мы можем вычислить из собранных кластеров.
> если надо дойти до "лужи" . каким то образом считаем расстояние до ближайшей. у
> этой лужи делаем квиксорт периметральных пикселей и идем к ближнему
а знать отдельные лужи? (зачем разбивка на кластрЫ луж)

что мешает запустить A* поиск до нахождения первой ячейки любой лужи.

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

MrShoorУчастникwww13 ноя. 201720:21#34
skalogryz
> что мешает запустить A* поиск до нахождения первой ячейки любой лужи.
Зеленое лужа. Красный пиксель - это мы. Яркозеленый - это первый попавшийся пиксель лужи:
+ Показать

A* нас будет долго вести вдоль лужи, хотя лужа совсем рядом.
MiraПостоялецwww13 ноя. 201720:41#35
MrShoor
> Но это же ускорит дейкстру, ты же понимаешь?
по моему дейкстре все равно)
skalogryzПостоялецwww13 ноя. 201720:55#36
MrShoor
Ликбез :(
Действительно у меня не А*, а волновой алгоритм.

Идём в ширь, проверяем каждую точку. При обнаружении первой лужи, восстанавливаем путь

skalogryzПостоялецwww14 ноя. 20177:52#37
MrShoor
> У тебя пока никакой реализации нет. Предлагаю тебе набросать свою реализацию, и
> убедиться что эти лишние проверки будут и у тебя.
Набросал, а вот удаление поленился писать.
временные замеры довольно ужасные, но потому, что поиск отрезков линейный.

Правка: 14 ноя. 2017 7:53

MiraПостоялецwww14 ноя. 20178:29#38
Вечером поглядим)
У меня 48мс занимает построение кластеров, на  картинке 512*512
mr.DIMASПостоялецwww14 ноя. 20179:15#39
Flood fill предлагали? http://lodev.org/cgtutor/floodfill.html

Бери сразу stack-based версию - остальные на больших картах сразу дают stack overflow.

Алгоритм обнаружения кластеров тогда будет следующий:

old = зеленый пиксель (как в нульпосте)

zoneId = 0
for y = 0 to height
  for x = 0 to width
    filledCount = FloodFill(x, y, zoneId, old)
  
    if filledCount > 0
      zoneId = zoneId + 1
    end
  end
end  

После прогона алгоритмом каждый зеленый островок (нульпост) будет помечен своим индексом. Размеры залитой зоны (min, max) можно найти в том же flood fill'e а потом вычислить их центр=(max+min)*0.5

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

Правка: 14 ноя. 2017 9:17

MiraПостоялецwww14 ноя. 20179:44#40
mr.DIMAS
Судя по всему мы с mrshoor это и сделали)
Кстати да,  пришлось переделать на безрекурсивную.  В отдельных случаях стековерфлов случался
MrShoorУчастникwww14 ноя. 201710:26#41
skalogryz
> Набросал, а вот удаление поленился писать.
Посмотрел. Чет жесть какая-то.
Пока у меня создается ощущение, что вся карта разбивается на горизонтальные линии (оффсет + длина), которые ты потом пытаешься как-то связать. Но самое главное, что у тебя сохранились четыре +- проверки для каждого пикселя (там теперь даже больше проверок, но не суть). Конечно она теперь совсем неявная, но я покажу.
Первый раз ты делаешь эту проверку когда вставляешь пиксель в горизонтальную ячейку. Внутри SearchPos у тебя почти аналог на x-1 проверку (только теперь ты перебираешь все сегменты, пока не найдешь подходящий, теперь там больше проверок). Далее тебе надо помержить с сегментом справа. Это аналог x+1 проверки.
Оставшиеся две +-y проверки ты делаешь в LinkVertByX передавая туда lines[Yofs-1] и lines[Yofs+1].

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

p.s. Ну и на выходе у тебя куда более сложная структура вышла, чем у меня.
MrShoorУчастникwww14 ноя. 201710:30#42
Mira
> Кстати да,  пришлось переделать на безрекурсивную.
Закину сюда безрекурсивную функцию (надеюсь ты не против, может кому пригодится):
+ Показать

А вообще да, FloodFill - это лишь название алгоритма закраски пикселей. И простейшая реализация как раз через поиск в глубину (dfs). Вот:

+ Показать

О чем на странице с флудфилом и сказано:
All these algorithms are some form of depth first search (but the scanline based ones are more specialized).

Правка: 14 ноя. 2017 10:36

MiraПостоялецwww14 ноя. 201711:53#43
MrShoor
Мне сканлайновые не очень подходят,  так как это постпроцессинг обычно.
Тут в принципе все максимально просто,  оптимизировать нече.  Скорость на хешировании садится больше всего.  Осталось эти кластеры тепер превратить в периметры и поглядеть че выйдет
skalogryzПостоялецwww14 ноя. 201716:54#44
MrShoor
> Посмотрел. Чет жесть какая-то.
> Пока у меня создается ощущение, что вся карта разбивается на горизонтальные
> линии (оффсет + длина), которые ты потом пытаешься как-то связать.
всё как я и обещал!
> В списке хранить только кластерные пиксели. При это хранить их как первый пиксель+длинна
вся карта это список отрезков.
Каждый отрезок связан либо с соседним (слева) отрезком (в той же линии), и со всем отрезками сверху и с низу.
(todo: поменять список на сортированный массив, для удобства поиска)
по-сути бОльшая часть кода это подержание структуры в акатульном состоянии.

MrShoor
> Но самое главное, что у тебя сохранились четыре +- проверки для каждого
> пикселя (там теперь даже больше проверок, но не суть).
она есть для каждого >добавленного< пикселя, потому что нужда проверить соседей никуда не девается.
Но она не продолжается рекурсивно, потому что подразумевается, что информация о соседях уже есть.

Такая ситуация:
Есть 4 несвязаных кластера, в форме креста.
Всередину добавляется новый пиксель.

    []
    []
[][]><[][]
    []
    []   
в твоей реализации нужно пройтись по всем 8 + 1 пикселям (и 17 пограничных пустышек) , объединяя их в кластер.
в мой реализации проверка будет только по +1 пикселям (4 соседа)... ну и перекраска 7 клеток (поставленный пиксель (1),  примет цвет соседнего кластера, и все присоединённые кластеры будут перекрашены в присоединённый цвет (6)).

Mira
> Осталось эти кластеры тепер превратить в периметры и поглядеть че выйдет
я всё ещё не понимаю почему тебе нужны периметры и центры. Если задача состоит в том, чтобы найти ближайшую цель (и путь до неё)?
затраты будут меньше, чем разбиение на лужи.

Страницы: 1 2 3 4 5 Следующая

/ Форум / Программирование игр / Общее

2001—2017 © GameDev.ru — Разработка игр