# [TRIGGER] Unit Group problem

Discussion in 'World Editor Help Zone' started by Dynasti, Aug 11, 2008.

1. ### Eleandor

Joined:
Aug 21, 2005
Messages:
3,681
Resources:
2
Models:
1
Tutorials:
1
Resources:
2
1) The answer to this was already given AFAIK, and I wrote what's supposed to be done in 1 line rather than a complete script.
2) And? You'll need a 2nd loop ANYWAY.

If you look at the GUI trigger, you could in fact also exit at any point in the loop. I know jass well enough to know it's better for loops, but I'm pointing out to all GUI users out there that you can have loops in GUI.

It is true that a "pick in range" with increasing ranges will probably take more time than a simple sort. Nevertheless, I'm pretty sure no square root is calculated, it's one of the basic principles of efficient programming to avoid square roots if possible.

If sqrt(x*x + y*y) <= your_range, you might as well calculate:
x*x + y*y <= your_range*your_range, which is an easier calculation.
On the other hand, "pick in range" is a native, which would probably mean it's been made as efficient as possible and will avoid using jass unit groups with unefficient FirstOfGroup and GroupRemoveUnit calls. Especially because it's probably constantly used for Acquisition ranges as well. For that reason, it might be more efficient to use "pick in range" actions.

2. ### YoshiRyu

