Round-Robin Scheduling Algorithm for Group Looting

In my previous post, I mentioned the Round-Robin Scheduling algorithm which was an alternative solution to the Josephus Problem. Although the algorithm is slow for the Josephus Problem, it excels at fair scheduling; so, I’ll describe how the Round-Robin Scheduler can be used to equally distribute a finite set of resources such as Group Looting in World of Warcraft (with some variations).

Group Looting Mechanics

Looting is the process of searching a corpse for valuable items. Certain items are better than others and their value is denoted by their color: from grey (poor quality) to orange (legendary quality).

Warglaive of Azzinoth

When raiding dungeons in WoW as a party, there are several options for loot distribution. Among them is the Round-Robin option which distributes lootable corpses equally among the party; however, certain corpses, such as bosses, may yield higher quality items.

It’s easy to see that this system can be unfair when a player can manipulate the order of deaths. Instead, I’ll cover a fair algorithm based on automatically distributing weighted corpses.

Extended Round-Robin Algorithm for Group Looting

First, let’s add weights to corpses. We need to quantify the value of corpses before adding weights. This can be done using several methods for accuracy; however, for the sake of simplicity, I’ll assign static weights:

Boss (50)
Elite Mob (10)
Trash Mob (1)

These weights will accumulate like on a Player like a bar tab. At the end of the game, we want every player to consume equal weight.

public class RoundRobinScheduler {
	private static class Player {
		public String name;
		public int weight;

		public Player(String name, int weight) {
			this.name = name;
			this.weight = weight;
		}

		// Returns the weight of the corpse looted
		public void loot(int corpseWeight) {
			// Implementation hidden
		}
	}
}

We can use the aforementioned mob weights using the class definition above for their Player. Each player increases their weight when they loot a corpse of significant value.

Consider the situation now: given that there is a sequence of players in a party, the corpses to be looted are distributed from the first player in the party to the last player in the party if all mobs were trash mobs i.e. weight of one.

The special case is when a player is able to loot either an elite mob or a boss mob. In such cases, we want distribution to be fair while adhering to the rules of Round-Robin; thus, we disallow a player to loot another corpse until a proportional number of corpses has been looted with equal weight to the weighted corpse looted by the player.

import java.util.Queue;

public class RoundRobinScheduler {
	private static class Player {
		public String name;
		public int value;

		public Player(String name, int weight) {
			this.name = name;
			this.weight = weight;
		}

		public void loot(int corpseWeight) {
			// Implementation hidden
		}
	}

	Queue<Player> players;

	public RoundRobinScheduler();
	public void schedule(String name, int weight);
	public void loot(int corpseWeight);
}

Our interface for the Round-Robin scheduler should appear as above. We schedule players according their name and their weight after looting a corpse. The special case is when the party is formed such that the weight of all players is zero.

import java.util.LinkedList;
import java.util.Queue;

public class RoundRobinScheduler {
	private static class Player {
		public String name;
		public int weight;

		public Player(String name, int weight) {
			this.name = name;
			this.weight = weight;
		}

		// Returns the weight of the corpse looted
		public void loot(int corpseWeight) {
			// Implementation hidden
		}
	}

	Queue<Player> players;

	public RoundRobinScheduler() {
		players = new LinkedList();
	}

	public void schedule(String name, int weight) {
		players.add(new Player(name, weight));
	}

	public void loot(int corpseWeight);
}

We begin implementing our algorithm by initializing our player list as empty. Afterwards, we can manually schedule players starting from the first player to the last player in the party to loot corpses by calling the schedule(String, int) method with the specified player name and their default weight (zero).

import java.util.LinkedList;
import java.util.Queue;

public class RoundRobinScheduler {
	private static class Player {
		public String name;
		public int weight;

		public Player(String name, int weight) {
			this.name = name;
			this.weight = weight;
		}

		public void loot(int corpseWeight) {
			// Implementation hidden
		}
	}

	Queue<Player> players;

	public RoundRobinScheduler() {
		players = new LinkedList();
	}

	public void schedule(String name, int weight) {
		players.add(new Player(name, weight));
	}

	public void loot(int corpseWeight) {
		Player player;
		while (!players.isEmpty()) {
			player = players.remove();

			if (player.weight > 0)
				schedule(player.name, --player.weight);
			else {
				player.loot(corpseWeight);
				schedule(player.name, corpseWeight);
				break;
			}
		}
	}
}

The loot(int) method is the heart of the Round-Robin algorithm. When a corpse appears, the loot(int) method is called which cycles through the player list and allows the player with the least weight to loot the corpse. Afterwards, the player inherits the weight of the corpse.

The next corpse available will be lootable by the player with the least weight on the list once again and the process will continue iteratively. For example, if a player loots a an elite corpse, they will be unable to loot another corpse until all other players have looted corpses of equal weight.

Applying the Algorithm and Looting Real Corpses

private static class Player {
	public String name;
	public int weight;

	public Player(String name, int weight) {
		this.name = name;
		this.weight = weight;
	}

	public void loot(int corpseWeight) {
		System.out.println(name + " has looted the corpse!");
	}
}

Testing the algorithm is trivial by implementing the loot(int) method for the Player class. Although this method can be implemented using a variety of methods, I’ll simply print out the player name to the standard output for the sake of testing.

public static void main(String[] args) {
	final int ELITE_MOB = 2;
	final int TRASH_MOB = 1;

	RoundRobinScheduler scheduler = new RoundRobinScheduler();
	scheduler.schedule("Boomkin", 0);
	scheduler.schedule("Warlock", 0);
	scheduler.schedule("Priest", 0);
	scheduler.schedule("Warrior", 0);

	scheduler.loot(ELITE_MOB);

	scheduler.loot(TRASH_MOB);
	scheduler.loot(TRASH_MOB);
	scheduler.loot(TRASH_MOB);

	scheduler.loot(TRASH_MOB);
	scheduler.loot(TRASH_MOB);
	scheduler.loot(TRASH_MOB);

	scheduler.loot(ELITE_MOB);
}

The test code above uses smaller weights for the sake of simplicity. We assume that the mobs have been killed in the specified, sequential order; thus, their corpses are available for looting in that sequence. The first player can loot the first corpse with a weight of two; consequently, every other player must loot mobs with proportional weight, two, before the first player can loot another corpse.

Boomkin has looted the corpse!
Warlock has looted the corpse!
Priest has looted the corpse!
Warrior has looted the corpse!
Warlock has looted the corpse!
Priest has looted the corpse!
Warrior has looted the corpse!
Boomkin has looted the corpse!

Therefore, I have demonstrated the extended Round-Robin scheduling algorithm using weights with hopes of fair loot distribution. This algorithm can be extended further by extending the implementation of the loot(int) method of the Player class.

Post a Comment

About Gio

Search

Categories

Recent Posts

Projects