Поиск соседей и соседей соседей блока...

1,921
107
378
На днях написал алгоритм поиска соседа и соседа соседа блока. Для наглядности это будет блок обсидиан. Этот метод я реализовал в ивенте клика по блоку. Наверное кому-нибудь пригодится.
Java:
if (block == Blocks.OBSIDIAN) { // Если наш блок изначально обсидиан
  HashSet<BlockPos> poss = new HashSet(); // Множество кол-ва наших блоков
  HashSet<BlockPos> unposs = new HashSet(); // Множество кол-ва непроверенных блоков

  poss.add(pos); // Добавляем наш блок в это множество
  for (int a = 0; a < 6; a++) // В этом цикле происходи подбор соседей изначального блока
    unposs.add(pos.add(EnumFacing.VALUES[a].getDirectionVec()));

  while (unposs.size() > 0) { // В этом цикле происходит проверка и создание новых непроверенных блоков
    HashSet<BlockPos> newSet = new HashSet(); // Создание нового множества, на замену unposs
    for (BlockPos upp : unposs) {
      if (event.getWorld().getBlockState(upp).getBlock() == Blocks.OBSIDIAN) {
        poss.add(upp);
        for (int a = 0; a < 6; a++) {
          BlockPos pp = upp.add(EnumFacing.VALUES[a].getDirectionVec()); // Позиция соседа
          if (!poss.contains(pp)) // Проверка, что сосед не обсидиан, который мы уже добавляли
            newSet.add(pp); // Добавление нового соседа на проверку
        }
      }  
      newSet.remove(upp); // Проверили - удалили
    }
    unposs = newSet; // Замена множества с "правками"
  }

  player.sendMessage(new TextComponentString(poss.size().toString()));
}
Алгоритм способен проверить блоки в кол-ве 2600 штук(Не в update) без серьёзных провисаний.
Наверное, дополнив этот код, можно сделать систему передачи энергии.
 
Последнее редактирование модератором:
Не очень.
Во-первых, Set для блоков, которые нужно проверить - дорого. Лучше ArrayList.
Во-вторых, создание новых коллекций - очень плохо.
В-третьих, дублирование кода. Добавь первую вершину в список непроверенных и убери первый цикл.

Выглядит так, будто ты сам изобрел этот алгоритм. Посмотри нормальную реализацию обхода дерева в ширину.
 
Dahaka написал(а):
Выглядит так, будто ты сам изобрел этот алгоритм.
Так и есть


Dahaka написал(а):
Во-первых, Set для блоков, которые нужно проверить - дорого. Лучше ArrayList.
Можно просто заменить HashMap на ArrayList и код не выдаст ошибок


Dahaka написал(а):
В-третьих, дублирование кода. Добавь первую вершину в список непроверенных и убери первый цикл.
Это более проще, чем добавлять тоже самое в цикл.
 
украл
 
WhiteWarrior написал(а):
Alex написал(а):
Maxik001 написал(а):

Так без пруфоф же это называется клевета! (Это законо-наказуемо!)

Он про себя говорил -_-. Наверное.

Пора бы уже на этом форуме свой правила этикета создать!
 
Шикарно как раз нужно было кучу блоков за пару тиков пересчитать.
 
talosdx написал(а):
Шикарно как раз нужно было кучу блоков за пару тиков пересчитать.

Сомневаюсь, что этот алгоритм сможет пересчитать 30k блоков за тик...
 
Dahaka же все по частям разобрал. Сделайте поиск в ширину по графу. Что это за поиск? Он обходит узлы у корня, затем в роли корня становится каждый из узлов. То, что нужно. И из коллекций, наверно, потребуется массив да Deque(очередь, в общем, нужна).
 
У меня примерно таким макаром вода у краёв обрыва убирается...
Ну, если натыкаюсь на большие водоёмы, зависает, конечно... (не в ущерб самой игре) Но кто не без греха? )))
Сумеречный лес при генерации тоже надолго повисает.
 
170k блоков пересчитывает без малейший лагов(y)
2017-11-26_12.37.49.png
 
4x4x4 - у меня уже лагало...
(При чем с немного переделанной системой)
 
Последнее редактирование:
Покажи мне ещё дамп памяти. Хочу посмотреть, сколько там объектов насоздавалось
 
Тысяч? Не поверю. У тебя, по идее, на каждый блок приходится несколько объектов. По-моему, реализация с одной кучей и списком для отметки прохода по узлу будет куда выгоднее.
 
Я еще заметил, что пересчет длится гораздо дольше, если в цикле while выводить сообщения в консоль...
 
Назад
Сверху