wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Resources > Code Resources > Scripts
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 06-20-2009, 02:28 AM   #1
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,025

Submissions (19)

Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default PruneGroup

I have been dissatisfied with my GroupGet library for a while now, but didn't really know how to change it until recently when I got some inspiration from this thread. The result is PruneGroup, a function that lets you pick any number of fittest units from a group instead of only one like GroupGet. The time complexity is O(n*k), where n is the number of units in the group and k is the number of units picked, so if you're only picking a single unit out of the group this function will be no less effective than GroupGet was.

Collapse PruneGroup:
library PruneGroup

//*****************************************************************
//*  PruneGroup
//*  written by: Anitarf
//*
//*  PruneGroup is a function that removes units from a group based
//*  on a user-specified fitness function.
//*
//*    function PruneGroup takes group g, Fitness Function, integer maxUnits, real minFitness returns nothing
//*
//*  The fitness function must follow the Fitness function 
//*  interface that is defined at the start of this library. The
//*  value it returns specifies a unit's fitness, the units with a
//*  higher value will remain in the group while the units with a
//*  lower fitness will be removed from it.
//*  The maxUnits argument specifies at most how many units may
//*  remain in the group, but the actual number may be lower if the
//*  group didn't have that many units in it to begin with or if
//*  too few units had a fitness higher than minFitness, the last
//*  argument of the PruneGroup function.
//*  The fitness limit can be disabled with the NO_FITNESS_LIMIT
//*  constant value defined in the calibration section, this way
//*  you can prune a group based only on the unit limit.
//*****************************************************************

    // This is the function interface for the fitness functions.
    public function interface Fitness takes unit u returns real

    globals
        // If this constant is passed to the PruneGroup function it will ignore the fitness limit.
        // This is a random value that is unlikely to be ever used, you don't really need to change it.
        constant real NO_FITNESS_LIMIT = -112358.13
    endglobals

// END OF CALIBRATION SECTION    
// ================================================================

    globals
        private Fitness func=0
        private integer maxcount=0
        private real minfit=0.0
        private boolean ignoreminfit=false
        
        private unit array fittest
        private real array fitness
        private integer array next
        private integer last=0
        private integer count=0
        private integer N=0
    endglobals

    private function Enum takes nothing returns nothing
        local unit u=GetEnumUnit()
        local real fit=func.evaluate(u)
        local integer i
        local integer j
        // Check if we should bother adding the unit to the list.
        if (ignoreminfit or fit>minfit) and (count<maxcount or fit>fitness[last]) then
            // Get a new index and store the unit.
            set N=N+1
            set count=count+1
            set fittest[N]=u
            set fitness[N]=fit
            // Add the index to the sorted list.
            if last==0 or fit<fitness[last] then
                set next[N]=last
                set last=N
            else
                set i=last
                loop
                    set j=next[i]
                    exitwhen j==0 or fitness[j]>=fit
                    set i=j
                endloop
                set next[N]=next[i]
                set next[i]=N
            endif
            // Remove the last unit from the list if needed.
            if count>maxcount then
                set last=next[last]
                set count=count-1
            endif
        endif
        set u=null
    endfunction

// ================================================================

    function PruneGroup takes group g, Fitness Function, integer maxUnits, real minFitness returns nothing
        // Remember the previous values in case this is interrupting another PruneGroup call.
        local Fitness f=func
        local integer mc=maxcount
        local real mf=minfit
        local integer l=last
        local integer c=count
        local integer n=N
        // Take care of faulty inputs.
        if maxUnits<=0 then
            call GroupClear(g)
            return
        endif
        // Populate the sorted list.
        set count=0
        set last=0
        set minfit=minFitness
        set maxcount=maxUnits
        set ignoreminfit=minfit==NO_FITNESS_LIMIT
        set func=Function
        call ForGroup(g, function Enum)
        // Repopulate the group from the list.
        call GroupClear(g)
        loop
            exitwhen last==0
            call GroupAddUnit(g, fittest[last])
            set last=next[last]
        endloop
        // Cleanup handle references.
        loop
            exitwhen N==n
            set fittest[N]=null
            set N=N-1
        endloop
        // Return the temporary globals to their previous values.
        set func=f
        set minfit=mf
        set maxcount=mc
        set ignoreminfit=minfit==NO_FITNESS_LIMIT
        set count=c
        set last=l
    endfunction

