An algorithm for semi-random sorting (Java)

Question

I'm making a turn-based RPG game, and my method that sorts all "Actor" objects in the order in which they all attack sorts them completely randomly. I, however, want to improve this method so that an "agility" stat that every actor has is able to improve their roll. I've looked at several methods in the Collections class, and Arrays as well, but didn't seem to find anything that does what I want.

Right now, I'm thinking about getting a random int between 1 and 100, and having the agility score improve the odds. I tried separate ArrayLists for the Integers and a HashMap... but a no go on those.

My method as it is now:

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

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

I appreciate the help!

Answer 1

Your question doesn't go into much detail about the requirements about how agility influences your attack order, but I assume that you meant one of these two:

1. If one unit has higher agility than another, it always attacks first.
2. If one unit has higher agility than another, it usually attacks first.

If the first of these is true (units with higher agility always attack first), then what you're looking for is a way of permuting the array subject to the restriction that units with higher agility always end up before units of lower agility, but with everything else done randomly. One way to do this is as follows:

1. If you have N units, assign the numbers 1 ... N to the units at random. Don't assign the same number twice.
2. Sort the units into ascending order as follows:
   • Any unit with higher agility than another unit comes first.
   • Of two untis that are tied, whichever has the higher random number comes first.

You can show that this approach will arrange the units so that all units of a certain agility are randomly permuted relative to one another, but always come before lower-agility units. This takes time O(n log n) and can be done using Collections.sort, Collections.shuffle, and an appropriate Comparator.

If, on the other hand, you want the ordering to be random but influenced by the agility, you may want to think about using some sort of random distribution that can be controlled by some parameter. For example, you might assign each unit a priority drawn from a normal distribution whose mean is the agility and whose standard deviation is some reasonably large number (say, 20). This would mean that units with more agility are more likely to move before units with less agility, though there is a large amount of randomness. The advantage of this approach is that by tweaking the underlying distribution and its parameters (mean and variance in the case of a normal distribution), you can fine-tune to what extent the agility measure factors in.

As an example of a very simple approach, you might model unit speed as

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

Here, the more agility you have, the greater that your priority is. Increasing the amount of randomness changes the extent to which agility matters. Of course, this might be a bit skewed because each marginal increase in agility has more meaning, so you may want to replace the exponential with something like a logistic function.

Hope this helps!

Answer 2

Use Collections.sort() and provide a Comparator that uses a combination of a random number and agility to compute the rank.

Here's an implementation that would work. Note here that Player is the simplest possible interface that will work:

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

The important thing to note is that once calculated, a player's random agile score must be reused again for all later comparisons. This Comparator class s designed to be used once only (the map is required to be empty at the start of its use).

Answer 3

If you can't touch the Actor internals, you need a way of associating a 'roll' for each actor for a complete sort (which probably includes many calls to compare), but which is forgotten by the next sort.

In that case, I would do this:

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

Now when you want to sort an ArrayList of Actors, build an ArrayList of ActorComparables, sort those, and build a resulting list out of the ActorComparables.

Answer 4

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

Then you can call

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

Answer 5

A whole example using a TreeSet (a SortedSet implementations that guarantees the elements are always ordered, using a Comparator in this case):

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