Auto-Balancing Implementation

[cyrili]

willing to code this (cause i'd like it implemented and want to learn lua):


any suggestions for changes to the ui or functionallity? just want to talk this trough before i start investing time if this is actually wanted.

algorithm would work optimizing lane balance, game balance and preference match based on userdefined weighting of the three (squads would be a hard constraint).

[Exotic_Retard]

willing to code this

and this alone makes you very valuable.

we develop faf on github:
https://github.com/FAForever

this is split into numerous repos, and the one you are interested in is the fa repo:
https://github.com/FAForever/fa
it contains the lobby and game code and its in lua so thats good for you since you want to learn it.

simple make a fork, get it set up so your code launches in offline mode and you can start writing it, then make a pr and theres a good chance it will be accepted.

if you need any help dont hesitate to ask, and to increase your chances of making a successful pr talk to: icedreamer, crotalus i guess speed2 and others to develop your idea, it certainly has some potential

aso for suggestions i think you want to swap numbers and letters - keep number for the teams as they were before and assign letters to the lanes instead, mostly so people dont get confused too much

also this is a pretty significant change so it might need to be hidden away if auto teams are off or manual

it looks like it could be a bit of a handful to setup, could look at some way of generating a suggestion or storing a default setup with the map, or both. i recall some talk of an implementation like that which takes the angles from the centre of the map and uses them to determine lanes

[cyrili]

thanks for the kind words.


already have a copy of faf's lua code on my pc.

how polished does the code have to be for a pull request? because for me alone it will be realy hard to make it bug free without someone thats not me trying to break the code first. (should i post it somewhere else first?)

yeah, my hope is to get some feedback here. so something usefull comes out of this instead of just a very time consuming exercise.

good call with the number problem. definetly agree. Guess it'll be upper case for lane preference and lower case for squads (greek letters dont exist for that font..)

about your last point. could it be that you're talking about this post (page 2) witch i actually wrote 2 months ago? (didnt get to do anything since then)
sure would be a lot better if a lane proposal was stored directly in the map files, as it would give the possibility to the map makers to edit them.

*edit*
and just to give a timeframe: this will take me approximately 2 months or more with the time i have at hands right now.

[Exotic_Retard]

knowing my own prs, polished is nice but not necessary. however it does need to be polished to be actually accepted - so the idea is you make a buggy pr then "inspire" others to fix it xD (dont tell icecreamer my methods!)


damn. yes this is the post i was thinking of: viewtopic.php?f=41&t=12862&start=10#p132156
the lane proposal has advantages and disadvantages to making that proposal on the fly - 99% of maps dont have said proposal put in, so how would we ensure backwards compatibility if every map ever doesnt have it? its essentially a lot of work but it wont be seen

thats why i think that having it auto made sounds a bit better, but still not ideal since it will mean you might have to tweak it every game ever if it gets it wrong, even by just a little.

maybe some combination of those two, or perhaps it remembers your proposal, or perhaps that proposal is stored in the map table in the vault so we can add and tweak them retroactively? perhaps have multiple proposals per map like topvbottom and leftvright?

how will ffa or uneven teams or alternate setup work?

also im not totally sure i understand how that ui works on tha pic. what are squads? are they teams?
what i took it as was a way to designate a position as a lane, and an enemy position with the same designation wil be counted as the opposite of that, so it will put more equal skilled players there, or something, right? perhaps some explanation is needed there.


this seems to me like the kind of thing that would certainly be cool, but tbh im not sure what it would achieve, and whether your efforts are better spent elsewhere, perhaps on that original idea you had since it works in the background, and doesnt complicate player ui. i would start with that first, since i think its nice to have it regardless (either as primary or supplementary to your idea) and then we can decide if we want to take this further or not.

im looking forward to what you conjure up, good luck

[cyrili]

ehh, first of: what's ffa, and what's alternate setup?

perhaps that proposal is stored in the map table in the vault so we can add and tweak them retroactively

liked this one best, since the algorithm allows to output a measure for the certainty of it's results. so maps with uncertain lanes could be flagged for review.



problems and shortcommings of the current auto-balance (in no particular order):
A - players don't get to decide if they're ok with the teams
B - lane balance is not regarded
C - players don't get to choose the lanes they want to play in
D - players that want to play together can't


i tried to design the ui to give the tools to solve those problems.
A - results are shown after deactivating balance mode and before game start
C - "Pref. 1&2" would be the preferred lane and the second choice lane
D - players in the same squads would always get into the same team.

the algorithm itself would then pick the game that has the highest team balance, lane balance, match to preferences (and respects squads). the relative importance of those 3 criterions would be set by the host (in the settings).

lane balance is surely a shortcomming that needs to be addressed, but i think that solving that problem without solving A, C and D would keep autobalance relatively useless. As for a starting point for my work, lane balance/definitions does have the advantage that it can stand alone.. i still lean more thowards the ui as for me it is the hardest part (want to know that it can be done).

[Uveso]

hello cyrili,

welcome to FAForever

I like your new "mod". Could be a real enhancement to the game.

If you need some help with adding options, or how translation works, just ask me

[cyrili]

update:

ui is mostly working.

here is the lane deduction function (only for even player count and 2 teams):

Spoiler: show

Code: Select all

--get teams and lanes from occupied slot coordinates and write them into gameInfo.PlayerOptions
function BalanceGetLanes()
    slot = {}      --array of occupied slots with their data
    slotCount = 0   --nr of occupied slots
   
   --get slot information of occupied slots
    map = GUI.mapView
   for i=1, numOpenSlots do --for all slots
        if not gameInfo.ClosedSlots[i] and gameInfo.PlayerOptions[i] then --if a player occupies the slot
            slotCount = slotCount+1                     --count up slot count
            slot[slotCount] = {id=1, x=0, y=0, angle=0}    --init slot info array
         slot[slotCount].id = i                      --slot id from PlayerOptions
            slot[slotCount].x = ((map.startPositions[i].Left()-map.Left()) / map.Width()) - 0.5      --x starting position normalized to -0.5 to 0.5
            slot[slotCount].y = -1*(((map.startPositions[i].Top()-map.Top()) / map.Height()) - 0.5)   --y starting position
            slot[slotCount].angle = math.atan2(slot[slotCount].y, slot[slotCount].x)            --angle from positive x axis (-pi to pi)
        end
    end
   
   --bubblesort slot list in ascending angle order
    for i=slotCount,1,-1 do      
        for j=1,slotCount-1 do
            if (slot[j].angle > slot[j+1].angle) then
                slot[j], slot[j+1] = slot[j+1], slot[j]
            end
        end
    end
   
   --get team division with the smallest possible angle containing the teams
    teamAperture = math.pi   --stores the smallest sum of the 2 angle containing the teams individually
    teamStart = 0         --stores first player of team 1. all others are deduced by going trough the slots counterclockwise
   mirrorAngle = 0         --angle defining the war-front
    for i=1, slotCount/2 do
      corner = {(i), (i+slotCount/2-1), (i+slotCount/2), (i+slotCount-1)}   --list of corner slots enclosing the whole team. [1][2] for team1 [3][4] for team2
      for j,v in ipairs(corner) do if v > slotCount then corner[j] = v - slotCount end end   --fix possible index overflow from above calculation
      
      apertureA = math.abs(slot[corner[1]].angle-slot[corner[2]].angle)    --team1 aperture
      if apertureA > math.pi then apertureA = 2*math.pi-apertureA end      --fix angle if team contains -pi,+pi jump
      apertureB = math.abs(slot[corner[3]].angle-slot[corner[4]].angle)    --team2 aperture
      if apertureB > math.pi then apertureB = 2*math.pi-apertureB   end      --fix angle if team contains -pi,+pi jump
      
      if apertureA+apertureB < teamAperture then   --if aperture is smaller than smallest aperture found untill now
         teamAperture = apertureA+apertureB   --save aperture as smalles found to this point
         mirrorAngle = ( (slot[corner[1]].angle+apertureA/2+math.pi/2) + (slot[corner[3]].angle+apertureB/2-math.pi/2) ) /2 -- war-front angle
         teamStart = i   --save team1 starting point
        end
    end

   --shift slot table as to make team1 starting point first index
   for i = 1, teamStart-1 do   
      table.insert( slot, slotCount+1, slot[1] )
      table.remove( slot, 1 )
   end
   --rotate slots by mirrorAngle so that the war-front lies on the x-axis, team 1 in -y and team 2 in +y
   cosMirrorAngle = math.cos(-1*mirrorAngle)
    sinMirrorAngle = math.sin(-1*mirrorAngle)
    for i=1, numOpenSlots do
        tempx = cosMirrorAngle*slot[i].x - sinMirrorAngle*slot[i].y
        tempy = sinMirrorAngle*slot[i].x + cosMirrorAngle*slot[i].y
        slot[i].x, slot[i].y = tempx, tempy
    end
   --mirror team 2 positions over x-axis to team 1
   for i=slotCount/2+1, slotCount do
      slot[i].y = -1*slot[i].y
      slot[i].angle = math.atan2(slot[i].y, slot[i].x)
   end
   --reverse team 2 positions order
   for i=1, math.floor(slotCount/4) do
      slot[i+slotCount/2], slot[slotCount+1-i] = slot[slotCount+1-i], slot[i+slotCount/2]
   end
   
   --fix errors where 2 slots have similar angles (usually enough since angle sort is a good approximation)
   for i=slotCount/2+1, slotCount-1 do
      distAA = math.sqrt((slot[i].x-slot[i-slotCount/2].x)*(slot[i].x-slot[i-slotCount/2].x)+(slot[i].y-slot[i-slotCount/2].y)*(slot[i].y-slot[i-slotCount/2].y))               --distance between slot[i] and slot[i]'s opponent
      distAB = math.sqrt((slot[i+1].x-slot[i+1-slotCount/2].x)*(slot[i+1].x-slot[i+1-slotCount/2].x)+(slot[i+1].y-slot[i+1-slotCount/2].y)*(slot[i+1].y-slot[i+1-slotCount/2].y)) --distance between slot[i+1] and slot[i+1]'s opponent
      distBA = math.sqrt((slot[i].x-slot[i+1-slotCount/2].x)*(slot[i].x-slot[i+1-slotCount/2].x)+(slot[i].y-slot[i+1-slotCount/2].y)*(slot[i].y-slot[i+1-slotCount/2].y))         --distance between slot[i] and slot[i+1]'s opponent
      distBB = math.sqrt((slot[i+1].x-slot[i-slotCount/2].x)*(slot[i+1].x-slot[i-slotCount/2].x)+(slot[i+1].y-slot[i-slotCount/2].y)*(slot[i+1].y-slot[i-slotCount/2].y))         --distance between slot[i+1] and slot[i]'s opponent
      if distAA+distAB > distBA+distBB then   --if swapping slot[i] and slot[i+1] would shorten the sum of distances between them and their opponents
         slot[i], slot[i+1] = slot[i+1], slot[i]   --swap
      end
   end
   
   --save results
   for i=1, slotCount do
      if (i <= slotCount/2) then
         gameInfo.PlayerOptions[slot[i].id].Team = 3
         gameInfo.PlayerOptions[slot[i].id].laneNumber = i
      else
         gameInfo.PlayerOptions[slot[i].id].Team = 2
         gameInfo.PlayerOptions[slot[i].id].laneNumber = i-slotCount/2
      end
   end

end


i'll leave it here since i'm going to have even less time to code in the near future and it could take quite a while before i make progress (sincerely prefer playing the game in the free time i have)

*edit*
@uvesto, thanks for the offer. think i mostly figured it out though.

[chainingsolid]

So I found this thread checking to see if this had been done before, and its looks half done so I'd like to help. So where do I go to help/whos in charge of this?(aka who do I bother with questions) I'm mainly looking for the already written code (which I couldn't find in the faf github, or in a fork of it) and a list of requirements for the auto team balancing feature. I already know how to code. Would also consider writing this from scratch if I have to (aka already written code can't be found).