Function that returns the nearest unit to a point

08-17-2006, 12:57 AM	#1
PandaMine	Is there a function (or could someone make one) that takes a location and returns the nearest unit to that location Thanks

08-17-2006, 01:04 AM	#2
st33m	Try wc3jass.com. Probably something there.

08-17-2006, 02:56 AM

Vexorian

It is easy to make one anyways

JASS:

// x,y : point
// tries : max dist checked would be 2^(tries+8)
// filter : (can use null, simply a filter man.)
//
function getclosest unit takes real x, real y, boolexpr filter, integer tries returns unit
 local unit p
 local unit c=null
 local real min
 local group g=CreateGroup()
 local real d=128.
 local real e
 local real f

    loop
         exitwhen (tries==0) or (c!=null)
         call GroupEnumUnitsInRange(g,x,y,d,filter)
         loop
              set p=FirstOfGroup(g)
              exitwhen p==null
              set e=x-GetUnitX(p)
              set f=y-GetUnitY(p)
              set e=e*e+ f*f
              if (c==null) or (min>e) then
                   set c=p
                   set min=e
              endif
              call GroupRemoveUnit(g,p)
         endloop
         set d=d*2.
         set tries=tries-1
    endloop
    call DestroyGroup(g)
 set g=null
    if (c!=null) then
         set tries=H2I(c)
         set c=null
         return tries
    endif
 return null

endfunction

08-17-2006, 03:59 AM	#4
PipeDream	as written, max distance checked is 2^(tries+6), not +8 Easy to refactor as a max distance condition. Top of the loop: If distance > maxdistance, set distance = maxdistance. Bottom of the loop: exitwhen distance >= maxdistance. Use integers instead of reals for dist/maxdist though or add a tolerance to the comparison.

08-17-2006, 04:34 AM

Vexorian

typo , I didn't want to add an if then else to the loop, it is not needed to actually have the max dist value there anyways, cause that argument is mostly to limit the number of tries, not really for distances.

Quote:

Use integers instead of reals for dist/maxdist though or add a tolerance to the comparison.

Why?

08-17-2006, 04:55 AM	#6
PandaMine	Thanks a lot vex, you should propably include this in the next version of your caster system since I have been using it for many spells Pipedream, There is no need to convert the integers to real just to make a max distance condition, the function is fine the way it is.

08-17-2006, 05:34 AM

PipeDream

Giving the user a number of "tries" is leaking abstraction like a sieve. Distance is a useful alternative, but often you don't want to deal with figuring out the map size, so two versions would be wanted in a good library.

There are two reasons to use integers instead of reals. In Vex's version you've got real subtraction between a quantity that came from the map grid(Unit x/y) and a quantity that did not (x,y arguments). So you're going to run into the real subtraction bugs if your x,y is for example something random.
In the max distance version, which I understand is not the function you're looking for, you need to compare two reals for equality. This is bad news, you have to make it with a tolerance. It's much easier to use integers instead. You only need to use an integer for distance/maxdistance, you can leave the coordinates as reals, although it would be better to use integers for all since that will also take care of the subtraction difficulty. Unfortunately it will only work for maps up to 256x256. So to write an absolutely safe function you need to use x,y integers for the first iteration and reals for the rest! Quite a mess.
---
For the non distance version, you would do well to encode the map size into the function. Perhaps scale up until r is half of one of the map widths, then enum through all units. This will net you a cleaner interface at the cost of complexity.

08-17-2006, 12:49 PM

Vexorian

could you please explain me the real substraction bug?, tolerance would be needed if comparing == with reals, but this function does not do that.

Also if you would really want a max distance argument:

JASS:

// x,y : point
// tries : max dist checked would be 2^(tries+8)
// filter : (can use null, simply a filter man.)
//
function getclosest unit takes real x, real y, boolexpr filter, real max returns unit
 local unit p
 local unit c=null
 local real min
 local group g=CreateGroup()
 local real d=max/8.
 local real e
 local real f
    set max=max+1.
    loop
         exitwhen (d>=max) or (c!=null)
         call GroupEnumUnitsInRange(g,x,y,d,filter)
         loop
              set p=FirstOfGroup(g)
              exitwhen p==null
              set e=x-GetUnitX(p)
              set f=y-GetUnitY(p)
              set e=e*e+ f*f
              if (c==null) or (min>e) then
                   set c=p
                   set min=e
              endif
              call GroupRemoveUnit(g,p)
         endloop
         set d=d*2.
         set tries=tries-1
    endloop
    call DestroyGroup(g)
 set g=null
    if (c!=null) then
         set tries=H2I(c)
         set c=null
         return tries
    endif
 return null

endfunction

08-17-2006, 02:10 PM

PipeDream

real subtraction bug: subtracting two very close real numbers ( a few bits of mantissa off ) becomes the closest garbage you can get to infinity. So, in your first iteration if you have a point that happens to be very very close to but not exactly the position of the unit, something undefined will happen. Likely ways this could happen is evolving a diff eq or computing something that should be the same two different ways.

No real comparison in your version: Indeed, that's why I say "max distance version".
---
exitwhenning before reaching max and doing a final exactly max distance iteration outside the loop would run the same number of bytecodes and work non-surprisingly.

08-17-2006, 04:55 PM	#10
Vexorian	I was going to try to reproduce it but I guess you can give me code that makes it happen?

08-17-2006, 04:57 PM	#11
blu_da_noob	I think 0.0-0.0 makes it happen.

08-17-2006, 09:38 PM	#12
PipeDream	writing 0.0 - 0.0 is fine. http://www.wc3campaigns.net/showthread.php?t=84489

08-17-2006, 11:18 PM

#13

Vexorian

all right, darn darn bug.

First of all I've been using real substraction for ages by now, specially when calculating distances, and never ran into issues, this bug seems to happen when just one bit differs, so I guess it could only happen if both reals are from different sources.

Dilema
* If I leave things with no change, there will be a chance for this to come and ruin everything.
* If I decide to fix this I would have to use (a*1024.-b*1024.)/1024. which is kind of lame.
* If I choose for code without real product/division I would need the duh functions:

JASS:

function Duh takes real d returns real
    if (d>1.) or (d<1.) or (d==1.) then
        return d
    endif
 return 0.
endfunction

then use Duh(a-b), but if I do so I would add a function call to every single situation that actually needs speed...

* I could replace everything with integers, but every single native already returns everything in real so we would have to use valueable time in conversions.

08-17-2006, 11:45 PM

#14

PipeDream

Quote:

this bug seems to happen when just one bit differs

The snippet there has a 4 bit difference (!)

I don't see what use "Duh" would be. I haven't seen it produce Inf/Nan, always something big but not Inf/Nan by a few bits.

08-18-2006, 03:03 AM	#15
Vexorian	Actually, the produced thing has the weird property of not being equal to 1. nor lower than 1 nor greater than 1.0 so that way if I find that crazy real I can recognize it, so it is mostly like an exception handling that returns 0. if it finds the underflow.