How to implement internet high scores in Google App Engine

Question

I want to implement internet high scores for my game. And give feedback to players which place they have (not only top100 or something like that). In normal SQL it would look like that:

SELECT COUNT(*) FROM Scores WHERE points > :newUsersPoints

and GQL have something similar

db.GqlQuery("SELECT * FROM Score WHERE points > :1", newUsersPoints).count()

but since count() is limited only to 1000 it won't be very useful in my case. Do you have any ideas on how to implement this?

I have two

First:

1. Use sharding counters idea (http://code.google.com/intl/pl/appengine/articles/sharding_counters.html) Create new "table" that stores how many scores are in some range(from_points, to_points)

2. Sum up all counters from above table where range.to_points < newUsersPoints

3. Find how many scores are bigger than scores in range where the new score is db.GqlQuery("SELECT * FROM Score WHERE points > :1 AND points >= :2 AND points < :3", newUsersPoints, range.from_points, range.to_points).count() + sumfrom2

4. Find range in which new score is in and increment its counter

5. Split ranges which counter is bigger than 1000 (or 999) so that 3. wouldn't reach the limit

6. Add new score to scores table

Which is quite complicated and error prone. We might increment some range and Timeout before adding the score. (not transactional)

Second idea:

From time to time (once every day?) sort all scores by points and give them new positions (script might Timeout so we have to do it in chunks)

To find out at which place new score is we just do

db.GqlQuery("SELECT * FROM Score WHERE points > :1 LIMIT 1", newUsersPoints).get().precalculated_position + 1

Any other ideas?

Answer 1

I've implemented Ranker in several GAE apps. They're Facebook Applications that have thousands up to hundreds of thousands of people playing. It works well, but for my purposes it has one big drawback: you need to declare in advance the final range over which the participant's scores will fall in. So this is bad for two reasons:

1. if you have a contest without an end, where people's scores can continue to climb without upper limit, you're hooped.

2. at the beginning of a contest, when everyone is bunched together near zero, the tree structure used by ranker.py is not efficient. the tree goes very deep and uses barely any of its breadth.

In other words, ranker.py is excellent for the case where you have contestants whose scores are randomly distributed in an even way over a known range of values. For other uses it is less than optimal.

I'm hoping to develop a more generally useful ranking engine soon. Will certainly update this thread when that happens!

Answer 2

This thread on the google-appengine group will probably be of interest. It also looks like there's a library, ranklist, specifically for this.

Basically, it sounds like they did something similar to sharded counters.