Вопрос Оптимизация кода поиска локации. Идеи?

CodeLomer · 4 Дек 2023

Есть код на поиск локации но дело в том что он чаще всего занимает время более секунды а я видел где это занимает максимум 366 миллисекунд

Java:

 public Location getRandomSolidAllowedLocation(Random random, int xMin, int xMax, int zMin, int zMax, World world, int centerX, int centerZ, int yMax, int yMin, Collection<Material> blockList, int maxTry){
        if(world == null || random == null || maxTry < 1) return null;
        long startTime = System.nanoTime();

        for(int tryFind = 0; tryFind < maxTry; tryFind++){
            Location location = generalRtpComponent.getRandomLocation(xMin,xMax,zMin,zMax,random,centerX,centerZ,world);

            Chunk chunk = location.getChunk();
            if(!chunk.isLoaded()) chunk.load();

            if(!world.getWorldBorder().isInside(location)) continue;
            location = generalRtpComponent.getSolidLocation(location,yMax,yMin);
            if(location == null) continue;
            if(blockList.contains(location.getBlock().getType())) continue;
            location.setY(location.getBlockY()+1);

            long endTime = System.nanoTime();
            long duration = (endTime - startTime) / 1_000_000;
            System.out.println("Время выполнения метода: " + duration + " мс");

            return location;
        }
        return null;
    }



public Location getSolidLocation(Location location, int yMax, int yMin){
        for(int y = yMax;y > yMin;y--){
            location.setY(y);
            Material material = location.getBlock().getType();
            if(material.isAir()) continue;
            return location;
        }
        return null;
    }
    public Location getRandomLocation(int xMin, int xMax, int zMin, int zMax, Random random, int centerX, int centerZ, World world){
        int x = SimpleUtil.rndInt(xMin,xMax,random);
        int z = SimpleUtil.rndInt(zMin,zMax,random);
        int xSign = (random.nextBoolean() ? -1 : 1);
        int zSign = (random.nextBoolean() ? -1 : 1);
        x = centerX + (x * xSign);
        z = centerZ + (z * zSign);
        return new Location(world,x,0,z);
    }

Destroy · 5 Дек 2023

Galtap написал(а):

Есть код на поиск локации но дело в том что он чаще всего занимает время более секунды а я видел где это занимает максимум 366 миллисекунд

Java:

 public Location getRandomSolidAllowedLocation(Random random, int xMin, int xMax, int zMin, int zMax, World world, int centerX, int centerZ, int yMax, int yMin, Collection<Material> blockList, int maxTry){
        if(world == null || random == null || maxTry < 1) return null;
        long startTime = System.nanoTime();

        for(int tryFind = 0; tryFind < maxTry; tryFind++){
            Location location = generalRtpComponent.getRandomLocation(xMin,xMax,zMin,zMax,random,centerX,centerZ,world);

            Chunk chunk = location.getChunk();
            if(!chunk.isLoaded()) chunk.load();

            if(!world.getWorldBorder().isInside(location)) continue;
            location = generalRtpComponent.getSolidLocation(location,yMax,yMin);
            if(location == null) continue;
            if(blockList.contains(location.getBlock().getType())) continue;
            location.setY(location.getBlockY()+1);

            long endTime = System.nanoTime();
            long duration = (endTime - startTime) / 1_000_000;
            System.out.println("Время выполнения метода: " + duration + " мс");

            return location;
        }
        return null;
    }



public Location getSolidLocation(Location location, int yMax, int yMin){
        for(int y = yMax;y > yMin;y--){
            location.setY(y);
            Material material = location.getBlock().getType();
            if(material.isAir()) continue;
            return location;
        }
        return null;
    }
    public Location getRandomLocation(int xMin, int xMax, int zMin, int zMax, Random random, int centerX, int centerZ, World world){
        int x = SimpleUtil.rndInt(xMin,xMax,random);
        int z = SimpleUtil.rndInt(zMin,zMax,random);
        int xSign = (random.nextBoolean() ? -1 : 1);
        int zSign = (random.nextBoolean() ? -1 : 1);
        x = centerX + (x * xSign);
        z = centerZ + (z * zSign);
        return new Location(world,x,0,z);
    }