endlibrary
Expand FitnessFunc:
__________________

Last edited by Anitarf : 06-28-2009 at 11:20 PM.
Anitarf is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 06-20-2009, 04:29 AM   #2
fX_
User
 
fX_'s Avatar
 
Join Date: Jan 2007
Posts: 528

Submissions (2)

fX_ will become famous soon enough (38)fX_ will become famous soon enough (38)

Default

shouldnt High$name$() return a positive correspondence of the measured state.

maybe associate (bunch) SetFitnessPosition(), with LowDistance() and HighDistance(), respectively, whether by their naming or what

i don't think the 'N' (global) gets restored like the other functional variables of Enum(), in PruneGroup().
can you "insert" an Enum() (or groupenums in general) while another Enum() is running? dont they queue up or work simultaneously?

Last edited by fX_ : 06-20-2009 at 04:49 AM.
fX_ is offline   Reply With Quote
Old 06-20-2009, 05:52 AM   #3
Veev
User
 
Join Date: Nov 2006
Posts: 199

Veev will become famous soon enough (63)Veev will become famous soon enough (63)Veev will become famous soon enough (63)

Default

Very clever, Anitarf: constant real NO_FITNESS_LIMIT = -112358.13

Last edited by Veev : 06-20-2009 at 05:52 AM.
Veev is offline   Reply With Quote
Old 06-20-2009, 08:52 AM   #4
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,025

Submissions (19)

Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default

Quote:
Originally Posted by fX_
shouldnt High$name$() return a positive correspondence of the measured state.
Right, that was sloppy of me, fixed.

Quote:
maybe associate (bunch) SetFitnessPosition(), with LowDistance() and HighDistance(), respectively, whether by their naming or what
The both have Fitness in the name? But sure, if anyone has a better idea for the names, speak up.

Quote:
i don't think the 'N' (global) gets restored like the other functional variables of Enum(), in PruneGroup().
Oh, but it does, it's just sneaky about it.

Quote:
can you "insert" an Enum() (or groupenums in general) while another Enum() is running? dont they queue up or work simultaneously?
I use ForGroup, not GroupEnum. A lot of maps would crash and die if JASS could work simultaneously.

Quote:
Originally Posted by Veev
Very clever, Anitarf: constant real NO_FITNESS_LIMIT = -112358.13
Meh, it's not that original.
__________________
Anitarf is offline   Reply With Quote
Old 06-20-2009, 09:04 AM   #5
akolyt0r
In Flames
 
akolyt0r's Avatar
 
Join Date: Jan 2006
Posts: 1,153

Submissions (3)

akolyt0r has a spectacular aura about (120)

Default

still you should use private/public for your constants.
__________________
akolyt0r is offline   Reply With Quote
Old 06-20-2009, 10:35 AM   #6
fX_
User
 
fX_'s Avatar
 
Join Date: Jan 2007
Posts: 528

Submissions (2)

fX_ will become famous soon enough (38)fX_ will become famous soon enough (38)

Default

didnt see that
Collapse JASS:
loop
set N=N-1
endloop

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
what i mean with all that "Enum() groupEnum" banter is does this interrupt older runs? is it possible to interrupt older ForGroup() runs and how?

Last edited by fX_ : 06-20-2009 at 10:43 AM.
fX_ is offline   Reply With Quote
Old 06-20-2009, 08:17 PM   #7
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,025

Submissions (19)

Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default

