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

Версия Minecraft
1.16.X
C

CodeLomer

Пользователь
Сообщения
25
Есть код на поиск локации но дело в том что он чаще всего занимает время более секунды а я видел где это занимает максимум 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);
    }
 
Сортировка по дате Сортировка по голосам
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() чтобы не выполнять вычисления в цикле. (Не нужно ничего делить)
Авто объединение сообщений:

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);
    }
Нажмите для раскрытия...
еще существует метод для получения максимального блока по высоте, попробуй его использовать в своем коде
 
Позитивный голос 0 Негативный голос
лан фиг с ним а если эта хрень в цикле че делать (занимает до 4 сек если не одна нормальная локация не нашлась в процессе 24 итераций)
Авто объединение сообщений:

на это время сервер зависает
на 4 сек из за однопоточности майна
Авто объединение сообщений:

или этим все rtp плагины страдают?
 
Позитивный голос 0 Негативный голос
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;
}
 
Последнее редактирование:
Позитивный голос 0 Негативный голос
это звучит отлично но есть 1 вопрос как не застопать сервер в процессе поиска локации (к примеру у betterRtp ищет локацию порарельно игре хотя bukkit однопоточный) ведь не смотря на оптимизированный поиск может случится что найти нужную локацию не возможно
 
Последнее редактирование:
Позитивный голос 0 Негативный голос
Galtap написал(а):
ведь не смотря на оптимизированный поиск может случится что найти нужную локацию не возможно
Нажмите для раскрытия...
Я же сказал, делай индекс по сгенерированным чанкам (и подходящими для телепортации), при весе в менее 50кб, можно гарантировано найти нужную точку, за практически O(1)
 
Позитивный голос 0 Негативный голос
Лично я при написании ртп делал N попыток поиска за тик, пока не найдется значение - так нагрузка фиксированная. Результат доставлялся через CompletableFuture
 
Позитивный голос 0 Негативный голос
ладно задам вопрос по-другому. Как не стопать сервер при попытке поиска если ГАРАНТИРОВАНО это будет долго не зависимо от того быстрый алгоритм поиска или нет
Авто объединение сообщений:

Ситуации могут быть разными
Авто объединение сообщений:

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

когда я тестил betterRtp он тоже искал и не стопал сервер хотя секунд 4 прошло и я мог ломать в этот момент и подбирать предмет
 
Позитивный голос 0 Негативный голос
могут быть моменты где ради гарантии нужно потратить время а это невозможно сделать если bukkit однопоточный вот я и хотел узнать как можно не стопая сервер искать локации
Авто объединение сообщений:

поиск регионов где есть только 2 региона там тоже нужно потратить время
Авто объединение сообщений:

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

как не как надо учитывать все возможное что пользователь может сделать если даже думаешь что есть гарантия
 
Позитивный голос 0 Негативный голос
BlackBaroness написал(а):
Лично я при написании ртп делал N попыток поиска за тик, пока не найдется значение - так нагрузка фиксированная. Результат доставлялся через CompletableFuture
Нажмите для раскрытия...
вот только по идее это тоже самое как поиск за 1 тик только без лагов и с более большим потраченным временем и по сути ты ничего в процессе не сможешь сделать (добывать блоки и тд) Смогут ли игроки что либо делать пока будет происходить поиск ? Например 4 секунды нужно на задачу. За это время игроки не смогут взаимодействовать по идее с миром
 
Позитивный голос 0 Негативный голос
Galtap написал(а):
если bukkit однопоточный
Нажмите для раскрытия...
Вот почему, я и говорю что ведро - то еще ведро. С краником, другими приворотами, или без. Используй Фабрик/Forge

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


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

Ты можешь без проблем в любом потоке читать любые данные сервера (без использования блокирующих итераций) - но добавлять в обработку можно только в основном потоке.
 
Позитивный голос 0 Негативный голос
Galtap написал(а):
Ладно а как насчет синхронности в асинхронне? В синхрон добавить прогрузку чанков а в асинхрон проверки
Нажмите для раскрытия...
Не забывай про накладные расходы на планировщик задач и управление потоками. Поиск по правильному индексу будет в разы быстрее чем это
 
Позитивный голос 0 Негативный голос
HomaPlus написал(а):
Вот почему, я и говорю что ведро - то еще ведро. С краником, другими приворотами, или без. Используй Фабрик/Forge

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



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

Ты можешь без проблем в любом потоке читать любые данные сервера (без использования блокирующих итераций) - но добавлять в обработку можно только в основном потоке.
Нажмите для раскрытия...
но как то betterRtp может делать поиск параллельно процессу игры
 
Позитивный голос 0 Негативный голос
Можешь сделать примерно так:
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);
 
Позитивный голос 0 Негативный голос
Galtap написал(а):
вот только по идее это тоже самое как поиск за 1 тик только без лагов и с более большим потраченным временем и по сути ты ничего в процессе не сможешь сделать (добывать блоки и тд) Смогут ли игроки что либо делать пока будет происходить поиск ? Например 4 секунды нужно на задачу. За это время игроки не смогут взаимодействовать по идее с миром
Нажмите для раскрытия...
Я ничего не блокировал, пофиг вообще. оно вряд ли будет целых 4 секунды, условно 5 попыток за ник это 100 попыток в секунду, что очень много

flaweoff написал(а):
private final Consumer<Location> callback;
Нажмите для раскрытия...
Тут лучше использовать CompletableFuture
 
Позитивный голос 0 Негативный голос
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);
}
 
Позитивный голос 0 Негативный голос
Войдите или зарегистрируйтесь для ответа.
Назад
Сверху Снизу