[Обсудим] Как правильно проверить наличие чего либо в регионе?

Как правильно проверить наличие чего либо в регионе?
У меня есть фукция, которая проверят на пересечение региона:

Код:

    public boolean isVhodit(Location loc)
    {
        if (loc.getY() >= min.getBlockY()
                && loc.getY() <= max.getBlockY()
                && loc.getX() >= min.getBlockX()
                && loc.getX() <= max.getBlockX()
                && loc.getZ() >= min.getBlockZ()
                && loc.getZ() <= max.getBlockZ()
                )
        {
            return true;
        }
        return false;
    }

Но допустим у меня 1000 регионов. При каждом движении игрока получается мне нужно сделать проверку на ВСЕ регионы?! Нет, так не пойдет.

У меня еще была идея связать все регионы с чанками массивом HashMap <Chunk, ArrayList<Region>> chunks. В этом случае, проверка будет выглядеть так:

Код:

    public void onMovePlayer(PlayerMoveEvent event)
    {
        Player p = event.getPlayer();
        Chunk c = p.getLocation().getChunk();
        if (chunks.containsKey(c))
        {
            for (Region r : chunks.get(c))
            {
                if (r.isVhodit(p.getLocation))
                {
                    //Код, если игрок пересек регион
                }
            }
        }
    }

Но это все равно будет нагружать сервер, например, в этом месте:

Код:

(chunks.containsKey(c))

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

Какой у вас способ упростить задачу?

 

Только так и получится.

 

Думаешь? Я подожду еще ответов.

 

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

 

Хм, а вот это идея..

 

Где-то внутри метадата блока - это просто HashMap<Block, Metadata>, никакой разницы от Chunk<Block, Metadata>

 

Ты уверен? Было бы у тебя 100000 регионов, тогда бы еще может и была какая нагрузка.

 

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

Если было бы 100 000 регионов на проверку от MovePlayerEvent при 20 игроках, то нагрузки бы не было, как и сервера. Где это видано, чтобы не реже 20 раз в секунду ява обрабатывала 2 000 000 обращений к разным областям памяти? К тому же если есть возможность оптимизировать и не горят сроки, то почему бы и нет? Или всем прикажете говнокодить и использовать первые подвернувшиеся конструкции под руку?

 

Во всех ядрах это реализация так или иначе сделана. На самом деле блоки в конкретном чанке - просто массив интов которые и содержат нужную инфу, а также хэшмапа с тайлэнтитями. Можно было бы конечно хранить массив каких-нибудь структурированных данных.
Но в конце концов сам чанк тоже ведь надо получить, а это опять же та же хэшмапа. Так что хранить данные в метаданных блока неэффективно в любом случае. Поэтому ничего лучше HashMap<Chunk, чёта> не придумано.

 

Можно как-то закодировать информацию в блоке, ибо адрес к его объекту уже хранится в PlayerMoveEvent, и его не придется доставать из массива, если я все правильно понял, но это конечно как-то неправильно.

Кто нибудь знает, как WorldGuard справляется с этой задачей? При разрушении блока нужно чекнуть все регионы как-никак. Помню у меня был сувивал сервер, там было порядка 3к регионов

 

Ну можешь сделать HashMap<Block, что-то>, но тогда памяти надо много, зато список регионов бысро вытаскивать будешь. А в самом блоке ты ничего не закодируешь.
WorldGuard кэширует почанково.

 

Есть множество способов решить/оптимизировать эту задачу.
Во-первых, заблуждение, что при 100 000 записей в HashMap-е её contains() будет пробегать их все.
Насколько я помню, WorldGuard предоставляет свои собственные события OnRegionEnter и OnRegionLeave (названия наобум, следи за смыслом). Если в теме под словом "регион" подразумеваются приваты от WG — пожалуйста, используйте их.
Кроме того, я уверен, что нет необходимости лично тебе делать проверку локации со всеми регионами -- достаточно будет только каких-то особых, на которые "подписано действие".

Также считаю полезным почитать про квадратичные деревья, которые могут использоваться для разбиения плоскости на области, содержащие ваши регионы. Для нахождения потенциально пересекающих точку регионов достаточно спуститься от корневого элемента до листа, которому принадлежит точка.
Возвращаясь к WG, все могут взять и поискать, как он определяет список регионов по заданному вектору: https://github.com/sk89q/WorldGuard...om/sk89q/worldguard/protection/managers/index[DOUBLEPOST=1436707762,1436706072][/DOUBLEPOST]Как оказалось, в WorldGuard используются встроенный ConcurrentHashMap и сторонняя реализация приоритетных R-деревьев.

 

sk89q не перестает удивлять.

https://github.com/sk89q/WorldGuard...tection/managers/RegionManager.java#L318-L324
Надеюсь, что этот метод работает достаточно быстро.

 

Работает, всегда им пользуюсь.

 

В итоге работа сваливается вот сюда:
https://github.com/sk89q/WorldGuard...on/managers/index/PriorityRTreeIndex.java#L70
(используется библиотека http://www.khelekore.org/prtree/).

В общем, не делайте костыли, используйте предлагаемое из коробки.