一种半随机排序算法(Java)

Question

我正在制作一个基于回合制的RPG游戏,我的方法按照所有"Actor"对象的顺序对所有"Actor"对象进行排序,这些对象完全随机排序.但是,我希望改进这种方法,以便每个演员都拥有的"敏捷"数据能够提高他们的成绩.我已经查看了Collections类和Arrays中的几个方法,但似乎没有找到任何符合我想要的方法.

现在,我正在考虑获得1到100之间的随机int,并且敏捷得分可以提高几率.我为整数和一个HashMap尝试了单独的ArrayLists ......但是没有继续使用它们.

我现在的方法是:

// 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

使用Collections.sort()并提供一个Comparator,它使用随机数和敏捷性的组合来计算排名.

这是一个可行的实现.请注意,这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 2

关于灵活性如何影响攻击顺序的要求,你的问题没有详细说明,但我认为你的意思是这两个中的一个:

1. 如果一个单位具有比另一个单位更高的敏捷性,它总是首先攻击.
2. 如果一个单位具有比另一个单位更高的敏捷性,它通常会先攻击.

如果其中第一个是真的(具有更高敏捷性的单位总是首先攻击),那么你正在寻找的是一种置换数组的方法,受制于具有较高敏捷性的单位总是在较低敏捷性单位之前结束的限制,但是其他一切随机完成.一种方法是这样做:

1. 如果您有N个单位,请随机将数字1 ... N分配给单位.不要两次分配相同的号码.
2. 按单位对单位进行升序排序,如下所示:
   • 任何具有比其他单位更高敏捷性的单位都是第一位的.
   • 在两个被绑定的uniss中,以较高的随机数为准.

您可以证明这种方法将安排单位,以便所有具有某种敏捷性的单位相对于彼此随机置换,但总是在低敏捷单位之前.这需要时间为O(n log n)的和可以做到用Collections.sort,Collections.shuffle以及适当的Comparator.

另一方面,如果您希望排序是随机的但受敏捷性的影响,您可能需要考虑使用某种可由某些参数控制的随机分布.例如,您可以为每个单位分配一个优先级,该正态分布的平均值是敏捷性,其标准偏差是一个相当大的数字(例如,20).这意味着具有更高敏捷性的单位更有可能在灵活性较低的单位之前移动,尽管存在大量随机性.这种方法的优点是通过调整基础分布及其参数(正态分布情况下的均值和方差),您可以微调灵敏度测量因素的程度.

作为一种非常简单的方法的示例,您可以将单位速度建模为

优先级= e ^{(敏捷/ 100)+随机(1,2)}

在这里,您拥有的灵活性越高,您的优先级就越高.增加随机性的数量会改变敏捷性的重要程度.当然,这可能有点偏斜,因为敏捷性的每个边际增加都有更多意义,所以你可能想用像逻辑函数这样的东西来代替指数.

希望这可以帮助!

Answer 3

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);