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

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

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

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

MrShoorУчастникwww14 ноя. 201717:42#45
skalogryz
> в твоей реализации нужно пройтись по всем 8 + 1 пикселям
В моей реализации нет вообще такого механизма: добавляем пиксель к уже существующим кластерам. У меня просто изначально есть пиксели, которые объединяются в кластер. На каждый пиксель только 4 проверки. Чтобы построить кластер из данного креста мой код выполнит ровно 9*4 + 1 проверок. Что как бы линейное время. У тебя количество операций предсказать проблематично, но меньше O(N) сделать это впринципе невозможно. Все, на чем твой код мог бы выйграть - это уменьшение константы O(1), но глядя на тот код верится чет с трудом.
В общем предлагаю сделать бенчмарк. :)
Причем я даже согласен на бенчмарк на твоих условиях (то есть ты можешь подобрать данные, которые выгодны твоему алгоритму). Если согласен, то я жду от тебя битмап. :)
skalogryzПостоялецwww14 ноя. 201718:49#46
MrShoor
> В общем предлагаю сделать бенчмарк.
бенчмарк постпроцессинга?
ну, как мне кажется, ты выиграешь с линейной зависимостью.
или, нужно:
Mira
> в идеале чтоб эти кластеры создавались в процессе попиксельного добавления
> добавления , а не постпроцессинг.

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

procedure SetSize(x,y: integer); // устаналивает размер поля (ну и инициализация структуры)
procedure SetGreen(x,y: integer); // устанавливает пиксель на карте
function GetResult: integer; // возвращает количество кластеров (для проверки привильности алгоритма)
procedure ReleaseTest; // санитария...

Проблема в том, что сейчас программа меряет время всех вызовов SetGreen(), подразумевая, что каждый такой вызов вернёт актуальное состояние кластеров.

Если в твоём алгоритме пересобирать все кластеры после каждого добавления пикселя, то О(n^2) получается... не?
какую задачу мерять? :)

Правка: 14 ноя. 2017 19:01

MrShoorУчастникwww14 ноя. 201719:11#47
skalogryz
Ну не вопрос, я могу минимально доработать алгоритм, чтобы он умел мейнтейнить текущие кластера (просто буду хранить TCluster-а и добавлю мапу с сылкой на эти кластера). И будем тогда добавлять по одному пикселю.
Я просто не делал этот алгоритм, потому что добавление там тривиально, проверить 4 соседей и помержить списки если надо.
А вот постпроцесс и удаление чуть сложнее.
В общем я по прежнему не вижу плюсов от твоего велосипеда из структур. :)
skalogryzПостоялецwww14 ноя. 201719:14#48
MrShoor
> В общем я по прежнему не вижу плюсов от твоего велосипеда из структур. :)
1) велосипед
2) объём памяти

> Ну не вопрос, я могу минимально доработать алгоритм, чтобы он умел
> мейнтейнить текущие кластера (просто буду хранить TCluster-а и добавлю мапу с сылкой на эти кластера). И будем тогда добавлять по одному пикселю.
по-моему Mira будет просто в восторге!
ну и бенчмарчиться будет интереснее

Правка: 14 ноя. 2017 19:15

MrShoorУчастникwww14 ноя. 201719:21#49
skalogryz
> 1) велосипед
Ну ок. Главное не упасть при езде.
skalogryz
> 2) объём памяти
А вот тут уже спорный момент. Понятно конечно, что ты хранишь оффсет + длину на строку. А еще ты хранишь кучу указателей на поддержание этой структуры из линкедлистов. А еще сами объекты отжирают лишние байты. Поэтому чтобы вырваться вперед твоему коду нужны непрерывные строки в десятки пикселей. В общем по памяти тут спорный момент.
MrShoorУчастникwww14 ноя. 201719:22#50
skalogryz
> по-моему Mira будет просто в восторге!
> ну и бенчмарчиться будет интереснее
Ок. Готовь битмап. ;)
Я сейчас с телефона. Буду у компа - доработаю код.
skalogryzПостоялецwww14 ноя. 201719:27#51
MrShoor
> Поэтому чтобы вырваться вперед твоему коду нужны непрерывные строки в десятки
> пикселей. В общем по памяти тут спорный момент.
глядя на изначальный пример, прицел был именно на то, что "лужи" будут тянуться на килобайты пикселей.
вполне готов проиграть по памяти на худших случаях! :)

MrShoor
> Я сейчас с телефона. Буду у компа - доработаю код.
да и я тоже не готов к бенчмарку. я себя уже мерял, там срам и позор!

