Custom Formations 2

TheFatController · Post by **TheFatController** » 03 Jul 2009, 01:22

Update on the bug

You can recreate this every time by starting spring.exe with Empty script and /cheat /give 38 corthud. Draw some lines with all selected and it'll crash very fast.

The issue seems to be in step 2. (as per the comments in the code), it looks like in the old spring none of this code was run at all so its probably always been buggy (ie it makes assumptions like that SearchNewNextNodes will certainly populate the next node when it wont etc. and via Echo i've never seen a call to SearchNewNextNodes not result in a crash...).

I can't find the fix in this step, short of rewriting it which I may do if noones fixed it before next BA (which will be as soon as the engine is updated to fix featurebuildstep...)

Argh · Post by **Argh** » 03 Jul 2009, 01:29

Ah! Somebody else found where the bug is

Shall I give everybody orkishly fixed source that doesn't use "optimized" at all? Yes, I shall! Enjoy.

Code: Select all

-- $Id: unit_customformations.lua 3016 2008-10-12 17:13:19Z jk $
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--
--  Copyright (C) 2008.
--  Licensed under the terms of the GNU GPL, v2 or later.
--
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

function widget:GetInfo()
  return {
    name      = "CustomFormations",
    desc      = "Allows you to draw your own formation line.",
    author    = "jK (Hungarian code written by gunblob), temporary fix by Argh",
    version   = "2.2",
    date      = "Jan, 2008",
    license   = "GNU GPL, v2 or later",
    layer     = 10000,
    enabled   = true,
    handler   = true,
  }
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

--// user configurable
local maxHungarianUnits         = 19
local maxOptimizationUnits      = 75  --// above it will use the random algo
local maxOptimizationIterations = 600 --// break the optimization after a limited iterations and distribute the remaining units on free nodes

local desiredSFP = 1/20 --// the optimization shouldn't take longer than 1/20 seconds (else decrease the maxUnits for that algo)

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

local gl      = gl
local Spring  = Spring
local GiveOrderToUnit   = Spring.GiveOrderToUnit
local spGetUnitPosition = Spring.GetUnitPosition
local spGetCommandQueue = Spring.GetCommandQueue
local spGetMiniMapGeometry = (Spring.GetMiniMapGeometry or Spring.GetMouseMiniMapState)
local tinsert = table.insert
local tremove = table.remove
local rand    = math.random
local sqrt    = math.sqrt
local abs     = math.abs
local min     = math.min
local floor   = math.floor
local ceil    = math.ceil

local formationNodes = {}
local totaldxy = 0  --// moved mouse distance

local dimmNodes = {}
local alphaDimm = 1

local inMinimap = false

local endShift = false
local activeCmdIndex = -1
local cmdTag = CMD.MOVE
local inButtonEvent = false  --//if you click the command menu the move/fight command is handled with left click instead of right one

local invertQueueKey = (Spring.GetConfigInt("InvertQueueKey", 0) == 1)

local CMD_JUMP = 38521

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-- Minimap functions

local function InMinimap(x,y)
  local posx,posy,sizex,sizey,minimized,maximized = spGetMiniMapGeometry()
  local rx,ry = (x-posx)/sizex,(y-posy)/sizey
  return (not (minimized or maximized)) and
         (rx>=0)and(rx<=1)and
         (ry>=0)and(ry<=1),rx,ry
end

local function MinimapToWorld(rx,ry)
  if (rx>=0)and(rx<=1)and
     (ry>=0)and(ry<=1)
  then
    local mapx,mapz = Game.mapSizeX*rx,Game.mapSizeZ-Game.mapSizeZ*ry
    local mapy = Spring.GetGroundHeight(mapx,mapz)
    return {mapx,mapy,mapz}
  else
    return {-1,-1,-1}
  end
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

local moveCmds = {
  [CMD.MOVE]=true,  [CMD.ATTACK]=true, [CMD.RECLAIM]=true,[CMD.RESTORE]=true,[CMD.RESURRECT]=true,
  [CMD.PATROL]=true,[CMD.CAPTURE]=true,[CMD.FIGHT]=true,  [CMD.DGUN]=true, [CMD_JUMP]=true,
}

function GetUnitPosition(unitID)
  local x,y,z = spGetUnitPosition(unitID)

  local cmds = spGetCommandQueue(unitID)
  if (cmds)and(cmds[1]) then
    for i=1,#cmds do
      local cmd = cmds[i]
      if (moveCmds[cmd.id])and(cmd.params[3]) then
        local params = cmd.params
        x,y,z = params[1],params[2],params[3]
      end
    end
  end

  return x,y,z
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

function widget:MousePress(x, y, button)
  local activeid
  endShift = false
  activeCmdIndex,activeid = Spring.GetActiveCommand()
  inButtonEvent = (activeid) and ((activeid==CMD.PATROL) or (activeid==CMD.FIGHT) or (activeid==CMD.MOVE) or (activeid==CMD_JUMP)) and (button==1)

  if (inButtonEvent) or ((activeid==nil)and(button==3)) then

    local selcnt = Spring.GetSelectedUnitsCount()
    if (selcnt>1) then

      local _,defid    = Spring.GetDefaultCommand()
      cmdTag = activeid or defid   --// CMD.MOVE or CMD.FIGHT

      if (defid==CMD.MOVE) or (inButtonEvent) then
        local units = Spring.GetSelectedUnits()
        units.n = nil

        --// check if there are moveable units selected
        local moveableUnits = false
        for _,unitID in pairs(units) do
          local unitDefID = Spring.GetUnitDefID(unitID)
          if (UnitDefs[unitDefID].canMove) then moveableUnits = true; break; end
        end

        if (moveableUnits) then
          local rx,ry, pos
          inMinimap,rx,ry = InMinimap(x,y)
          if inMinimap then
            pos = MinimapToWorld(rx,ry)
          else
            _,pos = Spring.TraceScreenRay(x,y,true)
          end

          if (pos) then
            widgetHandler:UpdateWidgetCallIn("DrawInMiniMap", self)
            widgetHandler:UpdateWidgetCallIn("DrawWorld", self)
            table.insert(formationNodes,pos)
            totaldxy = 0
            return true
          end
        end

      end
    end
  end

  return false
end


function widget:MouseMove(x, y, dx, dy, button)
  if ((inButtonEvent)and(button==3)) or
     ((not inButtonEvent)and(button~=3))
  then
    return false
  end

  if (#formationNodes>0) then
    if (totaldxy>40) then
      if (inMinimap) then
        local inMinimap,rx,ry = InMinimap(x,y)
        if inMinimap then
          table.insert(formationNodes,MinimapToWorld(rx,ry))
          totaldxy = 0
        end
      else
        local _,pos = Spring.TraceScreenRay(x,y,true)
        if (pos) then
          table.insert(formationNodes,pos)
          totaldxy = 0
        end
      end
    end

    if (inMinimap) then
      local _,_,sizex,sizey = spGetMiniMapGeometry()
      totaldxy = totaldxy + (dx*dx)*1024/sizex + (dy*dy)*1024/sizey
    else
      totaldxy = totaldxy + (dx*dx) + (dy*dy)
    end
  end

  return false
end


function widget:MouseRelease(x, y, button)
  --// create modkeystate list
  --// (keyState is for GiveOrder and keyState2 is for CommandNotify)
  local alt, ctrl, meta, shift = Spring.GetModKeyState()
  if (Spring.GetInvertQueueKey()) then
    shift = not shift
    -- check for immediate mode mouse 'rocker' gestures
    local x, y, b1, b2, b3 = Spring.GetMouseState()
    if (((button == 1) and b3) or
        ((button == 3) and b1)) then
      shift = false
    end
  end
  local keyState,keyState2 = {},{coded=0,alt=false,ctrl=false,shift=false,right=false}
  if alt   then table.insert(keyState,"alt");   keyState2.alt =true;  end
  if ctrl  then table.insert(keyState,"ctrl");  keyState2.ctrl=true;  end
  if meta  then table.insert(keyState,"meta")                         end
  if shift then table.insert(keyState,"shift"); keyState2.shift=true  end
  if (not inButtonEvent) then                   keyState2.right=true; end

  --// calc the "coded" number of keyState2
  if keyState2.alt   then keyState2.coded = keyState2.coded + CMD.OPT_ALT   end
  if keyState2.ctrl  then keyState2.coded = keyState2.coded + CMD.OPT_CTRL  end
  if keyState2.shift then keyState2.coded = keyState2.coded + CMD.OPT_SHIFT end
  if keyState2.right then keyState2.coded = keyState2.coded + CMD.OPT_RIGHT end

  --// end button event (user clicked command menu)
  if (inButtonEvent) then
    Spring.SetActiveCommand(-1)
  end

  --// single click? (no line drawn)
  if (#formationNodes==1) then

    --// check if some widgets want to stop the command
    local retval = widgetHandler:CommandNotify(cmdTag, formationNodes[1], keyState2) or false
    if (retval) then
      formationNodes = {}
      return -1
    end

    Spring.GiveOrder(cmdTag, formationNodes[1], keyState)
    formationNodes = {}
    if (keyState2.shift)and(activeCmdIndex>-1) then
      endShift = true
      return activeCmdIndex
    end
    return -1
  end

  --// spread units out
  if (#formationNodes>0) then
    if inMinimap then
      local inMinimap,rx,ry = InMinimap(x,y)
      if inMinimap then
        table.insert(formationNodes,MinimapToWorld(rx,ry))
      end
    else
      local _,pos = Spring.TraceScreenRay(x,y,true)
      if (pos) then
        table.insert(formationNodes,pos)
        totaldxy = 0
      end
    end

    local units  = Spring.GetSelectedUnitsSorted()
    units.n = nil

    --// count moveable units
    local selectedMobileUnits = {}
    local movunits = 0
    for unitDefID,unitIDs in pairs(units) do
      if (UnitDefs[unitDefID].canMove) then
        movunits = movunits + #unitIDs
        for i=1,#unitIDs do
          tinsert(selectedMobileUnits,unitIDs[i])
        end
      end
    end

    if (movunits>0) then
      local interNodes = GetInterpolatedNodes(formationNodes,movunits)

      if (not keyState2.alt)and(#selectedMobileUnits<maxOptimizationUnits) then
        if (#selectedMobileUnits<maxHungarianUnits) then
          SendOrdersHungarian(interNodes,selectedMobileUnits,keyState)
        else
          SendOrdersRandom(interNodes,selectedMobileUnits,keyState)
        end
      else
        SendOrdersRandom(interNodes,selectedMobileUnits,keyState)
      end
    end

    dimmNodes = formationNodes
    alphaDimm = 1
    formationNodes = {}

    if (keyState2.shift)and(activeCmdIndex>-1) then
      endShift = true
      return activeCmdIndex
    end
  end

  return -1
end


function widget:KeyRelease(key)
  if (key==304)and(endShift) then
    endShift = false
    Spring.SetActiveCommand(-1)
    return true
  end
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

local glVertex = gl.Vertex
local glLineStipple = gl.LineStipple
local glLineWidth   = gl.LineWidth
local glColor       = gl.Color
local glBeginEnd    = gl.BeginEnd
local GL_LINE_STRIP = GL.LINE_STRIP

local DrawFormationLine = function(dimmNodes)
  for _,v in pairs(dimmNodes) do
    glVertex(v[1],v[2],v[3])
  end
end

local DrawMinimapFormationLine = function(dimmNodes)
  for _,v in pairs(dimmNodes) do
    glVertex(v[1],v[3],1)
  end
end

function widget:DrawWorld()
  if (#formationNodes<1)and(#dimmNodes<1) then
    widgetHandler:RemoveWidgetCallIn("DrawWorld", self)
    return
  end

  --// draw the lines
  glLineStipple(2, 4095)
  glLineWidth(2.0)

  if (cmdTag==CMD.MOVE)
    then glColor(0.5,1,0.5)
    else glColor(0.5,0.5,1) end

  glBeginEnd(GL_LINE_STRIP, DrawFormationLine, formationNodes)

  if (#dimmNodes>1) then
    if (cmdTag==CMD.MOVE)
      then glColor(0.5,1,0.5,alphaDimm)
      else glColor(0.5,0.5,1,alphaDimm) end

    glBeginEnd(GL_LINE_STRIP, DrawFormationLine, dimmNodes)
    alphaDimm = alphaDimm - 0.03
    if (alphaDimm<=0) then dimmNodes = {} end
  end

  glColor(1,1,1,1)
  glLineWidth(1.0)
  glLineStipple(false)
end


function widget:DrawInMiniMap()
  if (#formationNodes<1)and(#dimmNodes<1) then
    widgetHandler:RemoveWidgetCallIn("DrawInMiniMap", self)
    return
  end

  --// draw the lines
  glLineStipple(1, 4095)
  glLineWidth(2.0)

  if (cmdTag==CMD.MOVE)
    then glColor(0.5,1,0.5)
    else glColor(0.5,0.5,1) end

  gl.PushMatrix()
  gl.LoadIdentity()
  gl.Translate(0,1,0)
  gl.Scale(1/Game.mapSizeX,-1/Game.mapSizeZ,1)

  glBeginEnd(GL_LINE_STRIP, DrawMinimapFormationLine, formationNodes)

  if (#dimmNodes>1) then
    if (cmdTag==CMD.MOVE)
      then glColor(0.5,1,0.5,alphaDimm)
      else glColor(0.5,0.5,1,alphaDimm) end

    glBeginEnd(GL_LINE_STRIP, DrawMinimapFormationLine, dimmNodes)
    alphaDimm = alphaDimm - 0.03
    if (alphaDimm<=0) then dimmNodes = {} end
  end

  gl.PopMatrix()

  glColor(1,1,1,1)
  glLineWidth(1.0)
  glLineStipple(false)
end




---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
----   ┬½Interpolate drawn line nodes┬╗                                                                ----
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------

function GetInterpolatedNodes(nodes,totalUnits)
  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- detect formation line length

  local length = 0
  for i=2,#nodes do
    local lv = nodes[i-1]
    local v  = nodes[i]
    local dlx,dlz = lv[1]-v[1],lv[3]-v[3]
    length = length + sqrt( dlx*dlx + dlz*dlz )
  end

  local unitdist = length / (totalUnits-1)   --// movunits == 1 -> x/0 -> math.huge  , no segm ;)
  local idx,idxLength = 1,0
  local interpolatedNodes = {nodes[1]}

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- determine unit positions on the line

  repeat
    for i=idx+1,#nodes+1 do
      if (i>#nodes) then
        idx = #nodes
        if (#interpolatedNodes<totalUnits) then
          tinsert(interpolatedNodes,nodes[idx])
        end
        break
      end
      local lv = nodes[i-1]
      local v  = nodes[i]
      local dlx,dly,dlz = lv[1]-v[1], lv[2]-v[2], lv[3]-v[3]
      local dl = sqrt( dlx*dlx + dlz*dlz )
      local bfr_idxLength = idxLength + dl

      local rel_dist = unitdist-bfr_idxLength

      if (rel_dist==0) then
        idxLength = 0
        idx = i
        tinsert(interpolatedNodes,nodes[i])
        break
      end
      if (rel_dist<0) then
        local fracLength = unitdist - idxLength
        local frac = fracLength/dl

        --// add an in-between node
        local inBetween = {lv[1]-frac*dlx, lv[2]-frac*dly, lv[3]-frac*dlz}
        tinsert(nodes,i,inBetween)

        idxLength = 0
        idx = i
        tinsert(interpolatedNodes,inBetween)
        break
      end

      idxLength = bfr_idxLength
    end
  until (idx >= #nodes)

  return interpolatedNodes
end --// end function GetInterpolatedNodes()






---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
----   ┬½Different Linear Optimization Algorithms┬╗                                                    ----
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
-- following algos:
--
--  SendOrdersRandom()
--  SendOrdersOptimized()
--  SendOrdersHungarian()
--

function SendOrdersRandom(nodes,units,keyState)
  ----------------------------------------------------------------------
  ----------------------------------------------------------------------
  -- the next code doesn't do any optimization at all,
  -- it simply gives each unit a random waypoint
  ----------------------------------------------------------------------
  ----------------------------------------------------------------------

  --// send orders
  for n=1,#nodes do
    local m = rand(1,#units)
    local unitID = units[m]
    local pos  = nodes[n]
    GiveOrderToUnit(unitID, cmdTag, pos, keyState)
    tremove(units,m)
  end
end --// end function SendOrdersRandom()



function SendOrdersOptimized(nodes,units,keyState)
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------
  -- the next code tries to optimize the total movement length (not optimal, but fast)
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------

  --// (tip: from now on "i" should index an unit var and "n" a formation node var)

  local t = os.clock()

  --// cache unit positions
  for i=1,#units do
    local unitID = units[i]
    units[i]={id=unitID, pos={GetUnitPosition(unitID)}}
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- 1. make array with all desired unit positions and
  --    add each unit to its nearest node

  local formationsNodesN = #nodes
  local sortFormation = {}
  for n=1,#nodes do sortFormation[n] = {} end

  for i=1,#units do
    local unit  = units[i]
    local ux,uz = unit.pos[1],unit.pos[3]
    local dist  = math.huge
    local nearest_n = -1
    unit.dists = {}
    for n=1,#nodes do
      local nn      = n*0.5
      if (n%2<1) then nn=ceil(nn) else nn=formationsNodesN-floor(nn) end --// this is faster!!!
      local pos     = nodes[nn]
      local px,pz   = pos[1],pos[3]
      local dlx,dlz = px-ux,pz-uz
      local dl      = sqrt(dlx*dlx + dlz*dlz)
      for m=1,min(#(unit.dists)+1,30) do --// save the 30 best nodes for this unit
        if (not unit.dists[m])or(unit.dists[m].dist>dl) then
          tinsert( unit.dists , m, {n=nn,dist=dl})
          break
        end
      end
    end
    for m=31,#(unit.dists) do
      tremove( unit.dists , m)
    end
    unit.n = 1
    tinsert( sortFormation[unit.dists[1].n] , unit)
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- some desired unit positions are now double (or more) used, so ..
  -- 2. try to optimize the formation (try to reduce the overall walk distances)

  local SearchNewNextNodes = function(unit)
    --// unit = { pos={vec3}, n=used_dists_n, dists={[1]={n=int,dist=float} }
    local currentDist,distsN = unit.dists[unit.n].dist,#(unit.dists)
    local maxNodes = distsN+30
    local ux,uz = unit.pos[1],unit.pos[3]
    for n=1,#nodes do
      local nn      = n*0.5; if (n%2<1) then nn=ceil(nn) else nn=formationsNodesN-floor(nn) end --// this is faster!!!
      local pos     = nodes[nn]; local px,pz = pos[1],pos[3]; local dlx,dlz = px-ux,pz-uz; local dl = sqrt(dlx*dlx + dlz*dlz)
      for m=1,min(#(unit.dists)+1,maxNodes) do --// save the 30 best nodes for this unit
        if ((not unit.dists[m])or(unit.dists[m].dist>dl))and(dl>currentDist) then
          tinsert( unit.dists , m, {n=nn,dist=dl}); break
        end
      end
    end
    for m=maxNodes+1,#(unit.dists) do
      tremove( unit.dists , m)
    end
  end

  local max_repeat,idx = maxOptimizationIterations
  repeat
    idx=0
    --// find next multi used node
    for n=1,#sortFormation do
      local nn = 0
      if (max_repeat%2<1) then nn=math.ceil(n*0.5) else nn=#sortFormation-math.floor(n*0.5) end
      if (#(sortFormation[n])>1) then
        idx=n
        break
      end
    end
    --// try to solve the multi usage
    if (idx>0) then
      local v = sortFormation[idx]

      --// determine which unit would suffer at least, if it takes another node
      local worst_dist = 0
      local ignore = 1 --// this is the unit, which should stay on that node
      for i=1,#v do
        local unit      = v[i]
        local next_node = unit.dists[unit.n+1]
        if (not next_node) then
          SearchNewNextNodes(unit)
          next_node = unit.dists[unit.n+1]
        end
        if (next_node)and(next_node.dist>worst_dist) then
          worst_dist = next_node.dist
          ignore     = i
        end
      end

      --// move all units to their >next< best node, except one
      for i=1,#v do
        if (i~=ignore) then
          local unit      = v[i]
          unit.n          = unit.n+1
          local next_node = unit.dists[unit.n]
          if next_node ~= nil and next_node[1] ~= nil then
          	tinsert(sortFormation[next_node.n],unit)
          end
        end
      end

      --// clean node unit list, so only 1 units stays there
      sortFormation[idx] = {v[ignore]}
    end
    max_repeat = max_repeat - 1
  until (idx==0)or(max_repeat<0)

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- 'cus we cut the optimize loop after some passes (->max_repeat),
  --  we can't be 100% that there aren't any multi usages left.
  --  so we solve the rest with a not optimized algo

  local freeNodes = {}
  for n=1,#sortFormation do
    if (#sortFormation[n]==0) then
      tinsert(freeNodes,n)
    end
  end
  local freeNodesN = #freeNodes
  for n=1,#sortFormation do
    if (#sortFormation[n]>1) then
      local beforeN = #sortFormation[n]
      for m=#sortFormation[n],2,-1 do
        tinsert(sortFormation[ freeNodes[freeNodesN] ],sortFormation[n][m])
        tremove(sortFormation[n],m)
        freeNodesN = freeNodesN -1
      end
    end
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- send orders

  for n=1,#sortFormation do
    local unit = sortFormation[n][1]
    local pos  = nodes[n]
    if unit[1] ~= nil then
      GiveOrderToUnit(unit.id, cmdTag, pos, keyState)
    end
  end


  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- determine needed time and optimize the maxUnits limit

  if (rand(0,2)==2) then
    local delay = os.clock()-t
    if (delay>desiredSFP) then
      maxOptimizationUnits=maxOptimizationUnits-1
    elseif (delay<(desiredSFP*0.8))and(#units>maxOptimizationUnits*0.95) then
      maxOptimizationUnits=maxOptimizationUnits+1
    end
  end
end --// end function SendOrdersOptimized()




function SendOrdersHungarian(nodes,units,keyState)
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------
  -- (the following code is written by gunblob)
  --   this code finds the optimal solution (slow, but effective!)
  --   it uses the hungarian algorithm from http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html
  --   if this violates gpl license please let gunblob and me know
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------
  local t = os.clock()

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- cache node<->unit distances

  local distances = {}
  for n=1,#nodes do distances[n]={} end

  for i=1,#units do
    local unitID = units[i]
    local thisDistances = {}
    local ux, _, uz = GetUnitPosition(unitID)
    for n=1,#nodes do
      local nodePos   = nodes[n]
      local dx,dz     = (nodePos[1]-ux),(nodePos[3]-uz)
      distances[n][i] = dx*dx+dz*dz
    end
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- find optimal solution and send orders

  local result = findHungarian(distances)
  for j=1,#result do
    local pair = result[j]
    GiveOrderToUnit(units[pair[2]], cmdTag, nodes[pair[1]], keyState)
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- determine needed time and optimize the maxUnits limit

  if (rand(0,2)==2) then
    local delay = os.clock()-t
    if (delay>desiredSFP) then
      maxHungarianUnits=maxHungarianUnits-1
    elseif (delay<(desiredSFP*0.8))and(#units>maxHungarianUnits*0.95) then
      maxHungarianUnits=maxHungarianUnits+1
    end
  end
end --// end function SendOrdersHungarian()


function findHungarian(array)
  local starmask = {}
  local colcover = {}
  local rowcover = {}

  for i=1,#array do
    starmask[i] = {}
    rowcover[i] = false
    for j=1,#(array[i]) do
      starmask[i][j] = 0
      colcover[j]    = false
    end
  end

  subMinimumFromRows(array)
  starZeroes(array, starmask)
  return stepCoverStarCol(array, starmask, colcover, rowcover)
end


function subMinimumFromRows(array)
  for i,list in ipairs(array) do
    local min = math.huge
    for j,val in ipairs(list) do
      if val < min then
        min = val
      end
    end
    for j,_ in ipairs(list) do
      list[j] = list[j] - min
    end
  end
end

function starZeroes(array, starmask)
  for i,list in ipairs(array) do
    for j, val in ipairs(list) do
      if val == 0 then
        maybeStar(starmask, i, j)
      end
    end
  end
end

function maybeStar(starmask, row, col)
  for i,_ in ipairs(starmask) do
    if starmask[i][col] == 1 then
      return
    end
  end
  for j,val in ipairs(starmask[row]) do
    if val == 1 then
      return
    end
  end
  starmask[row][col] = 1
end

function stepCoverStarCol(array, starmask, colcover, rowcover)
  coverStarCol(starmask, colcover)
  if allCovered(colcover) then
    return returnStarPositions(starmask)
  else
    return stepPrimeZeroes(array, starmask, colcover, rowcover)
  end
end

function coverStarCol(starmask, colcover)
  for i,list in ipairs(starmask) do
    for j,val in ipairs(list) do
      if starmask[i][j] == 1 then
        colcover[j] = true
      end
    end
  end
end

function allCovered(colcover)
  for _,val in ipairs(colcover) do
    if not val then
      return false
    end
  end
  return true
end

function returnStarPositions(starmask)
  local positions = {}
  for i,list in ipairs(starmask) do
    for j,val in ipairs(list) do
      if val == 1 then
        tinsert(positions, {i, j})
      end
    end
  end
  return positions
end

function stepPrimeZeroes(array, starmask, colcover, rowcover)
  for i,list in ipairs(array) do
    for j,val in ipairs(list) do
      if not colcover[j] and not rowcover[i] and val == 0 then
        starmask[i][j] = 2
        local starpos = findStarInRow(starmask, i)
        if starpos then
          rowcover[i] = true
          colcover[starpos] = false
        else
          return stepFiveStar(array,starmask,colcover,rowcover, {}, {{i,j}}, i,j)
        end
      end
    end
  end

  adjustValue(array,colcover,rowcover)
  return stepPrimeZeroes(array,starmask,colcover,rowcover)
end

function findStarInRow(starmask, row)
  for j,val in ipairs(starmask[row]) do
    if val == 1 then
      return j
    end
  end
  return nil
end

function adjustValue(array, colcover, rowcover)
  local min = math.huge
  for i,list in ipairs(array) do
    for j,val in ipairs(list) do
      if not colcover[j] and not rowcover[i] then
        if val < min then
          min = val
        end
      end
    end
  end
  for i,list in ipairs(array) do
    if rowcover[i] then
      for j,_ in ipairs(list) do
        list[j] = list[j] + min
      end
    end
  end
  for j,_ in ipairs(array[1]) do
    if not colcover[j] then
      for i,list in ipairs(array) do
        list[j] = list[j] - min
      end
    end
  end
end

function stepFiveStar(array,starmask,colcover,rowcover,stars,primes,row,col)
  local starrow = nil
  for i,list in ipairs(starmask) do
    if list[col] == 1 then
      starrow = i
      break
    end
  end
  if starrow then
    tinsert(stars, {starrow, col})
    return stepFivePrime(array,starmask,colcover,rowcover,stars,primes,starrow,col)
  else
    return stepFiveLast(array,starmask,colcover,rowcover,stars,primes)
  end
end

function stepFivePrime(array,starmask,colcover,rowcover,stars,primes,row,col)
  local primecol = nil
  for j,_ in ipairs(starmask) do
    if starmask[row][j] == 2 then
      primecol = j
      break
    end
  end
  if primecol then
    tinsert(primes, {row, primecol})
    return stepFiveStar(array,starmask,colcover,rowcover,stars,primes,row,primecol)
  else
    return stepFiveLast(array,starmask,colcover,rowcover,stars,primes)
  end
end

function stepFiveLast(array,starmask,colcover,rowcover,stars,primes)
  for _,pos in ipairs(stars) do
    starmask[pos[1]][pos[2]] = 0
  end
  for _,pos in ipairs(primes) do
    starmask[pos[1]][pos[2]] = 1
  end
  for i,list in ipairs(starmask) do
    for j,val in ipairs(list) do
      if val == 2 then
        list[j] = 0
      end
    end
  end
  for j,_ in ipairs(colcover) do
    colcover[j] = false
  end
  for i,_ in ipairs(rowcover) do
    rowcover[i] = false
  end
  return stepCoverStarCol(array, starmask,colcover,rowcover)
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

Niobium · Post by **Niobium** » 03 Jul 2009, 04:30

TheFatController wrote:Update on the bug

You can recreate this every time by starting spring.exe with Empty script and /cheat /give 38 corthud. Draw some lines with all selected and it'll crash very fast.

The issue seems to be in step 2. (as per the comments in the code), it looks like in the old spring none of this code was run at all so its probably always been buggy (ie it makes assumptions like that SearchNewNextNodes will certainly populate the next node when it wont etc. and via Echo i've never seen a call to SearchNewNextNodes not result in a crash...).

I can't find the fix in this step, short of rewriting it which I may do if noones fixed it before next BA (which will be as soon as the engine is updated to fix featurebuildstep...)

Are you sure you are running the latest version? (Check springdownloader), I have been unable to get it to crash with any amount of units, including 38 thuds. I'll go write a script to feed optimized algorithm random positions/destinations to see if it can crash it.

As for arghs version, it's a solution, but SendOrdersRandom is not pretty :p

TheFatController · Post by **TheFatController** » 03 Jul 2009, 09:38

Hmm this was the version from the link on this thread, ill try the one from SD, I can usually get it to crash by /give all and repeatedly grabbing groups and giving orders but if you've fixed it already that's awesome

Niobium · Post by **Niobium** » 03 Jul 2009, 10:09

I've deleted all links to any version of it on the forums, and the upload on jobjol, to try and control this version mess.

Got a springdownloader account now, so the springdownloader version is the only, and most up to date, version available.

Make sure you have version 1.2, which I uploaded today. It has a lot of improvements/fixes.

Argh · Post by **Argh** » 03 Jul 2009, 10:27

Eh? So ya fixed Option 2? That would be swell, Random is not great.

Niobium · Post by **Niobium** » 03 Jul 2009, 10:30

Argh wrote:Eh? So ya fixed Option 2? That would be swell, Random is not great.

I ran like 10,000+ tests with algorithm #2, with random input of sizes 1 to 100, and it never got an error, so I'm assuming TFC was using an older version.

Argh · Post by **Argh** » 03 Jul 2009, 12:13

Excellent!

Soooo... where is the current code? Excuse me, I'm reeeeeally tired now, and it's not at the top of the thread...

el_matarife · Post by **el_matarife** » 03 Jul 2009, 12:47

Argh wrote:Excellent!

Soooo... where is the current code? Excuse me, I'm reeeeeally tired now, and it's not at the top of the thread...

Niobium wrote: Got a springdownloader account now, so the springdownloader version is the only, and most up to date, version available.

Make sure you have version 1.2, which I uploaded today. It has a lot of improvements/fixes.

Login to SpringDownloader to grab the most up to date version.

Argh · Post by **Argh** » 03 Jul 2009, 13:11

I don't suppose that anybody could just post it... criminy... too tired to think about this right now.

el_matarife · Post by **el_matarife** » 03 Jul 2009, 14:22

http://pastebin.com/dd733da4 I paste bin'd it for one day, since one month would almost certainly overlap with a new version. You've got 24 hours so hopefully you see this when you wake up.

very_bad_soldier · Post by **very_bad_soldier** » 03 Jul 2009, 14:24

Argh wrote:I don't suppose that anybody could just post it... criminy... too tired to think about this right now.

This is the shortest route: http://spring.vsync.de/luaManager/lua_m ... =10&id=228

Argh · Post by **Argh** » 03 Jul 2009, 19:15

Thanks, I've got it. Sorry for being a pain in the arse, I'm just really tired and busy right now.

Jazcash · Post by **Jazcash** » 03 Jul 2009, 19:32

I'm using that version that vbs posted and the GUI LUA thingy still disables itself when I select too many units and I'm still getting errors and inability to form loads of units.

Argh · Post by **Argh** » 03 Jul 2009, 21:33

Try my version. Haven't had a complaint about it since I dropped Option 2.

Niobium · Post by **Niobium** » 04 Jul 2009, 05:57

JAZCASH wrote:I'm using that version that vbs posted and the GUI LUA thingy still disables itself when I select too many units and I'm still getting errors and inability to form loads of units.

Are you sure you are using the right version?.............. Just because you downloaded the new one doesn't mean you are using it.

I need more information
- Mod
- Units
- Infolog.txt, or either by looking at infolog.txt or from the crash, I need the line number and error description

Like I said, I ran 10,000+ tests on the algorithms, with the large majority of them using 100 units/destinations (Which is more than the max units algorithm will be allowed to run with in normal use). So I am quite amazed that you can just go download it and make it crash like that.

Jazcash · Post by **Jazcash** » 10 Jul 2009, 23:37

I'm sorry, can I get the link for the version of Custom Formations 2 which works with the final version of Spring? At the moment the only thing I can get my hands on is Custom Formations 1 working, Custom Formations 1 not working and Custom Formations 2 not working.

There's links to the dead versions all over the place -_-

Niobium · Post by **Niobium** » 11 Jul 2009, 06:02

JAZCASH wrote:I'm sorry, can I get the link for the version of Custom Formations 2 which works with the final version of Spring? At the moment the only thing I can get my hands on is Custom Formations 1 working, Custom Formations 1 not working and Custom Formations 2 not working.

There's links to the dead versions all over the place -_-

I purposely tried to remove all the links to versions as links get outdated, the place to look is either springdownloader, or the widget database at http://www.springinfo.info/?page_id=690

Niobium · Post by **Niobium** » 15 Jul 2009, 12:57

New version released, v2.0, highly recommended to update, many improvements over the old version. Note: New version uses the ALT instead of meta/spacebar.

The optimal algorithm is now twice as fast, mostly from removing use of ipairs(). Which means it should be used for higher numbers of units.

The secondary optimizing algorithm (Which used to cause all those luaui crashes) has been taken out and replaced by a new one written by myself. Which is very fast and produces very good solutions, generally indistinguishable from solutions of optimal algorithm. On my computer at least it can run with 100 units while staying under 0.05 secs per formation.

For those interested, it starts with an initial solution and improves it by removing unit paths that cross, which is the biggest cause of problems.

Get it from springdownloader, or widget database at http://www.springinfo.info/?page_id=690

Jazcash · Post by **Jazcash** » 15 Jul 2009, 13:22

Niobium wrote:New version released, v2.0, highly recommended to update, many improvements over the old version. Note: New version uses the ALT instead of meta/spacebar.

The optimal algorithm is now twice as fast, mostly from removing use of ipairs(). Which means it should be used for higher numbers of units.

The secondary optimizing algorithm (Which used to cause all those luaui crashes) has been taken out and replaced by a new one written by myself. Which is very fast and produces very good solutions, generally indistinguishable from solutions of optimal algorithm. On my computer at least it can run with 100 units while staying under 0.05 secs per formation.

For those interested, it starts with an initial solution and improves it by removing unit paths that cross, which is the biggest cause of problems.

Get it from springdownloader, or widget database at http://www.springinfo.info/?page_id=690

I fucking love you I do.

Spring RTS Engine

Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2

Re: Custom Formations 2