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

Оптимизация алгоритма определения связности в структуре

Поделиться
ILПостоялецwww11 ноя. 201723:38#0
Всем привет!

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

Блоки могут устанавливаться (или удаляться) только поочередено.

В чем задача?

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

Изображение


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

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

ps: уточню, блоки являются "соседями", только если стоят вполтную к грани, диагональные направления не учитываются.

ILПостоялецwww11 ноя. 201723:42#1
Я думал над идеей графом, но в случае сложных структур с большим кол-вом блоков, там его трудно применить.
ryzedПостоялецwww12 ноя. 20170:39#2
Решал подобную задачу в 2д.
Разбиение на тайлы сработало.
http://www.gamedev.ru/code/forum/?id=177932

Можно еще про вариант с иерархией подумать, но мне хватило.

foxesПостоялецwww12 ноя. 20170:52#3
IL
Была такая задача на мировом чемпионате по программированию, я ее решал через рекурсию. Как именно не помню, но по времени подходила, а с другими не сравнивал. Пока пишу вспоминаю, загвоздка там была естественно в глубине стека, которая решалась развертыванием его в отдельный массив. Возможно еще была пара хитростей...

Суть задачи с чемпионата была такой:
Посчитать количество структур и их размеры в количестве блоков и вывести список из 10 наиболее больших. Размер воксельного поля был до 100x100x100.

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

Я это решение уже потом оформил для курсовой в 2003 году. (еще за долго до всяких minecraft, хехе)

+ Показать
+ Показать

Вот такая програмулина Nalog

Размер города задает размер воксельного поля сразу по всем осям. Остальные три - это положение камеры, саму камеру можно вертеть мышкой.
RND - чтобы заполнить поле случайными кубиками, чтобы их было больше - просто нажать еще несколько раз.
Сразу после добавления кубиков происходить обход всего поля и снизу справа выводиться результат.

Правка: 12 ноя. 2017 2:03

MrShoorУчастникwww12 ноя. 20175:32#4
Тут нужен обычный поиск в глубину или в ширину. Пройденные куски помечать. Как только обход закончился - значит нашли целый независимый блок. Переходим к другим блокам.
SuslikМодераторwww12 ноя. 20179:14#5
есть стандартный алгоритм для решения этой задачи, называется disjoint set union. если в двух словах, то объекты(ячейки) образуют группы. каждый объект ссылается на единственный другой объект, принадлежащей той же группе, что и он сам. в каждой группе есть единственный представитель — объект, который ссылается сам на себя. чтобы узнать, какой группе принадлежит объект, пробегаешься от него вверх по иерархии, пока не найдёшь представителя его группы. для того, чтобы добавить очередной воксель в систему, просто переприсваиваешь представителю группы каждого из его соседей его самого, то есть теперь он — представитель всех прилежащих к нему групп, тем самым все прилежащие группы объединяются в одну.

в принципе, уже этого достаточно, чтобы за линейное время находить, какой группе принадлежит каждый воксель, но основная фишка алгоритма состоит в том, что при каждой итерации поиска можно для всех объектов иерархии переприсваивать кратчайшую ссылку на представителя группы, чтобы следующие запросы выполнялись не за линейное время, а за O(1). оценка результирующей сложности алгоритма — достаточно хитрая, но там получается что-то вроде итерированного логарифма, то есть, считай, почти константа. плюс содержательная часть алгоритма реализуется буквально в три строчки, проще не бывает и на произвольных графах работает эффективнее обходов, потому что:
- не требует хранения всего графа, а лишь O(n) памяти — это единственная ссылка на представителя для каждого элемента
- стек будет в среднем глубиной в итерированный логарифм количества элементов. считай, опять же, константа.
- алгоритм очень эффективно работает при инкрементальном добавлении новых связей, то есть при добавлении новых вокселей в твоём случае: для обходов в ширину/глубину пришлось бы их заново запускать, а эта штука работает за O(1).

во, я у себя даже код нашёл(это весь алгоритм). прошу прощения за каламбур со словом "set" — здесь это существительное, а не глагол:

struct DisjointSetUnion
{
  DisjointSetUnion(size_t elementsCount)
  {
    setIndices.resize(elementsCount);
    for(size_t setIndex = 0; setIndex < elementsCount; setIndex++)
      setIndices[setIndex] = setIndex;
  }

  size_t GetSetIndex(size_t elementIndex)
  {
    if(setIndices[elementIndex] == elementIndex) return elementIndex;
    return setIndices[elementIndex] = GetSetIndex(setIndices[elementIndex]);
  }

  void MergeElements(size_t elementIndex0, size_t elementIndex1)
  {
    setIndices[GetSetIndex(elementIndex0)] = setIndices[GetSetIndex(elementIndex1)];
  }

  std::vector<size_t> setIndices;
};
я уже много лет использую этот алгоритм для поиска мешей в polygon soup'ах вроде выхлопа marching cubes, для построения независимых островов в физике и тому подобного.

Правка: 12 ноя. 2017 9:43

FordPerfectПостоялецwww12 ноя. 201712:03#6
Suslik
Здесь же удаления нужны. С ними disjoint set union... интереснее.

Ключевое слово, вроде, Dinamic Connectivity problem:
http://codeforces.com/blog/entry/15296?locale=ru

FordPerfectПостоялецwww12 ноя. 201712:10#7
Для одинарного удаления точки раздела:
http://e-maxx.ru/algo/cutpoints

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

MrShoorУчастникwww13 ноя. 201719:58#8
IL
Соптимизироать можно так. После удаления блоков нужно взять все соседние блоки (включая диагональные, представь кубик рубика). Их максимум будет 26. Заспавнить где-то отдельно эту локальную группу. Если после этого у тебя получился один кластер, то все отлично. Блок можно безопасно удалять, и он не разобьет исходный кластер.

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

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