All Articles

MTG: Small AngularJS project

Every now and then me, my brother and some friends get together to play Magic the Gathering. We usually play a small tournament where everyone plays against each other once (aka Round-Robin) and the winner gets a small prize.

So I decided to make a small webapp to help with matchmaking and scorekeeping. It’s completely in HTML/JS and will work without a webserver. It can run directly by just opening the index.htm file. The only dependency is the cdn for the font-awesome icons.

You can find the code here: https://github.com/Tethik/mtg

Design

For design I used the Kube CSS framework, which I’ve been using as an alternative to Pure. I still think Pure is good, but it’s nice to have alternatives. Otherwise everything starts to look too samey. I also used the font-awesome icons. Well, one of them. The layout seems to be responive, which is a cool bonus since I never intended it to be. I guess Kube did that for me.

Matchmaking

For the Round-Robin matchmaking I made up my own algorithm. Preferably as many players as possible should be playing at the same time at the same time as well as having a random order. First I generate all the matches (O(n log n)?), then I randomly shuffle them (O(n)?). Finally, I pick out the matches one at a time so that matches with the same players aren’t picked close to each other.

This is what that snippet looks like from the app. A match is “picked” when an index is assigned to it.

$scope.matches = ... All the round robin matches. (n-1) + (n-2) + ... + 1.
matches_without_index = random_shuffle($scope.matches)

picked_players = [];
for(var i = 0; i < $scope.matches.length;) {
	var m = 0;
	for(; m < $scope.matches.length; m++) {
		var match = $scope.matches[matches_without_index[m]]; // accessing the random order.

		if(match.index > -1)
			continue; // already visited.

		if(picked_players.indexOf(match.players[0]) > -1 || picked_players.indexOf(match.players[1]) > -1)
			continue; // at least one of the players already has a matchup this round.

		match.index = i++;
		picked_players.push(match.players[0]);
		picked_players.push(match.players[1]);
		break; // This break can probably be removed
	}

	if(m == $scope.matches.length) {
		picked_players = []; // new round.
	}
}

So probably not the most optimal solution. I think the problem can be reduced to finding a series of Hamilton Paths in a complete graph so that each edge is visited at least once in the series.

After some research I found that wikipedia suggests this algorithm instead. http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

It would be interesting to try out these algorithms in a better language to see the difference in times.

Todo?

Some improvements I’d like to do:

  • Add filtering on the matches based on player name.

  • Add other types of tournaments, Swiss for example. Round-Robin takes too long to play if there are more than 5 players.

  • Refactoring (always)

  • Perhaps improve the matchmaking algorithm to be more correct.

Published Jun 20, 2014

Security Engineer with a dash of software. Originally from Stockholm, now in Berlin. I like to hack things.