Efficient way to find which unit has the most units near it?

[Weep]

The goal is to find which unit to target for maximum splash. This does not need to be 100% accurate; a near-best result is fine. O(n) or O(n^2 for greatly lowered n) would be nice.

Hopefully there's a better way than enumerating an area around every unit and counting (or enumerating an area around every unit and incrementing an attached integer on the enumerated units) followed by a sort.

 

[DioD]

there is no way to detect units nearby of other unit without checking it's distance, not jass, not any other language, you cant ever perform this in reallife, just try to get midrange object around you without checking every object in your sight range.

only way to improve performance on single call is constant calculations and monitoring units, soo, when function is called, you will use precached results right now without losing any time.

 

[Bribe]

only way to improve performance on single call is constant calculations and monitoring units, soo, when function is called, you will use precached results right now without losing any time.

Which is incredibly disadvantageous as a little extra work for some rare splash damage is much more optimal than a constant periodic timer.

 

[DioD]

This will do job well, if you know any other way - free to post it right now.

also there is no sorting algorithm O(N) possible, ever in best case you will need to check every value to at least 2 other values.

 

[Bribe]

groupenumunitsinrange of first unit

groupenumunitsinrange for each enumerated unit to count how many units are picked around it

To sort, simply track the current-highest number of units in a single, scalar variable and the unit associated with it.

At the end, whichever originally-picked unit that has the highest count is the target.

 

[Tamisrah]

Theory&Java
random thoughts in jass

 

[SerraAvenger]

You can do a greedy algorithm, dividing the area in half and then checking which half has more units in it; Repeat that process, until you have a field about the size of the splash. Then pick the most center or whatever unit out of those.

Since you have to check which units are within your current areas every time, you will be in O(n + log A/B), where A is the area in which you start to search and B is the Area you want to reach. This algorithm is far from optimal, but it is very fast.

EDIT: Going on with my random rant against DioD:
>also there is no sorting algorithm O(N) possible
Check Radix sort for O(n) sorting. Also, ND sort can easily work in O(n).

>there is no way to detect units nearby of other unit without checking it's distance
Check my Algorithm above for something that doesn't use the distance between any two units at all. It is not optimal, right, but seems to be good enough for this problem.

 

[Nestharus]

A unit in range event and a balanced binary tree would be the most optimal way to do this.

 

[SerraAvenger]

A unit in range event and a balanced binary tree would be the most optimal way to do this.

Reasoning?

 

[Weep]

Thanks for the suggestions, I'll do some more contemplation. I was thinking about a median cut type algorithm, and then realized that pretty much depends on a density way higher than provided with units in WC3. :nuts:

groupenumunitsinrange of first unit

groupenumunitsinrange for each enumerated unit to count how many units are picked around it

Isn't that what I posted I'd already considered and hoped to improve upon?

You can do a greedy algorithm, dividing the area in half and then checking which half has more units in it; Repeat that process, until you have a field about the size of the splash. Then pick the most center or whatever unit out of those.

And if the best is on the centerline between the two halves?

Perhaps doing the same with three overlapping "halves", one in the middle?

A unit in range event and a balanced binary tree would be the most optimal way to do this.

AFAIK Unit In Range event is similar to doing an in-range enum every 0.1s, although I don't know how it compares in computational weight. I have my doubts this is any lighter than occasionally performing the same (?) computation on only the relevant units at the time of inquiry...

 

[Bribe]

Your method sounded different because you mentioned sorting afterwards, while my method involved an active sort, tracking only the running maximum throughout the process.

 

[Troll-Brain]

A unit in range event and a balanced binary tree would be the most optimal way to do this.

I agree, since accurate is not required here. (range event)

AFAIK Unit In Range event is similar to doing an in-range enum every 0.1s, although I don't know how it compares in computational weight. I have my doubts this is any lighter than occasionally performing the same (?) computation on only the relevant units at the time of inquiry...

Indeed for the interval check it's right, but you forgot that the periodic check is done by the wc3 engine itself, not a random jass code compiled.
Or maybe i'm wrong and the final executed code is about the same.

Also do you really think all this extra stuff is really needed, i mean how often you need to know that ? All these workarounds aren't too overkill ? Any concrete example ?
Or it's just for fun ? Meh, anyway it's still interesting and i don't want to offense you, i'm just curious in which kind of situation all this stuff has a reason to be.

 

[Weep]

Indeed for the interval check it's right, but you forgot that the periodic check is done by the wc3 engine itself, not a random jass code compiled.
Or maybe i'm wrong and the final executed code is about the same.

Right, which is why I put in the caveat that I don't know how it compares in computational weight.

Also do you really think all this extra stuff is really needed, i mean how often you need to know that ? All these workarounds aren't too overkill ? Any concrete example ?
Or it's just for fun ? Meh, anyway it's still interesting and i don't want to offense you, i'm just curious in which kind of situation all this stuff has a reason to be.

Mostly, to have a non-targeted autocast spell with automatic targeting, that is not stupid with regards to its choices. Also, the "hard mode" version is to find a near-optimal target automatically for a "corpse explosion" spell, which causes splash damage from corpses picked in an area - but which area will cause the most splash damage? Hmm.