Quote:
Originally Posted by fX_
what i mean with all that "Enum() groupEnum" banter is does this interrupt older runs? is it possible to interrupt older ForGroup() runs and how?
It is possible if a fitness function itself calls PruneGroup. Since this library supports custom fitness functions, there's no way to ensure that that can't happen, so the code needs to take that possibility into account.

Quote:
Originally Posted by akolyt0r
still you should use private/public for your constants.
No need, the NO_FITNESS_LIMIT is a pretty unique constant name, as for NO_UNIT_LIMIT, I'm thinking of removing it since if you have no unit limit, there's no need to use something as complicated as PruneGroup.
__________________
Anitarf is offline   Reply With Quote
Old 06-26-2009, 11:59 PM   #8
Rising_Dusk
Obscurity, the Art


Projects Director
Project Leader: OD
 
Join Date: Feb 2006
Posts: 9,726

Submissions (27)

Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)

Hero Contest #3 - 1st PlaceApproved Map: Desert of ExileApproved Map: Advent of the ZenithHero Contest #2 - 1st PlaceHero Contest - Third place>

Send a message via AIM to Rising_Dusk Send a message via MSN to Rising_Dusk
Default

I like this a lot more than your old approach. I've looked over it and don't see any glaring problems, so I think I will approve this and graveyard the old one. Is that okay?
__________________
Home Page
DoE v1.14c Download
AotZ v2.03d Download
OD v0.10x Download

Coming soon eventually...

Personal To-Do List:
ICARUS
Aot3

WC3C Chat
Chat IP: 66.103.20.109
Earthbound 2 in English
vJass Manual

"DAMAGE_TYPE_POISON motherfucker!" ~Anitarf
Rising_Dusk is offline   Reply With Quote
Old 06-28-2009, 11:23 PM   #9
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,025

Submissions (19)

Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)Anitarf has a brilliant future (883)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default

Quote:
Originally Posted by Rising_Dusk
I like this a lot more than your old approach. I've looked over it and don't see any glaring problems, so I think I will approve this and graveyard the old one. Is that okay?
Sure, if you didn't I was going to graveyard GroupGet myself.
I just did a minor update to the first post, I removed the NO_UNIT_LIMIT constant since if you don't have a unit limit then you needn't use PruneGroup in the first place, you can just do a simple ForGroup. Other than that, the code remains the same.
__________________
Anitarf is offline   Reply With Quote
Old 06-29-2009, 12:52 AM   #10
Rising_Dusk
Obscurity, the Art


Projects Director
Project Leader: OD
 
Join Date: Feb 2006
Posts: 9,726

Submissions (27)

Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)

Hero Contest #3 - 1st PlaceApproved Map: Desert of ExileApproved Map: Advent of the ZenithHero Contest #2 - 1st PlaceHero Contest - Third place>

Send a message via AIM to Rising_Dusk Send a message via MSN to Rising_Dusk
Default

Okay then, Approved.
__________________
Home Page
DoE v1.14c Download
AotZ v2.03d Download
OD v0.10x Download

Coming soon eventually...

Personal To-Do List:
ICARUS
Aot3

WC3C Chat
Chat IP: 66.103.20.109
Earthbound 2 in English
vJass Manual

"DAMAGE_TYPE_POISON motherfucker!" ~Anitarf
Rising_Dusk is offline   Reply With Quote
Old 05-23-2011, 02:54 AM   #11
SanKakU
User
 
Join Date: Jan 2009
Posts: 133

SanKakU has a little shameless behaviour in the past (-1)

Send a message via AIM to SanKakU Send a message via MSN to SanKakU Send a message via Yahoo to SanKakU
Default

is this for animals vs animals themed map?
SanKakU is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 09:56 PM.


Donate

Affiliates
The Hubb http://bylur.com - Warcraft, StarCraft, Diablo and DotA Blog & Forums The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2014, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services