Bugged insertion sort

07-17-2004, 03:58 PM

I asked about this problem on the battle.net map development forum and was generally told "don't do it that way", however, I'm interested in figuring out what's wrong with this code, whether or not it's the method for solving the problem that you would choose.

This is supposed to be a fairly simple and direct insertion sorter for a multiboard, to put the player with the most kills on top, followed by second most, etc.

A helpful member on the battle.net forums pointed out that the BJ multiboard update triggers are cumbersome, so I made lightened versions which are posted after the trigger.

The symptom of the sorter is that it seems to assign kills that should go to the killing unit's owner to other players near him on the multiboard instead. Even still, it doesn't order according to those mis-assigned values. It does change the order, but I haven't been able to figure out what the order change pattern is.

Here it is:

Code:

// udg_mboardKills : the multiboard
// udg_intMbHeight: integer, the size of the multiboard (except the neutral players, who aren't sorted).
// udg_intArKillsUnit: integer array, udg_intArKillsUnit[player number] == number of unit kills for that player.
// udg_intArKillsHero: integer array, udg_intArKillsHero[player number] == number of hero kills for that player.  Does not affect sorting.
// udg_intArPurg: integer array, udg_intArPurg[player number] == amount of time in seconds remaining before that player's hero is revived.  Tracked outside this trigger.
// udg_intArMbRow: integer array, udg_intArMbRow[player number] == row of the multiboard that the player is assigned to.  Starts at 2 for the first player initially. 0 for player slots that aren't playing.
// udg_realArRed, udg_realArGreen, udg_realArBlue: real arrays, udg_realArRed[player number] == amount of red in the player's multiboard name text, blue, green

function Trig_Multiboard_update_Conditions takes nothing returns boolean
    if (IsUnitType(GetDyingUnit(), UNIT_TYPE_STRUCTURE) == true) then
        return false
    endif
    if (not(IsPlayerInForce(GetOwningPlayer(GetKillingUnitBJ()), GetPlayersAllies(GetOwningPlayer(GetDyingUnit()))) == false)) then
        return false
    endif
    if ((GetOwningPlayer(GetKillingUnitBJ()) == Player(bj_PLAYER_NEUTRAL_VICTIM)) or (GetOwningPlayer(GetKillingUnitBJ()) == Player(PLAYER_NEUTRAL_PASSIVE))) then
        return false
    endif
    if (GetKillingUnitBJ() == null) then
        return false
    endif
    return true
endfunction

function Trig_Multiboard_update_Actions takes nothing returns nothing
    local integer i = 0 //test index
    local integer j = 0 //first un-sorted index
    local integer intRowKey
    local integer intKillKey //temp storage of value of index
    local integer intLoop
    local integer intLoopPlayer
    local integer array intArPlayers

    // set new values
    if (IsUnitType(GetDyingUnit(), UNIT_TYPE_HERO) == true) then
        set udg_intArKillsHero[GetConvertedPlayerId(GetOwningPlayer(GetKillingUnitBJ()))] = (udg_intArKillsHero[GetConvertedPlayerId(GetOwningPlayer(GetKillingUnitBJ()))] + 1)
    else
        set udg_intArKillsUnit[GetConvertedPlayerId(GetOwningPlayer(GetKillingUnitBJ()))] = (udg_intArKillsUnit[GetConvertedPlayerId(GetOwningPlayer(GetKillingUnitBJ()))] + 1)
    endif

    // creating player array
    set intLoop = 1
    set intLoopPlayer = 0
    loop
        exitwhen intLoop > 12
        if (udg_intArMbRow[intLoop] > 0) then
            set intArPlayers[udg_intArMbRow[intLoop]] = intLoop
//            call DisplayTextToForce(GetPlayersAll(), "Player "+I2S(intLoop)+" is index "+I2S(udg_intArMbRow[intLoop]))
        endif
        set intLoop = intLoop + 1
    endloop 

    // insertion sort
    // sort by udg_intArKillsUnit but set udg_intArMbRow
    // the array values start at 2 because row 1 is column headers
    set j = 3
    loop
        exitwhen j > udg_intMbHeight
        call DisplayTextToForce(GetPlayersAll(), "j is "+I2S(j))
        set intKillKey = udg_intArKillsUnit[intArPlayers[j]]
        set intRowKey = udg_intArMbRow[intArPlayers[j]]
        set i = j - 1
        loop
            exitwhen i <= 1 or udg_intArKillsUnit[intArPlayers[i]] >= intKillKey
            call DisplayTextToForce(GetPlayersAll(), "i is "+I2S(i))
            set udg_intArMbRow[intArPlayers[i + 1]] = udg_intArMbRow[intArPlayers[i]]
            call DisplayTextToForce(GetPlayersAll(), "udg_intArMbRow["+I2S(i)+"] is "+I2S(udg_intArMbRow[i]))
            set udg_intArKillsUnit[intArPlayers[i + 1]] = udg_intArKillsUnit[intArPlayers[i]]
            call DisplayTextToForce(GetPlayersAll(), "udg_intArKillsUnit["+I2S(i)+"] is "+I2S(udg_intArKillsUnit[i]))
            set i = i - 1
        endloop
        call DisplayTextToForce(GetPlayersAll(), "intKillKey is "+I2S(intKillKey))
        call DisplayTextToForce(GetPlayersAll(), "intRowKey is "+I2S(intRowKey))
        set udg_intArKillsUnit[intArPlayers[i + 1]] = intKillKey
        set udg_intArMbRow[intArPlayers[i + 1]] = intRowKey
        set j = j + 1
    endloop

    // update multiboard
    set intLoop = 1
    loop
        exitwhen intLoop > 12

        // debug udg_intArMbRow; yep, it seems to be set to nonzero.
