Archive

Tag Archives: algorythm

Some time ago I designed very efficient pattern of top-n table implementation for social games. There are a lot of users (few millions). Our goal is quickly compose top-n table for any user. Generally, each user has its own top-n table, because the table contains information about the user either he’s in the top or not. Let’s assume users has the score and we build the top-n table by that score. So, most top user in the table (rank=1) has max. score.
As we have social game, so, it’s ok to have not exactly actual top-n table, but some version cached for an hour or 20 minutes. We will update the table in the cache every 20 minutes. The question is about how to represent information of the user (current one). His score is available, but his rank in the actual top-n table is not available if the user is not in the top. It should be calculated on fly. Keep in mind, that we don’t cache whole users table ordered by the score, but only n top records.
The idea is to avoid full table scan but and use linear interpolation to gues approximate rank for user out of top table.
If user has the same score as last user in the top then the rank is N+1.
In other case:
rank = -(UsersCount – N – 1)*(score – Max)/Max + N + 1,
where
UsersCount is total number of users,
N is the size of top table,
score is the score of the user,
Max is the score of last user in the top table.

Advertisements

I’m working on multiplayer realtime strategy game. Today I implemented method for getting 3 units of the player which are nearst to the station creation point. See below. As you can see it’s regular problem of getting N min(max) elements of array. The task looks pretty regular, even standard. But I can’t say that such tasks are daily ones. And what about you?

                // get 3 units nearst to the x, y
                var distances = new int[StationCreationUnitsNumber];
                var units = new Unit[StationCreationUnitsNumber];
                var taken = 0;
                foreach (var unit in player.Units)
                {
                    var d = _distance2(unit.X, unit.Y, x, y);

                    // check new point against taken ones
                    for (var i = 0; i < taken; ++i)
                    {
                        // if new point should be taken
                        if (d <= distances[i])
                        {
                            // shift already taken points
                            for (var j = taken – 1; j > i; –j)
                            {
                                distances[j] = distances[j – 1];
                                units[j] = units[j – 1];
                            }

                            // take the point and jump to process next one
                            distances[i] = d;
                            units[i] = unit;
                            goto units_loop_end;
                        }
                    }

                    // take initial point anyway
                    if (taken < StationCreationUnitsNumber)
                    {
                        distances[taken] = d;
                        units[taken] = unit;
                        ++taken;
                    }

                units_loop_end:
                    ;
                }