Алгоритм полуслучайной сортировки (Java)

Question

Я делаю пошаговую RPG-игру, и мой метод, который сортирует все объекты «Актер» в порядке, в котором они все атакуют, сортирует их совершенно случайным образом. Я, однако, хочу улучшить этот метод, чтобы статистика «ловкости», которую имеет каждый актер, могла улучшить его бросок. Я посмотрел на несколько методов в классе Collections, а также на Arrays, но, похоже, не нашел ничего, что делает то, что я хочу.

Прямо сейчас я думаю о том, чтобы получить случайное значение от 1 до 100, и чтобы показатель ловкости улучшил шансы. Я пробовал отдельные списки ArrayLists для целых чисел и HashMap ... но не надо.

Мой метод, как сейчас:

// getFriendlies(), getHostiles(), and attack_order are all ArrayLists

public void calculateAttackOrder() {
        attack_order.addAll(getFriendlies());
        attack_order.addAll(getHostiles());
        Collections.shuffle(attack_order);
}

Я ценю помощь!

Answer 1

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

1. Если один юнит обладает более высокой ловкостью, чемдругой, он всегда атакует первым.
2. Если один юнит обладает большей ловкостью, чем другой, он обычно атакует первым.

Есливо-первых, это правда (юниты с более высокой ловкостью всегда атакуют первыми), а затем вы ищете способ перестановки массива с учетом ограничения, заключающегося в том, что юниты с более высокой ловкостью всегда оказываются перед юнитами с меньшей ловкостью, но со всеминаче сделано случайно.Один из способов сделать это заключается в следующем:

1. Если у вас N единиц, присвойте номерам 1 ... N единицы случайным образом.Не назначайте один и тот же номер дважды.
2. Сортируйте юниты в порядке возрастания следующим образом:
   • Любой юнит с более высокой ловкостью, чем другой юнит, идет первым.
   • Из двух единицкоторые привязаны, в зависимости от того, какое из случайных чисел будет на первом месте.

Вы можете показать, что этот подход упорядочит единицы так, что все единицы определенной ловкости случайным образом переставляются относительнодруг другу, но всегда предшествуют юнитам с меньшей ловкостью.Это занимает время O (n log n) и может быть выполнено с использованием Collections.sort, Collections.shuffle и соответствующего Comparator.

Если, с другой стороны, вы хотите, чтобы порядок был случайным, но Под влиянием ловкости вы можете подумать об использовании некоторого рода случайного распределения, которым можно управлять с помощью какого-либо параметра.Например, вы можете назначить каждому юниту приоритет, полученный из нормального распределения, чье среднее значение - ловкость, а стандартное отклонение - некоторое достаточно большое число (скажем, 20).Это будет означать, что юниты с большей ловкостью с большей вероятностью будут двигаться раньше юнитов с меньшей ловкостью, хотя существует большое количество случайностей.Преимущество этого подхода заключается в том, что, настраивая базовое распределение и его параметры (среднее значение и дисперсию в случае нормального распределения), вы можете точно настроить степень, в которой учитывается показатель гибкости.

КакВ качестве примера очень простого подхода вы можете смоделировать единичную скорость как

priority = e ^{(agility / 100) + random (1, 2)}

Здесь, чем выше ловкость, тем выше приоритет.Увеличение количества случайности меняет степень, в которой ловкость имеет значение.Конечно, это может быть немного искажено, потому что каждое предельное увеличение ловкости имеет большее значение, поэтому вы можете заменить экспоненту чем-то вроде логистической функции .

Надеюсь, это поможет!

Answer 2

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

Вот реализация, которая будет работать. Обратите внимание, что Player - это самый простой интерфейс, который будет работать:

public interface HasAgility {
    /** @return value between 0 and 1 */
    double getAgility();
}

public class Player implements HasAgility {
    double agility;
    double getAgility( return agility; );
   // rest of class
}

public class MoveComparator implements Comparator<HasAgility> {
    /** Need to calculate the agility once, and keep using that same value, for each player */
    private Map<HasAgility, Double> playerAgilities = new HashMap<HasAgility, Double>();

    private Double getRandomAgility(HasAgility player) {
        Double randomAgility = playerAgilities.get(player);
        if (randomAgility == null) {
            randomAgility = Math.random() * player.getAgility();
            playerAgilities.put(player, randomAgility);
        }
        return randomAgility;
    }

    public int compare(HasAgility o1, HasAgility o2) {
        return getRandomAgility(o1).compareTo(getRandomAgility(o2));
    }
}

public static void main(String args[]) {
    List<Player> players= new ArrayList<Player>();
    Collections.sort(players, new MoveComparator());
}

Важно отметить, что после расчета случайный проворный счет игрока должен быть снова использован для всех последующих сравнений. Этот класс Comparator предназначен для использования только один раз (карта должна быть пустой в начале использования).

Answer 3

Если вы не можете прикоснуться к внутренним объектам актера, вам нужен способ связать «бросок» для каждого актера для полной сортировки (которая, вероятно, включает в себя множество вызовов для сравнения), но которая будет забыта при следующей сортировке. 1001 *

В таком случае я бы сделал это:

public class ActorComparable {
  Actor actor;
  int roll;

  public ActorComparable(Actor actor) {
    this.actor = actor;
    roll = Math.Random(100) + actor.getAgility();
  }

  public getActor() {
    return actor;
  }

  public getRoll() {
    return roll;
  }

  public int compareTo(Actor that) {
    return this.getRoll() - that.getRoll();
  }
}

Теперь, когда вы хотите отсортировать ArrayList из Actors, создайте ArrayList из ActorComparables, отсортируйте их и создайте итоговый список из ActorComparables.

Answer 4

Целый пример с использованием TreeSet (реализации SortedSet , которые гарантируют, что элементы всегда упорядочены, с использованием Comparator в данном случае):

class Actor {
    private int agility;
    private double weight = Math.random(); 

    public Actor(int agility) {
        this.agility = agility;
    }
    public double getComputedAgility() {
        return agility * weight;
    }
}

public class TestRandomActors {
    public static void main(String[] args) {
        Collection<Actor> collection = new TreeSet<Actor>(
                new Comparator<Actor>() {
                    @Override
                    public int compare(Actor a1, Actor a2) {
                        return 
                            a1.getComputedAgility() > a2.getComputedAgility() ? -1 : 1;
                    }
                }
            );

        collection.add(new Actor(30));
        collection.add(new Actor(31));
        collection.add(new Actor(60));

        for (Actor actor : collection)
            System.out.println("Actor with agility = " + actor.getComputedAgility());
    }
}

Answer 5

class Actor implements Comparable {

    private int agility;
    private int randomAgility;

    private int getInitiative() {
        //You can change this method as you see fit
        return randomAgility + this.agility;
    }

    public void generateRandomAgility() {
        this.randomAgility = (Math.random() * 100);
    }

    public int compareTo(Object o) {
        Actor other = (Actor)other;
        return this.getInitiative() - other.getInitiative();
    }
}

Тогда вы можете позвонить

for (Actor a : attack_order) {
    a.generateRandomAgility();
}
Collections.sort(attack_order);