//        call DisplayTextToForce(GetPlayersAll(), "udg_intArMbRow["+I2S(intLoop)+"] = "+I2S(udg_intArMbRow[intLoop]))

        if (udg_intArMbRow[intLoop] != 0) then
            call SetGoddamnCellValue(udg_mboardKills, 1, udg_intArMbRow[intLoop], GetPlayerName(ConvertedPlayer(intLoop)))
            call SetGoddamnCellColor(udg_mboardKills, 1, udg_intArMbRow[intLoop], udg_realArRed[intLoop], udg_realArGreen[intLoop], udg_realArBlue[intLoop], 0)
            call SetGoddamnCellValue(udg_mboardKills, 2, udg_intArMbRow[intLoop], I2S(udg_intArKillsUnit[intLoop]))
            call SetGoddamnCellValue(udg_mboardKills, 3, udg_intArMbRow[intLoop], I2S(udg_intArKillsHero[intLoop]))
            if (udg_intArPurg[intLoop] > 0) then
                call SetGoddamnCellValue(udg_mboardKills, 4, udg_intArMbRow[intLoop], I2S(udg_intArPurg[intLoop]))
            else
                call SetGoddamnCellValue(udg_mboardKills, 4, udg_intArMbRow[intLoop], "N/A")            
            endif
        endif
        set intLoop = intLoop + 1
    endloop

endfunction

//===========================================================================
function InitTrig_Multiboard_update takes nothing returns nothing
    set gg_trg_Multiboard_update = CreateTrigger(  )
    call DisableTrigger( gg_trg_Multiboard_update )
    call TriggerRegisterAnyUnitEventBJ( gg_trg_Multiboard_update, EVENT_PLAYER_UNIT_DEATH )
    call TriggerAddCondition( gg_trg_Multiboard_update, Condition( function Trig_Multiboard_update_Conditions ) )
    call TriggerAddAction( gg_trg_Multiboard_update, function Trig_Multiboard_update_Actions )
endfunction

Here's the lightened multiboard update triggers:

Code:

function SetGoddamnCellValue takes multiboard mb, integer intColumn, integer intRow, string stringValue returns nothing
    local multiboarditem mbitemCell = MultiboardGetItem(mb, intRow-1, intColumn-1)
    call MultiboardSetItemValue(mbitemCell, stringValue)
    call MultiboardReleaseItem(mbitemCell)
endfunction

function SetGoddamnCellColor takes multiboard mb, integer intColumn, integer intRow, real realRed, real realGreen, real realBlue, real realAlpha returns nothing
    local multiboarditem mbitemCell = MultiboardGetItem(mb, intRow-1, intColumn-1)
    call MultiboardSetItemValueColor(mbitemCell, PercentTo255(realRed), PercentTo255(realGreen), PercentTo255(realBlue), PercentTo255(100.0-realAlpha))
    call MultiboardReleaseItem(mbitemCell)
endfunction

07-17-2004, 08:00 PM

R3N3G4D3

Maybe I'm missing something but here are the 2 things I don't get. First, you said your intArPlayers starts in cell 2 (not cell 0 or 1), if so, then it looks like "creating player array" part sets intArPlayers[] to {2,3,4,5,6,7,8,9,10,11,12}. Also, jass starts players from 0, so player 1 is called player 0 in jass, doesn't that mean that your function only starts with player 3? Or are the first 2 players used for npcs? And the 2nd thing I don't get is in your sort, when you move stuff down, the way you do it, doesn't that overwrite data in the cell below the one you're looking at with the data from the cell you're looking at? Shouldn't you switch the 2 cell datas like this: set temp=a[i+1], set a[i+1]=a[i], set a[i]=temp?