distance sort sqf

[basil_rs]

hi folks

iÂ'm a ofp script newbee and i think i need some help.
what i need is a way to sort units asc to distance.
i did it with a rank idea but its a damn performance hog and
more dirty then clear

look at this

_unit is player for ex. _units is a simple 2d unit array like
list trigger. can be used with [player,units] call distfunc
where distfunc is preprocessed file

distance.sqf
----------------------------------------

private ["_units","_unit"];
_unit  = _this select 0;
_units = _this select 1;

_i = 0;
_j = count _units;

while ("_i<_j") do {
 _u1 = _units select _i;
 _d1 = _u1 distance _unit;

 _near set [_i, _u1];

 _o = _i + 1;
 _p = count _units;

 while ("_o<_p") do {
  _u2 = _units select _o;
  _d2 = _u2 distance _unit;

   if (_d1<_d2) then { _rank set [_i, ((_rank select _i) + 1)] }
   else              { _rank set [_o, ((_rank select _o) + 1)] };
  _o = _o + 1;
 };
 _i = _i + 1;
};

_i = 0;
_j = count _rank;
while ("_i<_j") do {
 _o = _j - ((_rank select _i) + 1);
 _nearest set [_o, (_near select _i)];
 _i = _i + 1;
}

---------------------------------
now nearest unit to _unit is first in _nearest, second - second in
_nearest ...

well this works but when i put this on 20 units my cpu is going
down. i need this to provide waypoints to a helicopter pilot who
pickup units from a custom rescue area. i cant do this with
simple waypoints couse unit count and position is never
the same.

another idea is to create a couple of units that group and regroup
automaticaly. nearest with next - next with next ...

is there a good way to sort arrays or another funktion like
nearplayer. i saw this nearestobject "streetlamp" stuff but it
seems not to work with custom objects.

what do you think ?

 

[Spinor]

The easiest way to reduce the CPU workload is to write your code as a script (i.e. to include it into the script where you need the sorted list) and use the waiting command '~' in the loops. That way the CPU workload is distributed over multiple frames rather than doing it in one (functions are always executed in one go and if there execution takes too long, will cause hickups.

It would of course be better though, to have the code as a nice function as it can be reused elsewhere (e.g. by me  ;D, I think I will also need such a thing). I haven't checked your algorithm in detail, but one thing that struck me is that you have to call the distance command very often. If you store an already calculated distance you would only have to call it once for each element in _units.

I am not a programming wiz, but you could try some other sorting algorithms, like a bubble sort (I think thats what its called  ):
 construct an array of all distances parallel to units:
_units
_distances
Now check neighboring pairs of distances and switch their position (both in _distances and _units) if _left > _right. Do this until there is no switching possible.
I have no idea if this is faster than your method, though.

Hope this helps,
Spinor

[bn880]

Here is kind of an algorithm for you using the Buble sort

_unit = 0
_targetsArray = 1

;/ GET DISTANCES
FOREACH _target in _targetsArray
_distanceArray = _distanceArray + [_target distance _unit];
NEXT _target

j = 0
n = count _distanceArray
WHILE j < n-1 DO
   k = j+1
   WHILE k < n DO
      IF _distanceArray[j] > _distanceArray[k] THEN
         tempDist = _distanceArray[j]
         tempTarget = _targetsArray[j]
         _distanceArray[j] = _distanceArray[k]
         _targetsArray[j] = _targetsArray[k]
         _distanceArray[k] = tempDist
         _targetsArray[k] = tempTarget
      END IF
      k++
   END WHILE
   j++
END WHILE

It's almost in sqf format as it is.

To lower the fps load, create the outer WHILE in sqs, and call the inner WHILE as a sqf.

I will create this function if Spinor is too busy...

There are better sorting algorithms, but this should suffice for 700 - 2000 units.

[bn880]

Alright, so that will basically sort the given array with relation to distance from the _unit which is your chopper.

If you want to keep finding the nearest unit from your list to the chopper, just create a function that finds the smallest distance from the chopper to the next unit at the time, and call it every time the chopper is ready for the next pickup.  :-\  Nice and simple.

[toadlife]

Here is a pre-1.85 compatible way of sorting an array and ordering the items from nearest to farthest. This is code derived from my grouplink script and modified to suit your needs. I have no idea if it would be more efficient, but I figured it wouldn't hurt to post it.

*THIS HAS NOT BEEN TESTED*

_object = the helicopter
_objects = the dude the helicopter needs to pick up
order = the array you end up with and the end , the first item in it being the closest and the last item being the farthest.

*THIS HAS NOT BEEN TESTED*

Code: [Select]

_object = _this select 0
_objects = _this select 1
order = []
_nearest = 10000

#loop1
~0.001
_num = (count _objects)
?_num == 0:goto "end"

#loop2
~0.001
_num = _num -1
_item = _objects select _num
?!alive _item:goto "loop1"
_dis = _item distance _object
?_dis < _nearest:_nearestitem = _item;_nearest = _dis
?_num <= 0:order = order + [_nearestitem];_objects = _objects - [_nearestitem];goto "loop1"
goto "loop2"

#end
exit

This version only finds the nearest soldier in a group of soldiers and sets the global variable "nearestitem" to the nearest soldier.

*THIS HAS NOT BEEN TESTED*

Code: [Select]

_object = _this select 0
_objects = _this select 1
_nearest = 10000

#loop1
~0.001
_num = (count _objects)
?_num == 0:goto "end"

#loop2
~0.001
_num = _num -1
_item = _objects select _num
?!alive _item:goto "loop1"
_dis = _item distance _object
?_dis < _nearest:nearestitem = _item;_nearest = _dis
?_num <= 0:goto "end"
goto "loop2"

#end
exit


[toadlife]

Alright, so that will basically sort the given array with relation to distance from the _unit which is your chopper.

If you want to keep finding the nearest unit from your list to the chopper, just create a function that finds the smallest distance from the chopper to the next unit at the time, and call it every time the chopper is ready for the next pickup.  :-\  Nice and simple.

This method sounds like the best way to do it. Find the nearest one at a time. NOW then...a script that finds the fastest pathway between a group of objects would really kick ass!

Anyone up to that?

[basil_rs]

thanks you all  ;D
bubble function should help

[bn880]

NOW then...a script that finds the fastest pathway between a group of objects would really kick ass!

Anyone up to that?

Nope sorry, I would be up for that except I'm now too busy (2-3 days).  ;D   I'll see about posting the bubble function from CoC if anyone is interested...

[toadlife]

I might just write it, if I remember too. I would be usefull.

[bn880]

Yep shortest path is not too bad

This is in ALGPSEUDOCODE:   ;D

called with
source (person or pos), places[] (or persons)

Code: [Select]

_source = this 0
_places = + this 1

WHILE count _places > 0
      _closest  = [_source, _places] call closestFunc
      _resultPathArray = resultPathArray + [_closest]
      _source = _closest
      _places = _places - _closest
END WHILE


[bn880]

I have posted the SortBubble function from the CoC under functions, however this is not a CoC relaease, food for editors only.  

http://www.ofpec.com/editors/funcref.php?letter=S#SortBubble

[basil_rs]

great work !