вместо нано миллис попробуй использовать currentTimeMillis() чтобы не выполнять вычисления в цикле. (Не нужно ничего делить)

Объединено 5 Дек 2023

Galtap написал(а):

Есть код на поиск локации но дело в том что он чаще всего занимает время более секунды а я видел где это занимает максимум 366 миллисекунд

Java:

 public Location getRandomSolidAllowedLocation(Random random, int xMin, int xMax, int zMin, int zMax, World world, int centerX, int centerZ, int yMax, int yMin, Collection<Material> blockList, int maxTry){
        if(world == null || random == null || maxTry < 1) return null;
        long startTime = System.nanoTime();

        for(int tryFind = 0; tryFind < maxTry; tryFind++){
            Location location = generalRtpComponent.getRandomLocation(xMin,xMax,zMin,zMax,random,centerX,centerZ,world);

            Chunk chunk = location.getChunk();
            if(!chunk.isLoaded()) chunk.load();

            if(!world.getWorldBorder().isInside(location)) continue;
            location = generalRtpComponent.getSolidLocation(location,yMax,yMin);
            if(location == null) continue;
            if(blockList.contains(location.getBlock().getType())) continue;
            location.setY(location.getBlockY()+1);

            long endTime = System.nanoTime();
            long duration = (endTime - startTime) / 1_000_000;
            System.out.println("Время выполнения метода: " + duration + " мс");

            return location;
        }
        return null;
    }



public Location getSolidLocation(Location location, int yMax, int yMin){
        for(int y = yMax;y > yMin;y--){
            location.setY(y);
            Material material = location.getBlock().getType();
            if(material.isAir()) continue;
            return location;
        }
        return null;
    }
    public Location getRandomLocation(int xMin, int xMax, int zMin, int zMax, Random random, int centerX, int centerZ, World world){
        int x = SimpleUtil.rndInt(xMin,xMax,random);
        int z = SimpleUtil.rndInt(zMin,zMax,random);
        int xSign = (random.nextBoolean() ? -1 : 1);
        int zSign = (random.nextBoolean() ? -1 : 1);
        x = centerX + (x * xSign);
        z = centerZ + (z * zSign);
        return new Location(world,x,0,z);
    }

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

CodeLomer · 5 Дек 2023

результат получается сразу после первого поиска смысла в отсутствии деления нет

CodeLomer · 5 Дек 2023

лан фиг с ним а если эта хрень в цикле че делать (занимает до 4 сек если не одна нормальная локация не нашлась в процессе 24 итераций)

Объединено 5 Дек 2023

на это время сервер зависает
на 4 сек из за однопоточности майна

Объединено 5 Дек 2023

или этим все rtp плагины страдают?

HomaPlus · 5 Дек 2023

Galtap написал(а):
или этим все rtp плагины страдают?

Учи java
1) Неизвестно какую коллекцию толкаешь в аргументы. Асимптотика сложности для методов у каждой своя
2) Учи математику и программировать в целом, getRandomLocation можно записать в 2 строки
3) Учи алгоритмы, getSolidLocation можно переписать, сократив количество проверок в 2-10 раз

И главный гвоздь низкой производительности - это загрузка (так же возможно бонусом каскадная генерация) чанков.
Можно ускорить метод до 3-20 мс, если переделать по нормальному то, на что я указал выше, а так же проиндексировать сгенерированные чанки, и телепортировать только в них

UPD держи пример на обучение

Java:

public Location getSolidLocation(Location location, int yMax, int yMin){
    //todo переписать это через экспоненциальный поиск
    //todo тк итерация идет в пределах 1-го чанка, запрашивай его 1 раз, а не каждую проверку
    //todo возвращать location - сомнительная идея, с моей точки зрения лучше будет
    //     переименовать метод на isSuccessLocation() и возвращать true/false
    for(;yMax > yMin; location.setY(--yMax))
        if(!location.getBlock().getType().isAir()) return location;
    return null;
}

CodeLomer · 5 Дек 2023

это звучит отлично но есть 1 вопрос как не застопать сервер в процессе поиска локации (к примеру у betterRtp ищет локацию порарельно игре хотя bukkit однопоточный) ведь не смотря на оптимизированный поиск может случится что найти нужную локацию не возможно

