Балансировщик БГ

The_Zealot · June 16

Для начала. Мне не совсем понятно, что же делается с распределением на бэгэ, если изменения есть:

Далее. Мне не совсем понятно, почему на пшоше делается все, кроме баланса по илвлу? То примам палкой бьем по голове, то по хилам. Почему все сводится исключительно к ограничениям? :PepeHmmm:

А почему?

А почему? х2

Я предлагаю 2 варианта решения. Адекватный - удалить бг из игры. Неадекватный будет далее.

Я немного наговнякал по-быстрому, вот что вышло:

Принцип (все отмеченное знаком "!" я не реализовывал и не тестировал, соответственно, только теоретическое представление):

Алгоритм балансировки без учета ролей и групп:
	Балансируется MIN_NUM_PLAYER (10) человек 5х5 по командам. В команды по очереди из очереди добавляется самый сильный и самый слабый.
	Каждый последующий игрок добавляется в ту комнду, где разница между средним уровнем шмота команды будет минимальной после его добавления.
	Если разница одинаковая, то игрок приоритетно добавляется в ту команду, где меньше игроков.
	Если игроков одинаковое количество, то игрок добавляется в любую.
	Если разница между количеством игроков в команде превышает MAX_DIFFERENCE_VALUE, то независимо от вычисления разницы среднего илвл игрок приоритетно добавляется в команду с наименьшим числом участников.

Дополнение с учетом ролей и групп:
	!Если после добавления разница по роли (например лекарь) между командами превышает MAX_DIF_ROLE_VALUE, игрок помещается в буферную очередь, а не команду.
	!Если игрок находится в составе группы, то выбор команды для группы осуществляется таким же образом, что и для одиночного игрока. Разница заключается в том, что илвл для такой группы - это средний илвл всех ее членов.
	!Если после выбора команды группа не проходит проверку по количеству или проверку по ролям, вся группы помещается в буферную очередь.
	!Если илвл игрока понижает средний илвл команды более, чем на MAX_REDUCE_VALUE, такой игрок помещается в буферную очередь. Дабы избежать такого исхода, можно ограничить регистрацию на поля боя для игроков, чей илвл менее MIN_ACCEPT_ILVL.
	
	!Буферная очередь* В нее попадают игроки, которые по каким-либо причинам не могут попасть на заполняемое бг в текущих условиях, но при этом, каждая итерация добавления участника начинается с попытки добавить именно их. Возможные причины: соотношение хилов, большая разница среднего илвла, премейд

Тесты проводились на 1000 бг.

Все тесты имеют вид:

543,516,500,526,523,543,542,543,509,545,538,546,498,503,546,545,525,520,506,545
539,545,524,530,511,528,542,516,541,512,512,507,519,528,501,534,518,534,543,545
525,521,500,502,528,500,534,517,515,535,537,538,532,528,542,506,497,547,503,550
536,500,513,499,510,542,498,543,509,538,496,515,537,512,506,543,505,519,543,520
503,516,549,499,534,523,509,523,515,529,537,544,521,550,539,510,526,543,507,514
545,524,506,542,527,508,527,496,542,550,544,537,500,533,546,522,533,500,517,528
514,505,523,528,541,510,519,517,499,514,544,541,507,504,550,529,543,508,525,519
530,503,514,503,526,505,520,532,513,539,502,521,531,527,515,528,537,542,509,527

Строка - это очередь на одно бг, где каждое число - илвл игрока. Строка может содержать 20, 30 или 80 значений. Сами значения находятся в диапазоне [450, 550]

Файл с тестами

out_all.txt

Результат при MAX_DIFFERENCE_VALUE = 1

MAX_DIFFERENCE_VALUE 1
Avg dif: 0 was found 283 time(s) is 28.3%
Avg dif: 1 was found 377 time(s) is 37.7%
Avg dif: 2 was found 194 time(s) is 19.4%
Avg dif: 3 was found 72 time(s) is 7.2%
Avg dif: 4 was found 43 time(s) is 4.3%
Avg dif: 5 was found 12 time(s) is 1.2%
Avg dif: 6 was found 4 time(s) is 0.4%
Avg dif: 7 was found 6 time(s) is 0.6%
Avg dif: 8 was found 4 time(s) is 0.4%
Avg dif: 9 was found 3 time(s) is 0.3%
Avg dif: 10 was found 1 time(s) is 0.1%
Avg dif: 11 was found 1 time(s) is 0.1%

Результат при MAX_DIFFERENCE_VALUE = 2

