Online leaderboards are are great feature that gives your more competitive players a lot of replayability, allowing them to continue replaying your content to keep pushing each other to a new higher score. It can also be a source of excess database load if you let things get out of hand.
I'm going to use the simple example of a high score leaderboard to walk through how to initially set things up, and how to optimise. With the example leaderboard, we'll sort things so higher score is better, but the same process will work for any sortranking like lap times where smaller is better.
We'll start with a description of the entries in the database. I'll use a pseudo SQL style here, but note that this will work with any kind of database such as MySQL, PostgreSQL or MongoDB.
CREATE TABLE tblEntry (
nUserId INT,
nStageId INT,
nScore INT///
);Where:
nUserId is some sort of unique identifier for the player.
nStageId is a unique identifier for each stage, eg: each level or track in your game.
nScore is the thing we'll be ranking players on, here it's the score, but could be lap time in a racing game.
We'll also create two indexes:
CREATE INDEX idxStageScore ON tblEntry(nStage, nScore);
CREATE UNIQUE INDEX idxUserIdStage ON tblEntry(nUserId, nStage);idxStageScore will allow us to quickly split the entries by stage and sort them by score.
idxUserIdStage this unique index will make sure the player only has one entry per stage to keep things simple.
With this setup, to calculate the rank of a score nPlayerScore, you have to count every row above it in the leaderboard.
SELECT COUNT(*) FROM tblEntry WHERE nStageId=1 AND nScore < $nPlayerScore;And now we know the exact rank of the player (ignoring other players with the exact same score). This should be a pretty efficient query, since it should be able to be calculated by just scanning the index data.
You could cache the value on the entry and update it occasionaly in the background. But that's extra code, and in the end will make the database work even more than directly calculating the rank when needed.
When showing the player their leaderboard position, we also want to show the players around them. This is simple enough to approximate by getting a set of scores above and below what the player submitted. This is imperfect, as there may be multiple players with the same score, but it's very much good enough.
SELECT * FROM tblEntry WHERE nStage=1 AND nScore > $nPlayerScore ORDER BY nSCORE ASC LIMIT 10;
SELECT * FROM tblEntry WHERE nStage=1 AND nScore < $nPlayerScore ORDER BY nSCORE DESC LIMIT 10;This will give 10 scores above and below what the player submitted. Perfect for building a leaderboard. Note that the results above the plater are sorted in the wrong order, so you'll need to manually fix that in code.
Since we know the players score, we can use that to guesstimate what each opponents rank is be how far away they are from them.
It turns out nobody really cares (or will never know) if they aren't perfectly ranked in the dark depths of the leaderboard. Usualy any increase in points in the middle of the leaderboard will lead to a big jump in rank as well, so a player will move so far they cannot even see their old position anymore.
At the top of the leaderboard it is very important to have correct rankings, so for the top 100 we'll use exact rank calculation. And for the rest of the leaderboard we can estimate the players rank.
We can estimate with just a few simple numbers, firstly what the top 100 score is, and how many players are in the leaderboard.
Here is the table layout we'll use to cache that data:
CREATE TABLE tblRankingCache (
nRankingCacheId PRIMARY KEY,
nStageId INT,
nTop100Score INT,
nNumEntry INT
);The plan here will be to always perfectly rank the top 100, that's usually where it really matters to players. And since the difference in scores between 1st and 2nd is usually a lot different than between 345341st and 345342nd, estimations will be way off at the top.
So we cache the score of the 100th ranked entry, and how many entries are behind it in the leaderboard. From here we can do a simple linear approximation for any score and where it would rank on the leaderboard.
Firstly we need to work out how many players are in the leaderboard:
SELECT COUNT(*) FROM tblEntry WHERE nStageId = 1;We set this value on nNumEntry in the cache table. If this number is less than 100, then we set nTop100Score to 0. As we don't have enough entries (yet).
If we do have enough entries, then we need to work out the top 100 score:
SELECT nScore FROM tblEntry WHERE nStageId = 1 ORDER BY nScore OFFSET 100; And we set this value in the nTop100Score field.
Now that we have this cache data it's easy to approximate a rank for a given score nPlayerScore:
fRankPerScore = (nMaxScore - nMinScore) / nNumPlayer
nRank = (nScore - nMinScore) * fRankPerScore;This way, by using a simple cache table that is occasionaly updated, you can quickly generate the rank for any score.
When showing a player their local leaderboard, with all the players you can select a sorted chunk of players from above and below
With our table setup, we are only allowing one entry per user per stage in this leaderboard. It is possible to store multiple per user if your game needs it, perhaps for showing a full history, or wanting to rank all time best vs best of the week. These things are possible, but you'll need to add extra columns to the index, and keep it updated whenever the player submits a new score.
Previous: Hashing player passwords on your game server