Как сделать лидерборд в гонках

Лидерборд — это таблица, ранжирующая участников заезда по какому-либо критерию, например, по позиции на маршруте. Фактически, это логика гонок, которая определяет, кто побеждает, а кто проигрывает. Правильная реализация лидерборда — не такая уж простая задача, как может показаться, потому что она зависит от того, как игра хранит трассу, и во многом пересекается с кодом ИИ-оппонентов.

Если отталкиваться от методологии, которую я описал в статье Как сделать ИИ для гонок, то задача упрощается – можно использовать следующий подход, который показался мне весьма надежным и лишенным логических изъянов.

Сначала для каждого участника игра определяет ближайший сегмент трассы. Это уже делается для вычисления целевой точки для ИИ, так что функция поиска просто переиспользуется.

Мой алгоритм опирается на пространственно-временную когерентность — то есть, на тот факт, что машина едет с предсказуемой скоростью и более-менее точно вдоль трассы, не срезая большие участки. Это позволяет оптимизировать поиск, отбрасывая большую часть сегментов как заведомо слишком далекие, и рассматривать только несколько ближайших к машине (сложность O(1)). Чем больше доступного гонщикам пространства вокруг дороги, тем, к сожалению, хуже возможности для такой оптимизации. Но если дорогу можно срезать, то гонки получаются уже какие-то нетривиальные, ведь это жульничество, и оно, по идее, должно пресекаться. Я в своей игре решил этой проблемы не касаться и просто сделать трассы с тесными стенками, оптимальные для моего алгоритма.

На кольцевой трассе последняя точка в цепи сегментов совпадает с первой. Это важное свойство, позволяющее отсчитывать пройденные круги: когда машина пересекает последний сегмент, счетчик кругов увеличивается на 1. Чтобы нельзя было обмануть систему, отъехав назад и снова вернувшись на финиш, необходимо запретить обратное зацикливание индексов. То есть, если игрок, находясь в сегменте 0, поедет назад, он уже не попадет в сегмент 99 — его сегмент будет все равно 0. Таким образом, каждый участник должен честно намотать нужное количество кругов для зачета.

На данном этапе уже можно написать функцию сортировки участников по их количеству кругов и позиции на круге (то есть, индексу сегмента). В функции-компараторе нужно сначала сравнить круги и вернуть участника с большим количеством кругов, а если они одинаковы, то сравнить позиции.

participants.sort!((a, b) {
    if (a.laps != b.laps)
        return a.laps > b.laps;
    if (a.trackSegmentIndex != b.trackSegmentIndex)
        return a.trackSegmentIndex > b.trackSegmentIndex;
    return false;
});

После сортировки массива машин можно каждой из них присвоить позицию для дальнейшего использования (например, для вывода на экран):

foreach (i, car; participants)
{
    car.racePosition = i + 1;
}

Такая сортировка отлично работает в процессе гонок, когда участники обгоняют друг друга. Но для того, чтобы точно определить победителя на финише, позиции на основе индекса сегмента недостаточно: два лидера могут идти нос к носу, с равными индексами. Все решает время. Для каждого участника нужен таймер, хранящий пройденное от начала гонки время в дробных секундах. Когда машина пересекает финишную черту, таймер останавливается. У кого получилось наименьшее время, тот и победил. Итоговая таблица результатов составляется путем сортировки участников по времени финиширования:

participants.sort!((a, b) {
    if (a.finished && b.finished)
        return a.raceTime < b.raceTime;
    if (a.laps != b.laps)
        return a.laps > b.laps;
    if (a.trackSegmentIndex != b.trackSegmentIndex)
        return a.trackSegmentIndex > b.trackSegmentIndex;
    return false;
});

Примечания и допущения:

• В начале гонки машины должны быть выстроены перед стартовой линией, индексы сегмента у всех 0, вне зависимости от очередности.
• Если кто-то из участников поехал назад, то его позиция должна сокращаться до начала текущего круга. Количество пройденных кругов не уменьшается.
• Если два и более участников поехали назад и пересекли стартовую точку в обратном направлении (смысла в этом нет, но вдруг?), то них индексы сегмента будут равны 0, и они по отношению друг к другу будут на равных, пока не развернутся, снова пересекут старт и поедут дальше с приращением позиции. Я решил не усложнять алгоритм разбирательством, кто из них впереди, кто позади, хотя, в теории, можно ввести бесконечно растущий отрицательный индекс сегмента.