MAX_DIFFERENCE_VALUE 2
Avg dif: 0 was found 257 time(s) is 25.7%
Avg dif: 1 was found 373 time(s) is 37.3%
Avg dif: 2 was found 193 time(s) is 19.3%
Avg dif: 3 was found 91 time(s) is 9.1%
Avg dif: 4 was found 42 time(s) is 4.2%
Avg dif: 5 was found 17 time(s) is 1.7%
Avg dif: 6 was found 6 time(s) is 0.6%
Avg dif: 7 was found 8 time(s) is 0.8%
Avg dif: 8 was found 7 time(s) is 0.7%
Avg dif: 9 was found 1 time(s) is 0.1%
Avg dif: 10 was found 2 time(s) is 0.2%
Avg dif: 11 was found 2 time(s) is 0.2%
Avg dif: 12 was found 1 time(s) is 0.1%

Результат при MAX_DIFFERENCE_VALUE = 3

MAX_DIFFERENCE_VALUE 3
Avg dif: 0 was found 240 time(s) is 24%
Avg dif: 1 was found 344 time(s) is 34.4%
Avg dif: 2 was found 201 time(s) is 20.1%
Avg dif: 3 was found 101 time(s) is 10.1%
Avg dif: 4 was found 44 time(s) is 4.4%
Avg dif: 5 was found 30 time(s) is 3%
Avg dif: 6 was found 12 time(s) is 1.2%
Avg dif: 7 was found 7 time(s) is 0.7%
Avg dif: 8 was found 9 time(s) is 0.9%
Avg dif: 9 was found 3 time(s) is 0.3%
Avg dif: 10 was found 2 time(s) is 0.2%
Avg dif: 11 was found 3 time(s) is 0.3%
Avg dif: 12 was found 1 time(s) is 0.1%
Avg dif: 13 was found 1 time(s) is 0.1%
Avg dif: 15 was found 1 time(s) is 0.1%
Avg dif: 19 was found 1 time(s) is 0.1%

На самом деле, тестов я провел немного больше. В целом, получалось, что MAX_DIFFERENCE_VALUE=2 оптимальный вариант. На длинной дистанции, конечно, 2 хуже, чем 1, но разница невелика. Можно считать, на уровне погрешности.

Говнокод:

balance.h

#ifndef BALANCE_H
#define BALANCE_H

#include <iostream>
#include <algorithm>
#include <vector>

#define MIN_NUM_PLAYER          10
#define MAX_DIFFERENCE_VALUE    1

#define DEBUG(a) std::cout << a;

struct Player;
typedef std::vector<Player> PlayerList;

enum class Role
{
    Tank    = 0,
    DPS     = 1,
    Heal    = 2,
};

struct Player
{
    Player(int ilvl = 0);

    Role role   = Role::DPS;
    int ilvl    = 0;

    static void sortPlayerList(PlayerList &list);
    void operator=(int ilvl);
};


struct BattleGround
{
    BattleGround(int capacity = 20);
    static int getAvgTeam(const PlayerList &team);
    int getAvgDif();
    static int getAvgDif(const PlayerList &blueTeam, const PlayerList &redTeam);
    int getSizeDif();
    bool isEmpty();
    bool isFull();
    void printState();
    std::string getData();
    void clear();

    static int roleCount(const PlayerList &team, Role role);

    int capacity;
    PlayerList blueTeam;
    PlayerList redTeam;
};

bool balance(BattleGround &bg, const PlayerList &playerList);

#endif // BALANCE_H

balance.cpp

#include "balance.h"

Player::Player(int ilvl)
{
    this->ilvl = ilvl;
}

