| 01-23-2007, 03:25 AM | #1 |
I'll start by saying I'm looking for conceptual ideas to solve my problem, not actual code. I have an autocast system. Units with certain abilities will automatically cast their abilties when appropriate. The system is fairly complex and 100% JASS. It is on its way to being fully optimized. Its really quite the sight too, I can give a unit 6-7 abilities and it'll just fire away. Healing, Debuffs, channeled spells, AOE's, hell even mana burn and all its variations. Unfortunately I hit a snag on dispel'ish type effects. Lets first just assume the ability in question is Abolish Magic. Yes, I know, abolish magic HAS an autocast, but custom abilities that do similar things (yet not exactly the same) may not. The basic underlying fact here is that the spell being casted is infact targetable on both enemies and allies, and has some girth to it (checking for buffs, etc). Currently, what happens is, any unit with the abolish magic ability is automatically created its own trigger. The trigger says, when any unit enters a certain range (700) of the abolish magic casting unit, it is automatically added to group "UnitsInRange". UnitsInRange is of course 'attached' to the unit with the ability using a combonation of *seldom use* of handlevars and the great structs of JASSHelper (+1 pt for Vexorian). The unit also has a temporary group attached to it, because it cannot modify the UnitsInRange group (Units can have multiple autocastable abilities, all of which use UnitsInRange). The unit is also associated with a timer, which is executed every 1.19 seconds. The timer will do the following things: if "unit is dead", kill timer, cleanup ,etc. if "unit is channeling" do nothing. if "last cast time + cooldown < current time" do nothing. if "mana cost > mana" do nothing. if temporarygroup is empty, add UnitsInRange to temporary group. call ForGroup(temporarygroup, filter). [details below] Now the ForGroup filter is complicated. What it does is this: If the enum unit is dead, no longer in range, has more positive than negative buffs (for allies, or vice versa if enemy), or has no buffs at all, then REMOVE it from the temporary group... Otherwise, set a global variable (target) to the unit. If the global variable (target) is not null, every unit after is then ignored (not removed from the group nor even check range etc). That check is what prevents repetative dumping of UnitsInRange to the temporary group over.. and over... and over again. After the ForGroup call, the global variable target will hold the 'target' we should cast the spell on. If target is null, no valid target was found, so we do nothing and wait for the next time the timer fires. Heres where it is having problems: If I have one unit with abolish magic and 100 surrounding him, it runs smooth. It'll dispel a unit almost instantly after its hit with a negative buff. BUT, If I have 100 units, all with abolish magic, then it goes haywire. See, every unit is adding groups of 100 to another group, then looking through all 100 units, checking to see if they need to be dispelled. That looks like O(N^2) (100 units = 10000 checks) to me (worst case scenario). Worst case scenario happens to be when theres a large bunch of units who can cast dispel standing next to eachother when not one has a single buff. This case is extremely common. Fortunately for me, even if I have 30-40 or even 50 units with abolish magic standing next to eachother it runs semismooth, its just when you hit the 120 mark or so when it noticably bogs down. Do I anticipate someone making 100 units with dispel magic all next to eachother? Not really, but I hate it when maps lag due to heavy jass execution. If there is any better way to approach this problem, I'm all ears. Heres some alternatives I know don't work: GroupEnumUnits... Those functions leak and are slow. They cannot be used at all. Having a trigger store all units that come into range into a group and re-using the group is much better than constantly fetching all nearby units. Increasing the timer firing frequency: Not really fixing the problem, its just making the casting less efficient, and instead of slowing down at the 120 mark, it'll slow down at the 130 or 140 mark. Jass code  JASS:function Autocast_ActDispelSingleFilter takes nothing returns nothing local integer iPositiveBuffCount local integer iNegativeBuffCount if ( Autocast_FilterTarget != null ) then return endif set Autocast_FilterEnemy = GetEnumUnit() if ( GetUnitState(Autocast_FilterEnemy, UNIT_STATE_LIFE) <= 0.5 ) then call GroupRemoveUnit(Autocast_FilterGroup, Autocast_FilterEnemy) return endif if ( IsUnitInRange(Autocast_FilterCaster, Autocast_FilterEnemy, Autocast_FilterRange) == FALSE ) then call GroupRemoveUnit(Autocast_FilterGroup, Autocast_FilterEnemy) return endif set iPositiveBuffCount = UnitCountBuffsEx(Autocast_FilterEnemy, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) set iNegativeBuffCount = UnitCountBuffsEx(Autocast_FilterEnemy, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) if ( IsPlayerAlly(GetOwningPlayer(Autocast_FilterCaster), GetOwningPlayer(Autocast_FilterEnemy)) == TRUE ) then // allies, don't dispel if they got alot of good buffs if ( iPositiveBuffCount > iNegativeBuffCount ) then call GroupRemoveUnit(Autocast_FilterGroup, Autocast_FilterEnemy) return endif else // unlike allies, don't dispel enemies with lots of negative buffs if ( iPositiveBuffCount < iNegativeBuffCount ) then call GroupRemoveUnit(Autocast_FilterGroup, Autocast_FilterEnemy) return endif // hook summoners if ( IsUnitType(Autocast_FilterEnemy, UNIT_TYPE_SUMMONED) == TRUE ) then // bad programming, but whatever. set Autocast_FilterTarget = Autocast_FilterEnemy return endif endif if ( iPositiveBuffCount == 0 and iNegativeBuffCount == 0 ) then call GroupRemoveUnit(Autocast_FilterGroup, Autocast_FilterEnemy) return endif //call BJDebugMsg("Found one: " + I2S(iPositiveBuffCount) + "," + I2S(iNegativeBuffCount) + " " + GetUnitName(uTarget) + " of " + GetPlayerName(GetOwningPlayer(uTarget))) set Autocast_FilterTarget = Autocast_FilterEnemy return endfunction // returns boolean whether or not it casted... function Autocast_ActDispelSingle takes ACAbility ab, ACUnit au, ACInstance ai returns boolean if ( FirstOfGroup(ai.gTemp) == null ) then call GroupAddGroup(au.gEnemiesInRange, ai.gTemp) call GroupAddGroup(au.gFriendsInRange, ai.gTemp) endif call ForGroup(ai.gTemp, function Autocast_ActDispelSingleFilter) if ( Autocast_FilterTarget == null ) then return FALSE endif if ( ab.strOrder == "id" ) then return IssueTargetOrderById(au.u, ab.iOrderId, Autocast_FilterTarget) else return IssueTargetOrder(au.u, ab.strOrder, Autocast_FilterTarget) endif endfunction |
| 01-23-2007, 04:58 AM | #2 |
I shudder to think about doing it in JASS, but a quadtree might be the answer. GroupEnum is unavoidable unless you figure a way to tile the plane with circles :P but if you use a permanent group and a filter (which returns true) it won't leak. Plus they'd be cached, and in fact you'd only need one, since you do the subrectangles in JASS. Then, instead of looping through 100 units that need dispelling, you would just check within the square until you find one unit that is close enough, since I assume a unit can only cast once per moment. Ought to get you to constant time for finding the dispel target in linear units, and another linear in units step for the grid construction. Edit: You wouldn't actually need a quadtree, just placing units on a square 90x90 grid in an array would be good enough I bet. --- Well I ended up just writing it since it seemed like a fun problem. Untested, and probably won't work. The unit lists should be replaced with just a group. To pass the filter in I would recommend subclassing an interface. JASS://! library UnitInRange struct unitpair unit u unitpair next static method Create takes unit u returns unitpair local unitpair p = unitpair.create() set p.u = u set p.next = 0 return p endmethod endstruct globals private group g private unitpair array grid private integer array active //determines if units were added this round private integer activecolor = 0 private integer n = 45 // max is 90 private real minx private real maxx private real miny private real maxy private real width private real height private real hx private real hy private rect maprect private boolexpr truebe endglobals private function truefunc takes nothing returns boolean return true endfunction function UIR_Init takes nothing returns nothing set maprect = GetWorldBounds() set minx = GetRectMinX(maprect) set miny = GetRectMinY(maprect) set maxx = GetRectMaxX(maprect) set maxy = GetRectMaxY(maprect) set width = maxx - minx set height = maxy - miny set hx = n / width //with of a grid cell set hy = n / height set g = CreateGroup() set truebe = Filter(function truefunc) endfunction function destroylist takes unitpair p returns nothing local unitpair next loop exitwhen p == 0 set next = p.next call unitpair.destroy(p) set p = p.next endloop endfunction function AddUnitToCell takes integer i, unit u returns nothing local unitpair p if active[i] == activecolor then set p = active[i] loop exitwhen p.next == 0 set p = p.next endloop set p.next = unitpair.Create(u) else set active[i] = activecolor if grid[i] != 0 then call destroylist(grid[i]) endif set grid[i] = unitpair.Create(u) endif endfunction private function GetRow takes real x returns integer return R2I(hx * (x - minx)) endfunction private function GetCol takes real y returns integer return R2I(hy * (y - miny)) endfunction function UIR_BuildCache takes nothing returns nothing local real x local real y local integer i local integer j local unit u set activecolor = activecolor + 1 call GroupEnumUnitsInRect(g,maprect,truebe) loop set u = FirstOfGroup(g) exitwhen u == null set x = GetUnitX(u) set y = GetUnitY(u) set i = R2I(hx * (x - minx)) set j = R2I(hy * (y - miny)) call AddUnitToCell(i*n + j,u) call GroupRemoveUnit(g,u) endloop endfunction //Must build cache before running //Think about how to add the filter cleanly function UIR_GroupEnumUnitsInRangeCounted takes group g, real x, real y, real r, integer count returns nothing local unitpair p local real rr = r*r local real dx local real dy // Draw bounding square around circle and take all cells that overlap with square local integer mini = GetRow(x-r) local integer maxi = GetRow(x+r) local integer minj = GetCol(y-r) local integer maxj = GetRow(y+r) local integer i = mini local integer j local integer offset loop exitwhen i > maxi set j = minj loop exitwhen j > maxj set offset = i*n+j if active[offset] == activecolor then set p = grid[offset] loop exitwhen p == 0 set dx = GetUnitX(p.u) - x set dy = GetUnitY(p.u) - y if dx*dx + dy*dy < rr then //Include collision circle (?) call GroupAddUnit(g,p.u) set count = count - 1 if count == 0 then return endif endif set p = p.next endloop endif set j = j + 1 endloop set i = i + 1 endloop endfunction //! endlibrary I bet that the native GroupEnumUnitsInRangeCounted will just work though. |
| 01-23-2007, 02:04 PM | #3 |
| 01-23-2007, 08:07 PM | #4 |