Joined:
Jun 26, 2007
Messages:
686
Resources:
0
Resources:
0
Not sure, because we need only the 5 first elements (and we doesn't care about their order) and not the full sorted list, you don't need a sort but just a "little piece of sort"

You're talking to the guy who have done a full chess game without JASS -_-

and one other principles of the efficient programming is to not assume what a function do without its code

Sorry, but i'm still thinking that a sort (wich could be partial) could be faster
for example, you could do it with a "5 instances only" bubble sort (because you don't care about the order of the remains of the list)

PS :
i souldn't assume but i'm pretty sure that FirstOfGroup just do a kind of "return group.headptr" and that calling GroupRemoveUnit on FirstOfGroup just do "if (group.headptr==input_unit) set group.headptr = group.headptr.next" and exit the function...

3. ### jareph

Joined:
Oct 20, 2007
Messages:
348
Resources:
2
Maps:
2
Resources:
2
Sry 1st, that i can't give u a beautiful trigger using {TRIGGER} code
my warcraft and editor was crash

a way... but maybe will cause lag... i can't try my self

"create variable "A" as integer"
"create variable "range_A" as real"
"create variable "Group" as unit group"

for loop integer A from 1 to 1
action:
set variable range_A = range_A + 20 (lower the number to make it more accurate)
set variable Group = every unit in range range_A matching condition "what u want"
If then else condition
condition - if number if unit in Group not equal or greater than 5 (prevent miss take)
true - set A to 0 (it will repeat if set to 0)
- clear all unit in Group
false - "what u want..."

for the memory leak... u should remove by urself.... i m not given...
it will make you blur...

4. ### Eleandor

Joined:
Aug 21, 2005
Messages:
3,681
Resources:
2
Models:
1
Tutorials:
1
Resources:
2
I think I can say without doubt that I'm among the best GUI people around here.

you mean?

Logically, I agree with you. But I'm not at all sure of that. You must remember that like every 0,01 seconds the AI loops through all units on the map and calculates the acquisition range for auto-attacks. That would also be some sort of "pick every unit in range and if unit is hostile, attack". I'd be surprised if they would make something as crucial as that not as efficient as possible.
A sort would still mean looping 5 times through all units. Picking every unit in range requires a 1 time loop through all units and checking the range between their positions, and loop again if required.

Sure it's something like that, but like I said, the AI would have to loop through all units every 0,01 seconds. It would be pretty stupid to use a group for that and 2 expensive function calls to get the first of group and remove it. It's 2 calls per unit on the map. I wouldn't be using a queue for something like that... Especially considering that acquisition range would work like this:

Pick every unit on the map and do:
Pick every unit but picked unit and check the range between the 2
if range < picked unit's acquisition range then
attack the unit

This would require 1 group to be created for each unit on the map... Sounds pretty heavy to me.

I'm pretty convinced pick every unit - native is faster than you'd expect. Well, the easiest way to find out is make a benchmark for the EnumUnitsInRange native and your own custom sort... Feel free to make it, I'm interested in it.

5. ### YoshiRyu

Joined:
Jun 26, 2007
Messages:
686
Resources:
0
Resources:
0
arf... that wasn't english ? :/
ok, i'll try to say it an other way...
you think that's "pick in range" do not use square root, but you're not sure
in coding, it's a bad thing to considerate as true thing you can't check
is it more understandable ?
(my apologies, i'm french, sorry, sorry, sorry, ...)

maybe not, maybe they have found a way to optimize that by using a less obvious algorythm
for exemple, it's probably performed only for unit wich are of different teams
you've got 100 units and your opponent got 100 units too
a "pick in range" for each unit perform 40 000 checks
if you take in consideration that unit acquisition work only on enemy unit
it perform 10 000 checks
i think (but i'm still assuming, wich is bad) that the "acquisition range" do not use "pick in range" because it would do to many useless check

well, only map script are in jass, the game is probably in C++, wich mean that the game's dev have access to hundreds of options we don't have
and because of that, they probably have access to an array (and not a group) wich contain all units and on wich they just do "for(int i=0; i<nb_units; i++) all_units.anythingtheywant"

PS : if i make a sort, i won't make it in a group, i'll use an output array and use the group as a constant input

6. ### Vicboy

Joined:
Aug 20, 2007
Messages:
1,048
Resources:
2
Maps:
2
Resources:
2
You guys are really... Arrogant...

7. ### Eleandor

Joined:
Aug 21, 2005
Messages:
3,681
Resources:
2
Models:
1
Tutorials:
1
Resources:
2
I can't know for sure indeed, but why would they use sqrt if they don't have to?

The algorithm would still involve a "pick every unit in range". All they could do is eliminate e.g. half the units on the map, but they would still have to pick every possible unit and calculate its distance to the "picked" unit... Which, when done with groups, would be inefficient.

Ofcourse, which brings me to my point that the native "Pick every unit in range" is probably programmed efficiently in c, while a jass script that picks every unit in a group with FirstOfGroup calls and such would never be as efficiently.
Which is exactly why I'd like to see a benchmark between your jassed sort and the native "pick every unit" scripts.

Why?

Also, you might want to remove the "banned" tag. It's not allowed to mimic the effects.

8. ### Vicboy

Joined:
Aug 20, 2007
Messages:
1,048
Resources:
2
Maps:
2
Resources:
2

BTW, no I like mimicking...

9. ### Eleandor

Joined:
Aug 21, 2005
Messages:
3,681
Resources:
2
Models:
1
Tutorials:
1
Resources:
2
Well, if it makes you happy...

Just warning you, it's forbidden by the rules, or at least it was some time ago.

10. ### YoshiRyu

Joined:
Jun 26, 2007
Messages:
686
Resources:
0
Resources:
0
because in pro world, you make sometime crappy code
in fact, optimizing code cost money, so optimization are done only when required
if something doesn't make your product lag, you don't spend time to optimize it

As i've already said : "group" is a JASS type, warcraft is not made in JASS
JASS is just a script language, warcraft is made in a compilable language

not more and not less than FirstInGroup
but with a "pick in range" called n times with k units, you can be sure that the game will perform n*k checks, by using FirstInGroup cleverly, you can do less than n*k checks

@Dinasti : i've done a partial sort function based on the bubble sort, but i hadn't tested it a lot,
it clean the input_group but it doesn't destroy it, it don't destroy the from_point too
Code (vJASS):
function GetClosestUnitToPointInGroup takes group input_group, location from_point, integer output_group_size returns group
local integer input_group_size = CountUnitsInGroup(input_group)

local unit array unit_array
local real array range_array

local group output_group

local integer i
local unit i_unit
local real i_range
local location i_loc

local integer l

set i = 0
loop
exitwhen (i >= input_group_size)
set i_unit = FirstOfGroup(input_group)
set unit_array[i] = i_unit
set i_loc = GetUnitLoc(i_unit)
set range_array[i] = DistanceBetweenPoints(from_point, i_loc)
call RemoveLocation(i_loc)
set i_loc = null
call GroupRemoveUnit(input_group, i_unit)
set i = i + 1
endloop

set l = 0
loop
exitwhen ((l == output_group_size) or (l >= input_group_size - 1))
set i = 0
loop
exitwhen (i >= input_group_size - l - 1)
if (range_array[i] < range_array[i+1]) then
set i_unit = unit_array[i]
set i_range = range_array[i]
set unit_array[i] = unit_array[i+1]
set range_array[i] = range_array[i+1]
set unit_array[i+1] = i_unit
set range_array[i+1] = i_range
endif
set i = i + 1
endloop
set l = l + 1
endloop

set output_group = CreateGroup()
set i = 0
loop
exitwhen (i >= input_group_size)
if (i >= input_group_size - output_group_size) then
endif
set unit_array[i] = null
set i = i + 1
endloop

return output_group
endfunction

Last edited: Aug 14, 2008
11. ### Vicboy

Joined:
Aug 20, 2007
Messages:
1,048
Resources:
2
Maps:
2
Resources:
2
Hmm, any of you guys a modeler?

12. ### Eleandor

Joined:
Aug 21, 2005
Messages:
3,681
Resources:
2
Models:
1
Tutorials:
1
Resources:
2
There's a difference between "optimizations" and the very basics... It's common knowledge amongst programmers that to know exact distance you use sqrt, to know which one is the closest (or "relative" distance), you don't use sqrt.

Yes, which is yet again my point: why would they use groups for something that needs to be efficient? Which brings me to the point that "pick every unit" (made in c) can still be faster than a group sort (made in jass). Not because of the principles behind the concept, but because it's simply not written in jass.

Which still requires at least 1 function call. Per unit, that is.

Now you're assuming stuff you can't see.

You're not nulling unit_array or i_loc.

And if you care so much about efficiency, don't use the CountUnitsInGroup bj.

Code (vJASS):

local integer input_group_size = 0

local unit array unit_array
local real array range_array

local group output_group

local integer i
local unit i_unit
local real i_range
local location i_loc

local integer l

loop
set i_unit = FirstOfGroup(input_group)
exitwhen (i_unit == null)
set unit_array[input_group_size] = i_unit
set i_loc = GetUnitLoc(i_unit)
set range_array[input_group_size] = DistanceBetweenPoints(from_point, i_loc) // again, don't use a function, calculate it directly with x, y coordinates, preferably without squareroot.
call RemoveLocation(i_loc)
call GroupRemoveUnit(input_group, i_unit)
set input_group_size = input_group_size + 1
endloop

...

13. ### Vicboy

Joined:
Aug 20, 2007
Messages:
1,048
Resources:
2
Maps:
2
Resources:
2
You guys got 12 posts in this single thread about one boring and confusing argument!

14. ### YoshiRyu

Joined:
Jun 26, 2007
Messages:
686
Resources:
0
Resources:
0
when hundreds of persons work on the same code, their first aim is to make a code understandable, not an optimised one, I KNOW that you can avoid the sqrt if you just need to compare distances, but that's not enough to affirmate that it's done in "pick in range", you've got the source code of war3 ? no you don't

but who the hell force you to sort a group ?
OF COURSE, i'll use an array and not a group, i say it since the beggening...

and why 1 fonction call per unit is heavier than 1 fonction call per range ?
and what allow you to affirm that "pick in range" is smaller than "first of group" ?

yes i am, but there is near 99% chance that i'm more qualified than you about that...

useless

code have to be easy to read when possible, 1 CountUnitsInGroup is nearly nothing and it make the code more clear for the one who will try to understand it

EDIT
but you're still reading them ;p

15. ### Vicboy

Joined:
Aug 20, 2007
Messages:
1,048
Resources:
2
Maps:
2
Resources:
2
Okay, I'll join the argument...

I like GUI cause... After Starcraft II's release, JASS isn't used...

That's why.

EDIT:

Hmm, noone responded yet...

I win!

16. ### YoshiRyu

Joined:
Jun 26, 2007
Messages:
686
Resources:
0
Resources:
0
lol, we're not arguing about GUI vs JASS
we're arguing about "growing pick in range" vs "unit sort", which one is faster

17. ### Vicboy

Joined:
Aug 20, 2007
Messages:
1,048
Resources:
2
Maps:
2
Resources:
2
I didn't know that...

What the heck are you guys saying???

18. ### YoshiRyu

Joined:
Jun 26, 2007
Messages:
686
Resources:
0
Resources:
0
Eleandor think that "for r from 0 to limit, pick unit in range r" is faster
I think that using a partial sort on an array of unit is faster
(faster = less lag)

19. ### Eleandor

Joined:
Aug 21, 2005
Messages:
3,681
Resources:
2
Models:
1
Tutorials:
1
Resources:
2
I don't think hundreds of people have developed jass. Even then, a quick calculation of x*x + y*y followed by a comment saying no sqrt is required won't take years of development, would you think? Besides, I'm pretty sure a lot work went into optimising warcraft, as with most videogames.

Which still doesn't make my argument any less valid. In fact, you've said it yourself: jass can't be as efficient as c. I don't know which one would be faster, I don't even care, but you keep saying "nananana mine is faster nanana", while at the same time admitting the native itself can be faster because it wasn't written in jass. Make up your mind, ok?

right...

Not useless, always null variables and clean leaks. It has little to do with uselessness, more to do with discipline, something most of you seem to lack.

Not at all. the fact the variablename is called input_group_size says enough. If you would still not know what that variable stands for, you can always add a comment that in the first loop you get the group size and put it into input_group_size. On top of that, your function is called GetClosestUnitToPointInGroup. Woever uses it should NOT care about the implementation, he should only know what input is required and what output is expected, and preferably in an efficient way.

20. ### Vicboy

Joined:
Aug 20, 2007
Messages:
1,048
Resources:
2
Maps:
2
Resources:
2
Elean is ignoring me...