HomaPlus · 5 Дек 2023

Galtap написал(а):
ведь не смотря на оптимизированный поиск может случится что найти нужную локацию не возможно

Я же сказал, делай индекс по сгенерированным чанкам (и подходящими для телепортации), при весе в менее 50кб, можно гарантировано найти нужную точку, за практически O(1)

BlackBaroness · 5 Дек 2023

Лично я при написании ртп делал N попыток поиска за тик, пока не найдется значение - так нагрузка фиксированная. Результат доставлялся через CompletableFuture

CodeLomer · 5 Дек 2023

ладно задам вопрос по-другому. Как не стопать сервер при попытке поиска если ГАРАНТИРОВАНО это будет долго не зависимо от того быстрый алгоритм поиска или нет

Объединено 5 Дек 2023

Ситуации могут быть разными

Объединено 5 Дек 2023

Хоть даже привести пример можно поиск баз на холике там он ищет некоторое время а потом только телепортирует и при этом во время поиска не стопает сервер хотя bukkit однопоточный

Объединено 5 Дек 2023

когда я тестил betterRtp он тоже искал и не стопал сервер хотя секунд 4 прошло и я мог ломать в этот момент и подбирать предмет

CodeLomer · 5 Дек 2023

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

Объединено 5 Дек 2023

поиск регионов где есть только 2 региона там тоже нужно потратить время

Объединено 5 Дек 2023

да даже вопрос касается не только поиска локации а вообще процесса работы больших объёмов связаных с майкрафтов где асинхронности не может быть

Объединено 5 Дек 2023

как не как надо учитывать все возможное что пользователь может сделать если даже думаешь что есть гарантия

CodeLomer · 5 Дек 2023

BlackBaroness написал(а):
Лично я при написании ртп делал N попыток поиска за тик, пока не найдется значение - так нагрузка фиксированная. Результат доставлялся через CompletableFuture

вот только по идее это тоже самое как поиск за 1 тик только без лагов и с более большим потраченным временем и по сути ты ничего в процессе не сможешь сделать (добывать блоки и тд) Смогут ли игроки что либо делать пока будет происходить поиск ? Например 4 секунды нужно на задачу. За это время игроки не смогут взаимодействовать по идее с миром

HomaPlus · 5 Дек 2023

Galtap написал(а):
если bukkit однопоточный

Вот почему, я и говорю что ведро - то еще ведро. С краником, другими приворотами, или без. Используй Фабрик/Forge

Вам необходимо зарегистрироваться для просмотра изображений-вложений

Galtap написал(а):
не стопая сервер искать локации

Это не возможно на ведре чел. Генерация чанков должна быть строго синхронизирована (шумы, и кеш биомов). Если чанк УЖЕ сгенерирован - индексы.
Тебе человек правильно ответил - используй отложенный поиск

Ты можешь без проблем в любом потоке читать любые данные сервера (без использования блокирующих итераций) - но добавлять в обработку можно только в основном потоке.

CodeLomer · 5 Дек 2023

Ладно а как насчет синхронности в асинхронне? В синхрон добавить прогрузку чанков а в асинхрон проверки

HomaPlus · 5 Дек 2023

Galtap написал(а):
Ладно а как насчет синхронности в асинхронне? В синхрон добавить прогрузку чанков а в асинхрон проверки

Не забывай про накладные расходы на планировщик задач и управление потоками. Поиск по правильному индексу будет в разы быстрее чем это

CodeLomer · 5 Дек 2023

HomaPlus написал(а):
Вот почему, я и говорю что ведро - то еще ведро. С краником, другими приворотами, или без. Используй Фабрик/Forge

Вам необходимо зарегистрироваться для просмотра изображений-вложений

Это не возможно на ведре чел. Генерация чанков должна быть строго синхронизирована (шумы, и кеш биомов). Если чанк УЖЕ сгенерирован - индексы.
Тебе человек правильно ответил - используй отложенный поиск

Ты можешь без проблем в любом потоке читать любые данные сервера (без использования блокирующих итераций) - но добавлять в обработку можно только в основном потоке.