void Player::sortPlayerList(PlayerList &list)
{
    int size = list.size();
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size - 1; ++j)
        {
            if (list[j].ilvl > list[j + 1].ilvl)
            {
                Player temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
}

//// temp ////
void Player::operator=(int ilvl)
{
    this->ilvl = ilvl;
}


BattleGround::BattleGround(int capacity)
{
    this->capacity = capacity;
    blueTeam.resize(0);
    redTeam.resize(0);
}

int BattleGround::getAvgTeam(const PlayerList &team)
{
    int result = 0;
    for (auto iter : team)
    {
        result += iter.ilvl;
    }
    if (team.size() == 0)
    {
        return 0;
    }
    return result / team.size();
}

int BattleGround::getAvgDif()
{
    return abs(getAvgTeam(blueTeam) - getAvgTeam(redTeam));
}
int BattleGround::getAvgDif(const PlayerList &blueTeam, const PlayerList &redTeam)
{
    return abs(getAvgTeam(blueTeam) - getAvgTeam(redTeam));
}

int BattleGround::getSizeDif()
{
    return blueTeam.size() - redTeam.size();
}

bool BattleGround::isEmpty()
{
    return !(blueTeam.size() + redTeam.size());
}

bool BattleGround::isFull()
{
    return int(blueTeam.size() + redTeam.size()) == capacity;
}

void BattleGround::printState()
{
    std::cout << getData();
}

std::string BattleGround::getData()
{
    auto getList = [](PlayerList &list) -> std::string{
        int size = list.size();
        std::string result;
        for (int i = 0; i < size; ++i)
        {
            result.append(std::to_string(list[i].ilvl));
            if (i == (size - 1))
            {
                break;
            }
            result.append(", ");
        }

        return result;
    };
    std::string result;
    result.append("Blue team:            ");
    result.append(getList(blueTeam));
    result.append("\n");
    result.append("Average ilvl:         ");
    result.append(std::to_string(getAvgTeam(blueTeam)) + "\n");
    result.append("Red team:             ");
    result.append(getList(redTeam));
    result.append("\n");
    result.append("Average ilvl:         ");
    result.append(std::to_string(getAvgTeam(redTeam)) + "\n");
    result.append("Average difference:   ");
    result.append(std::to_string(getAvgDif(blueTeam, redTeam)) + "\n");
    result.append("Current capacity:     ");
    result.append(std::to_string(capacity));

    return result;
}


void BattleGround::clear()
{
    blueTeam.clear();
    redTeam.clear();
}

int BattleGround::roleCount(const PlayerList &team, Role role)
{
    int result = 0;
    for (auto iter : team)
    {
        if (iter.role == role)
        {
            result++;
        }
    }
    return result;
}

bool balance(BattleGround &bg, const PlayerList &playerList)
{
    int listSize = playerList.size();
    if (listSize % 2)
    {
        return false;
    }

    auto insertOne = [](BattleGround &bg, Player player){

        if (bg.getSizeDif() >= MAX_DIFFERENCE_VALUE)
        {
            bg.redTeam.push_back(player);
            return;
        }

        if (bg.getSizeDif() <= -(MAX_DIFFERENCE_VALUE))
        {
            bg.blueTeam.push_back(player);
            return;
        }

        if ((int)bg.blueTeam.size() == (bg.capacity / 2))
        {
            bg.redTeam.push_back(player);
            return;
        }

        if ((int)bg.redTeam.size() == (bg.capacity / 2))
        {
            bg.blueTeam.push_back(player);
            return;
        }

        PlayerList newBlueTeam = bg.blueTeam;
        PlayerList newRedTeam  = bg.redTeam;

        newBlueTeam.push_back(player);
        newRedTeam.push_back(player);
        if (BattleGround::getAvgDif(newBlueTeam, bg.redTeam) < BattleGround::getAvgDif(newRedTeam, bg.blueTeam))
        {
            //////// roles check ////////
            bg.blueTeam.push_back(player);
        }
        else
        {
            //////// roles check ////////
            bg.redTeam.push_back(player);
        }
    };

    if (bg.isEmpty())
    {
        if (listSize >= MIN_NUM_PLAYER)
        {
            PlayerList result;
            for (int i = 0; i < MIN_NUM_PLAYER; ++i)
            {
                result.push_back(playerList[i]);
            }
            Player::sortPlayerList(result);

            for (int i = 0; i < MIN_NUM_PLAYER / 2 - 1; i += 2)
            {
                bg.blueTeam.push_back(result[i]);
                bg.blueTeam.push_back(result[MIN_NUM_PLAYER - 1 - i]);
                bg.redTeam.push_back(result[i + 1]);
                bg.redTeam.push_back(result[MIN_NUM_PLAYER - 2 - i]);
            }
            bg.blueTeam.push_back(result[4]);
            bg.redTeam.push_back(result[5]);
        }
        if (listSize > MIN_NUM_PLAYER)
        {
            for (int i = MIN_NUM_PLAYER; i < listSize; ++i)
            {
                insertOne(bg, playerList[i]);
            }
        }
    }
    else
    {
        /////////////// code ///////////////
    }

    return true;
}

В месте комментария roles check можно добавить проверку по роли, особо не меняя ничего. Повозиться придется только с пати. А поскольку это все сделано за один вечер после работы, мне чет впадлу этим заниматься, ~~все равно всем насрать будет~~.

@DeadMouse, @Neff, скажите в чем проблема? Какую задачу нужно решить, чтобы что-то подобное появилось? Не ограничения хрен пойми какие, которые ничего, кроме негатива у людей не вызывают, а решения проблемы? Если я правильно понимаю и оцениваю, то по логике, описанной выше, проблем быть не должно. Время ожидания не должно увеличится у большинства игроков вообще. Разве только что у аутист-примов, где 1 воен на 4 хила. При этом люди не будут чувствовать, что их на бг изнасилуют уже со старта.

Спойлер

Если сильно надо, я конечно, могу, теоретически, потрать выходные, чтобы доделать все до ума и протестировать. Только мне что-то подсказывает, что это никому нахер не нужно :PepeHmmm:

Wokoko · June 16

Нихуя ты программист

randompandawowplayer · June 16

2 hours ago, The_Zealot dijo:

Разве только что у аутист-примов, где 1 воен на 4 хила

premades max size is 3 players now

Edited June 16 by randompandawowplayer

Sign In

Балансировщик БГ

Recommended Posts

The_Zealot

Wokoko

randompandawowplayer

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members

Who's Online 2 Members, 0 Anonymous, 361 Guests (See full list)

Browse

Activity