My old attempt was laggy when I made it with GUI, but perhaps lightening it a few times by JASSifying the process will be good enough. I'm also considering making the splash center on the AOE, not on each corpse.

 

[Troll-Brain]

I'm not surprised that is laggy in gui, because of handles creation/destruction like location, group and such.
But i would be surprised if it lags with jass code with the rect enum process, with less than let's say 100 units, you even don't need to create/destroy rects, just move them, as you probably already know.

Also if your areas are enough small you can avoid the distance check since the square approximation would be good enough, rather than the perfect one, the circle.

 

[SerraAvenger]

I'm not surprised that is laggy in gui, because of handles creation/destruction like location, group and such.
But i would be surprised if it lags with jass code with the rect enum process, with less than let's say 100 units, you even don't need to create/destroy rects, just move them, as you probably already know.

Also if your areas are enough small you can avoid the distance check since the square approximation would be good enough, rather than the perfect one, the circle.

GUI -> JASS doesn't really change complexity away from O(n!). IIRC, rect moving didn't really work either.

Perhaps doing the same with three overlapping "halves", one in the middle?

Two overlapping "halves" (or three, as you suggested) should work well. You just need to make sure that you always remove at least some percentage of the Area, like 25% or something.

 

[Trollvottel]

GUI -> JASS doesn't really change complexity away from O(n!). IIRC, rect moving didn't really work either.

Just to note it:
It is not even O(n²), which is also bad, but not as bad.... I mean You have to check every Unit for near units. So you check n times for some units, i think in the worst case it would be O(n * n/4) but always, if there are always 1/4*n units near each unit. Or did i miss anything that would make it n! ?

 

[Troll-Brain]

I don't get why the worst case wouldn't be O(N²).

Ofc it's not the greatest algorithm of the year but there still a pretty huge difference between doing O(N²) simple operations and O(N²) handle creations/destructions (locations at very least).

But yes i didn't get that was O(N²), with 100 units it becomes hard
I guess the limit op would be reached, because as far i remember a simple empty incrementation loop reach it before 15 000 iterations.
I still believe it would be fine with 50 units or less though, so i think fair enough for any real case, or are you making an other random AOS ?
It worths a try.

About the rect thing i had never the need to move them, but i wouldn't see why it wouldn't work, ofc moving a rect won't change a region if you have added the rect to it, but that's all.
A rect is added to a region by val not by ref, if you understand what i want to mean, but it's off-topic here.
Or is it an other obscure jass bug/limitation ?

By the way, the range event can't work alone since we don't gave the opposite event, we would still have to use a periodic check, so Nestharus and i were wrong at this particular point.

 

[SerraAvenger]

Just to note it:
It is not even O(n²), which is also bad, but not as bad.... I mean You have to check every Unit for near units. So you check n times for some units, i think in the worst case it would be O(n * n/4) but always, if there are always 1/4*n units near each unit. Or did i miss anything that would make it n! ?

You have to calculate the distance between every pair of units. That creates an undirected graph with n vertices and full edges. Every edge is one calculation.

It is true that you only have O(n²) edges, I'm sorry about that. I got it mixed with the number of length n paths on that graph, sorry.

Spoiler

Anyhow, O(n²/4)=O(n²). Also, the nth unit adds n-1 edges; Hence you have Z[i=1...n](i-1) = n*(n-1)/2 = (n²-n)/2 edges for n units. Now let's just look at whether
n²/4<(n²-n)/2 for any but a finite number of n: n²/2<n²-n <=> n<n²/2 so yeah you actually were underestimating the number of edges by a tiny bit. Not that it mattered much anyway...

About the rect thing i had never the need to move them, but i wouldn't see why it wouldn't work, ofc moving a rect won't change a region if you have added the rect to it, but that's all.

Well I guess that was the problem, I don't really remember.

But anyhow, my solution is not periodical, has a better complexity, doesn't require any handle allocation... I'm just unsure if it is precise enough. You could playtest it and see if it makes obvious errors that are unforgivable.

 

[Troll-Brain]

But anyhow, my solution is not periodical, has a better complexity, doesn't require any handle allocation... I'm just unsure if it is precise enough. You could playtest it and see if it makes obvious errors that are unforgivable.

"Mine" (which is in fact Weep's first algorithm but jassified) is neither periodical, neither got any dynamic handle allocation.
But to tell you the truth, i don't understand your algorithm, i mean i don't see how it could give a right result. Maybe i should try it on a paper.

Anyway i don't really give it a shit to it, i've removed wc3 from my computers since months. I'm just here for fun
But like i said i still believe the Weep's lag problem was mostly because of GUI (many locations/group and such handles creation/destruction).
It's just a theory so ofc i can be wrong.
Let's Weep tell us, or try yourself if you really want it.

 

[Weep]

Anyhow, O(n²/4)=O(n²).

Not when 1/4 second lag is noticeable and 1/16 second lag is imperceptible.

But like i said i still believe the Weep's lag problem was mostly because of GUI (many locations/group and such handles creation/destruction).
It's just a theory so ofc i can be wrong.
Let's Weep tell us, or try yourself if you really want it.

I will, when I get back to working on this spell.

Thanks for the discussion, again.