Поиск оптимальной стратегии для итерации по блокам чанка

Ethrian · 5 Июн 2023

Доброго времени суток, господа. Столкнулся я со следующей задачей: применение довольно сложного предиката к чанку, проверяющего его на наличие N количества блоков, подходящих под определённые условия. Например, нужно узнать, есть ли в чанке 40 блоков пашни под открытым небом, 4 сундука и верстак. Важное уточнение: нужно, проверять только на минимальное кол-во выбранных блоков, а не эквивалентность. Также мы не проверяем тайл энтити блоков.
Первое, что приходит на ум, это использовать тройной for, но потенциально это 16 * 16 * 256 = 65536 циклов. Игнорируя блоки воздуха, и предполагая, что в среднем такая проверка найдёт все нужные блоки за 75% шагов, мы получаем около 24500 циклов в случае успешной проверки. Благо, такая проверка применяется не очень часто - при взаимодействии с блоком, (после чего результат кэшируется), но может затрагивать несколько чанков за раз, максимум - 81 чанк за раз.

Вопрос предельно простой: как можно это оптимизировать?

will0376 · 5 Июн 2023

Если есть возможность - можно поиск в поток вынести, кешируя результат...

Ethrian · 6 Июн 2023

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

https://medium.com/levi-niners-crafts/java-performance-improvement-java-8-streams-vs-loops-and-lists-vs-arrays-e824136832d6

Так что это точно не вариант.

mts2200 · 6 Июн 2023

Ethrian написал(а):
циклов

итераций*

Ethrian написал(а):
Для таких задач обычный цикл предпочтительнее потока

Многопоточность, а не StreamAPI. А ещё лучше - сопрограммы, они же корутины, для read операций их можно использовать спокойно.

Ethrian · 6 Июн 2023

mts2200 написал(а):
итераций*

mts2200 написал(а):
Многопоточность, а не StreamAPI

Не сразу понял о чём речь. Стоит попробовать.

mts2200 написал(а):
А ещё лучше - сопрограммы, они же корутины

Джава ведь не поддерживает корутины... или же...?

ZZZubec · 6 Июн 2023

Ethrian написал(а):
не поддерживает корутины

ну... будем считать что нет, вообще поддерживает, есть у ней async.wait но это лишь абстракция над Thread и всяких Future<Void>

Для ваших задач подойдет "автомат" (автоматное программирование). Когда заходят в вызов мы делаем только 1 шаг, инкрементируем счётчик и выходим. И так до тех пор пока нам это необходимо. Таким образом мы будем находиться в основном потоке и при этом не особо влиять на происходящее вокруг.

Был такой метод раньше, getHeight или что то такое, который возвращал последний блок сверху. Это могло быть либо земля с травой, либо снег на дерево. Но это самый ближайший блок к земле и самый ближайший блок к небу (солнцу).
Скорее всего он лежит где то в world или в chunk.
Оптимизировать можно довольно просто, как только мы нашли блок который не содержит воздух выше и не является деревом или травой (если травой, то мы нашли самый ближайший к земле).

public int getHeight(Heightmap.Type p_201576_1_, int p_201576_2_, int p_201576_3_) {...}
public Collection<Entry<Heightmap.Type, Heightmap>> getHeightmaps() {...}

Ethrian · 6 Июн 2023

ZZZubec написал(а):
Для ваших задач подойдет "автомат"

Слабо знаком с этой парадигмой. Я правильно понимаю, что это решение, грубо говоря, предполагает построение chain of responsibility, состоящую из нужных для конкретной проверки предикатов в качестве обработчиков, в конце которой стоят инкременты?

ZZZubec · 6 Июн 2023

Я теорию плохо знаю, мне ближе практика.

Ethrian написал(а):
chain of responsibility

впервые слышу это название. Автоматное программирование скорее всего произошло именно от Автомата (для меня лично первый автомат это который наливал газировку ). Суть которого заключается в том чтобы налить газированную воду в стакан.
Монета служит для активации проверки подпрограмм - автоматов.
Автоматы ничего не знают о существовании других систем. Они работают исключительно со своей задачей. На вход подаются данные, на выходе мы должны получить результат (результатом может быть исключение, ошибка).
Таким образом автомат газировки содержит следующие автоматы (ещё раз напомню, которые сами по себе независимы):
Автомат проверки оплаты - да/нет
Автомат для проверки есть ли газ в балоне - да/нет
Автомат для проверки воды - да/нет
и т.д.
Таким образом, при отсутствии например углекислого газа, автомат может ещё наливать воду. О чём он обычно подсвечивал над кнопками. То есть можно налить 2а варианта воды.

По своей сути автоматы напоминают сложную систему FSM, в большей её степени. Но это может чуть запутать. Поэтому упоминаю только сейчас. Они отличаются, хотя назначение одно и тоже. FSM не так гибок, то есть у него в условии стоит что он всегда находится ТОЛЬКО в одном из состояний. Что нам сложнее воспринимать.

Теперь вернёмся "к нашим баранам", я подразумевал что есть некий шаг (проверка 1 из блоков в списке или за 1 раз нескольких), а затем завершение процесса

class BlahBlah {
int step = 0;
bool isFinish = false;

function bool Step() {
//проверка
try
{
//вычисления
BlockPos pos = ArrayList<BlockPos>[step]();
if(pos...)
} catch {
throw exception || return false || isFinish = true;
}
if step != lastStep -> step++;
else
  isFinish = true;
return true;
}

if(

}

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

Ethrian · 6 Июн 2023

Теперь понял, большое спасибо за подробное объяснение.

Ethrian · 6 Июн 2023

Ethrian написал(а):
chain of responsibility

https://www.geeksforgeeks.org/chain-responsibility-design-pattern/

Вдруг кому пригодится

Поиск оптимальной стратегии для итерации по блокам чанка

Токсичная личность