MrShoorУчастникwww14 ноя. 201719:31#52
skalogryz
> вполне готов проиграть по памяти на худших случаях! :)
> да и я тоже не готов к бенчмарку. я себя уже мерял, там срам и позор!
Эм... так а что мы бенчить будем то? Или не будем? Или доработам код и таки будем?
skalogryzПостоялецwww14 ноя. 201719:35#53
MrShoor
> Эм... так а что мы бенчить будем то? Или не будем? Или доработам код и таки
> будем?
1) пошаговое добавление пикселей при условии, что на каждом добавлении сохраняется актуальность кластеров.
2) пошаговое удаление пикселей.

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

я вполне принимаю, что в геймдеве битмапы размером 512 Mb x 512 Mb встречаются только в мегатекстурах.
А вот игровые карты ну не больше 2048x2048, т.е. острая нужда экономии памяти (в ущерб простоте реализации) сомнительна.

ЗЫ: чего я до сих пор понять не могу, почему нельзя было обойтись просто нахождением ближайшей лужи (без разбиения на кластеры)

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

MrShoorУчастникwww14 ноя. 201719:44#54
skalogryz
> 1) пошаговое добавление пикселей при условии, что на каждом добавлении
> сохраняется актуальность кластеров.
> 2) пошаговое удаление пикселей.
Ок. Не вопрос.

skalogryz
> Есть ещё вариант, ничего не этого не делать, подождать когда придёт Mira, и
> скажет, что последний вариант алгоритма (без рекурсии) вполне устраивает.
> Тогда смысл любых тестов отпадает.
Эй, ну как же отпадает. Мы же just for fun вроде это делаем. Ну я по крайней мере делаю так, а бонусом идет то, что Mira получает решение.

skalogryz
> ЗЫ: чего я до сих пор понять не могу, почему нельзя было обойтись просто
> нахождением ближайшей лужи (без разбиения на кластеры)
Я честно говоря вообще не совсем понимаю что он с ними задумал. Он скидывал мне карту, там вокруг здания обведено оранжевым, и типа в это оранжевое можно спрыгивать с крыши здания. Это типа лужа. Есть подозрение, что он хочет там ям нарыть, и важно знать в какую из ям нужно прыгать, чтобы добраться до врага. А то так можно спрыгнуть в изолированную яму и куковать там.

MiraПостоялецwww14 ноя. 201719:54#55
MrShoor
> А то так можно спрыгнуть в изолированную яму и куковать там.
это кстати тоже нужно учесть -_-, или избегать таких ям при проектировании считая еще одним техническим ограничением
skalogryzПостоялецwww14 ноя. 201720:00#56
MrShoor
> Мы же just for fun вроде это делаем
я победю! обход графа быстрее хэширования! (•̀o•́)ง

MrShoor
> Он скидывал мне карту, там вокруг здания обведено оранжевым, и типа в это
> оранжевое можно спрыгивать с крыши здания. Это типа лужа. Есть подозрение, что
> он хочет там ям нарыть, и важно знать в какую из ям нужно прыгать, чтобы
> добраться до врага. А то так можно спрыгнуть в изолированную яму и куковать там.
A*
просто он осложнён контекстом: если юнит находится на крыше, то край-крыши становится проходимой точкой
если юнит находится на земле, то край-крыши становится проходимой точкой только если там есть лестница.

После этого, если юниту явно не приказать - прыгай в яму, то... как он туда попадёт?

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

MrShoorУчастникwww14 ноя. 201720:20#57
skalogryz
> я победю!
Хех, посмотрим.

skalogryz
> если юниту явно не приказать - прыгай в яму, то... как он туда попадёт?
Смотри. Игрок залазит в яму, и начинает стрелять по боту. А боту больно, боту обидно. Нужно отомстить обидчику, и ничего не остается как спрыгнуть к игроку в яму.

skalogryzПостоялецwww14 ноя. 201720:36#58
MrShoor
> Смотри. Игрок залазит в яму, и начинает стрелять по боту. А боту больно, боту
> обидно. Нужно отомстить обидчику, и ничего не остается как спрыгнуть к игроку в
> яму.
угу. а игрок может выбраться... а "изолированная ямка" это 1x1, 2x1, 2x2, 30x30, 40x40?

хотя игру уже интересно посмотреть :)

MrShoorУчастникwww18 ноя. 20177:07#59
skalogryz
Я начал было адаптировать код, потом совершенно не было времени, а теперь время есть но энтузиазм угас... короче я сдаюсь. :)

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

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

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