но как то betterRtp может делать поиск параллельно процессу игры

HomaPlus · 5 Дек 2023

Galtap написал(а):
но как то betterRtp может делать поиск параллельно процессу

посмотри исходники, делов то. Не так уж и параллельно

NullPointer · 5 Дек 2023

Можешь сделать примерно так:

Java:

public class RTPTask extends BukkitRunnable {
    private int attempts;
    private final Consumer<Location> callback;

    public RTPTask(int attempts, Consumer<Location> callback) {
        this.attempts = attempts;
        this.callback = callback;
    }

    @Override
    public void run() {
        if (attempts == 0) {
            cancel();
            return;
        }

        int x = ThreadLocalRandom.current().nextInt(-9500, 9500);
        int z = ThreadLocalRandom.current().nextInt(-9500, 9500);
        Location location = Bukkit.getWorld("world").getHighestBlockAt(x, z).getLocation();
        if (location.clone().subtract(0, 1, 0).getBlock().getType() != Material.STATIONARY_WATER) {
            callback.accept(location.add(0.5, 0, 0.5));
            attempts = 0;
            cancel();
            return;
        }
        attempts -= 1;
    }
}

Java:

new RTPTask(10, location -> {
    player.sendMessage("Локация найдена");
    player.teleport(location);
}).runTaskTimer(this, 0L, 10L);

BlackBaroness · 6 Дек 2023

Galtap написал(а):
вот только по идее это тоже самое как поиск за 1 тик только без лагов и с более большим потраченным временем и по сути ты ничего в процессе не сможешь сделать (добывать блоки и тд) Смогут ли игроки что либо делать пока будет происходить поиск ? Например 4 секунды нужно на задачу. За это время игроки не смогут взаимодействовать по идее с миром

Я ничего не блокировал, пофиг вообще. оно вряд ли будет целых 4 секунды, условно 5 попыток за ник это 100 попыток в секунду, что очень много

flaweoff написал(а):
private final Consumer<Location> callback;

Тут лучше использовать CompletableFuture

naker1337 · 11 Дек 2023

1. тут я избежал загрузки чанков (if (!chunk.isLoaded()) continue

2. упрощенный поиск снизу вверх
3. удалил не нужные вызовы

Java:

public Location getRandomSolidAllowedLocation(Random random, int xMin, int xMax, int zMin, int zMax, World world, int centerX, int centerZ, int yMax, int yMin, Collection<Material> blockList, int maxTry) {
    if(world == null || random == null || maxTry < 1) return null;
    long startTime = System.nanoTime();

    for (int tryFind = 0; tryFind < maxTry; tryFind++) {
        Location location = getRandomLocation(xMin, xMax, zMin, zMax, random, centerX, centerZ, world);

        Chunk chunk = location.getChunk();
        if (!chunk.isLoaded()) continue;

        if (!world.getWorldBorder().isInside(location)) continue;
        Location solidLocation = getSolidLocation(location, yMax, yMin);
        if (solidLocation == null || blockList.contains(solidLocation.getBlock().getType())) continue;

        solidLocation.setY(solidLocation.getBlockY() + 1);

        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1_000_000;
        System.out.println("time: " + duration + " ms");

        return solidLocation;
    }
    return null;
}

public Location getSolidLocation(Location location, int yMax, int yMin) {
    while (yMax > yMin) {
        location.setY(yMax);
        Material material = location.getBlock().getType();
        if (!material.isAir()) {
            return location;
        }
        yMax--;
    }
    return null;
}

public Location getRandomLocation(int xMin, int xMax, int zMin, int zMax, Random random, int centerX, int centerZ, World world) {
    int x = SimpleUtil.rndInt(xMin, xMax, random);
    int z = SimpleUtil.rndInt(zMin, zMax, random);
    int xSign = (random.nextBoolean() ? -1 : 1);
    int zSign = (random.nextBoolean() ? -1 : 1);
    x = centerX + (x * xSign);
    z = centerZ + (z * zSign);
    return new Location(world, x, 0, z);
}

Вопрос Оптимизация кода поиска локации. Идеи?

Мы ценим вашу конфиденциальность