Discussion Suggestion: advanced version of instance_nearest

[Roderick]

I'm not 100% sure what would be the proper naming convention, but what I'm suggesting would be a second version of instance_nearest that would take some extra parameters:

instance_nearest_ext(x, y, obj, number, min_range, max_range, min_angle, max_angle)

x, y, and obj would be exactly the same as the existing instance_nearest.

number would be the number of objects to find. The result would be stored in an array, rather than a variable.

min_range would be the minimum range to check. If an object is closer than min_range, it will not be included in the results.

max_range would be the maximum range. Like min_range, things further than this value would be ignored. A value of 0 or negative means no maximum range.

min_angle and max_angle define an arc to be checked. Anything outside this arc is ignored.

This would allow users to get the nearest multiple objects, or the second closest object, or the nearest object within a specified area, without having to resort to using complicated scripts, and by making it a new, separate command, the original would still be available when the basic functionality is all that's needed.

 

[Alexx]

Then just make a script that does this and which returns a populated array with the results. I'm sure many people would find this very useful.

 

[MilesThatch]

I made a script that took at least half of those arguments. That's kind of what the scripts are for @Roderick.

 

[csanyk]

I made a script that took at least half of those arguments. That's kind of what the scripts are for @Roderick.

I'd buy that for a dollar.

 

[MilesThatch]

 

[Juju]

I'd buy that for a dollar.

That'll be one dollar, please. (Code completely untested.) Note that the "number" argument is redundant since you need to iterate over all instances anyway so you might as well return all the data.

///instance_nearest_ext_list( x, y, object, min range, max range, direction, angular range, strip distances )
// If "strip distances" is set to false, instance IDs can be recovered from the list by bitmasking with $FFFFFFFF
// @jujuadams 2016/12/26
// Do not redistribute without prior permission.
// With thanks to Ariak / @Mordwaith

var _x     = argument0;
var _y     = argument1;
var _obj   = argument2;
var _min   = argument3;
var _max   = argument4;
var _dir   = argument5;
var _range = argument6;
var _strip = argument7;

var _dir_x   =  dcos( _dir );
var _dir_y   = -dsin( _dir );
var _cos_rng =  dcos( _range );

var _list = ds_list_create();

with( _obj ) {
    var _dist = point_distance( _x, _y, x, y );
    if ( _dist < _min ) or ( _dist > _max ) continue;
    if ( _dir_x*( x - _x ) + _dir_y*( y - _y ) < _cos_rng * _dist ) continue;
    ds_list_add( _list, id + ( _dist << 32 ) );
}

ds_list_sort( _list, true );
if ( _strip ) for( var _i = ds_list_size( _list ) - 1; _i >= 0; _i-- ) _list[|_i] = _list[|_i] & $FFFFFFFF;
return _list;

 

[csanyk]

That'll be one dollar, please. (Code completely untested.) Note that the "number" argument is redundant since you need to iterate over all instances anyway so you might as well return all the data.

///instance_nearest_ext_list( x, y, object, min range, max range, direction, angular range, strip distances )
// If "strip distances" is set to false, instance IDs can be recovered from the list by bitmasking with $FFFFFFFF

var _x     = argument0;
var _y     = argument1;
var _obj   = argument2;
var _min   = argument3;
var _max   = argument4;
var _dir   = argument5;
var _range = argument6;
var _strip = argument7;

var _dir_x   =  dcos( _dir );
var _dir_y   = -dsin( _dir );
var _cos_rng =  dcos( _range );

var _list = ds_list_create();

with( _obj ) {
    var _dist = point_distance( _x, _y, x, y );
    if ( _dist < _min ) or ( _dist > _max ) continue;
    if ( _dir_x*( _x - x ) + _dir_y*( _y - y ) > _cos_rng * _dist ) continue;
    ds_list_add( _list, id + ( _dist << 32 ) );
}

ds_list_sort( _list, true );
if ( _strip ) for( var _i = ds_list_size( _list ) - 1; _i >= 0; _i-- ) _list[|_i] = _list[|_i] & $FFFFFFFF;
return _list;

This looks good. Tell me where to send it, and I'll totally send you a dollar!

Could you explain these two lines:

if ( _dir_x*( _x - x ) + _dir_y*( _y - y ) > _cos_rng * _dist ) continue;

if ( _strip ) for( var _i = ds_list_size( _list ) - 1; _i >= 0; _i-- ) _list[|_i] = _list[|_i] & $FFFFFFFF;

I get what they're doing, but it'd be nice to have a better understanding of how.

Also, if I understand this code correctly, it's assumed to be called by the instance that is doing the check for the nearest, is that right?

 

[Juju]

Could you explain these two lines:

I sure can!

if ( _strip ) for( var _i = ds_list_size( _list ) - 1; _i >= 0; _i-- ) _list[|_i] = _list[|_i] & $FFFFFFFF;

The distance and instance IDs are packed into the ds_list by bitshifting the distance value to the left (i.e. making it most-significant for the sorting operation). In order to get the instance IDs back out of the list, you need to remove the distance values. The easiest way to do that is with a bitmask that selects the 32 least significant bits.

if ( _dir_x*( _x - x ) + _dir_y*( _y - y ) > _cos_rng * _dist ) continue;

This is a bit more complex. It's based on the dot product which gives us a rule linking two vectors ( a; b ), the length of those two vectors ( |a|; |b| ), and the angle between them ( theta ):

a . b = |a| |b| cos( theta )

We set one vector to represent the "ideal" direction, as defined by argument5. We then use the vector from (argument0,argument1) to the target instance as the other vector. We know vector a is of length 1 and the length of vector b is simply the distance between the point and the target instance's position. This gives us a simple equation:

a . b = |b| cos( theta )

Our value of theta wants to be less than the given range, as defined by argument6, but doing trigonometry is expensive and we don't want that. If we look at the way a cosine curve goes, we can see that all values of theta greater than a target range will have a smaller cosine value. This means if our dot product is larger than cos( theta ), we know the angle between the two vectors is within the desired range! Lovely.

a . b > |b| cos( range )
IF the angle between a and b is less than range

We substitute in for a and b with the appropriate variables and we can also pre-compute cos( range ).

Now... you may have noticed that my inequality is the wrong way round in the actual code. This is because I got the subtraction operation ass-backwards and decided to reverse the inequality rather than the subtraction. I'm pretty ill right now so who knows why I did that.

Edit: Nope, I was just wrong.

Also, if I understand this code correctly, it's assumed to be called by the instance that is doing the check for the nearest, is that right?

Nope, it's agnostic.

That this script creates a new list every time is actually kind of crap. You'd probably want to have an "existing list" argument so you're not constantly creating/destroying a list whenever you want to use the script.

 

[csanyk]

if ( _strip ) for( var _i = ds_list_size( _list ) - 1; _i >= 0; _i-- ) _list[|_i] = _list[|_i] & $FFFFFFFF;

The distance and instance IDs are packed into the ds_list by bitshifting the distance value to the left (i.e. making it most-significant for the sorting operation). In order to get the instance IDs back out of the list, you need to remove the distance values. The easiest way to do that is with a bitmask that selects the 32 least significant bits.

Very clever! So is it known that instance id's shall never exceed 32 bits? Or is that a potential problem if it does?

if ( _dir_x*( _x - x ) + _dir_y*( _y - y ) > _cos_rng * _dist ) continue;

This is a bit more complex. It's based on the dot product which gives us a rule linking two vectors ( a; b ), the length of those two vectors ( |a|; |b| ), and the angle between them ( theta ):

a . b = |a| |b| cos( theta )

We set one vector to represent the "ideal" direction, as defined by argument5. We then use the vector from (argument0,argument1) to the target instance as the other vector. We know vector a is of length 1 and the length of vector b is simply the distance between the point and the target instance's position. This gives us a simple equation:

a . b = |b| cos( theta )

Our value of theta wants to be less than the given range, as defined by argument6, but doing trigonometry is expensive and we don't want that. If we look at the way a cosine curve goes, we can see that all values of theta greater than a target range will have a smaller cosine value. This means if our dot product is larger than cos( theta ), we know the angle between the two vectors is within the desired range! Lovely.

a . b > |b| cos( range )
IF the angle between a and b is less than range

We substitute in for a and b with the appropriate variables and we can also pre-compute cos( range ).

Now... you may have noticed that my inequality is the wrong way round in the actual code. This is because I got the subtraction operation ass-backwards and decided to reverse the inequality rather than the subtraction. I'm pretty ill right now so who knows why I did that.

This will take me some time for me to process, but I basically follow what you're saying. I do have a question: does this code handle angle ranges that wrap between 0 and 360 correctly? For example, if I want the range to go from, say, 315-45 deg, can this script handle that correctly? Will it handle numbers outside of that range, or do I have to normalize angles <0 or >360 to get them to be a positive value between 0-360?

I will have to try this script out and test a few experimental cases with it, but I think it will be very handy.

 

[Juju]

Very clever! So is it known that instance id's shall never exceed 32 bits? Or is that a potential problem if it does?

Thank @Ariak for that one. 2^32 is an absurdly large number. I'm not sure if GM is even capable of going up that far without breaking. It's large enough that you're not going to run into that bug too often.

does this code handle angle ranges that wrap between 0 and 360 correctly?

Yes it does, that's implicit in the way the dot product works.

You don't need to normalise / check / correct / wrap the input direction value at all (though a range of over 180 degrees might break it).

 

[Ariak]

@csanyk : I did a little bit of maths on the Instance ID thing. As juju said, GM prolly cannot handle it anyway - but just to give you an idea of the absurd amount of instances you'd need to create before it falls apart: if you spawn 1000 instances @ 60 fps the system goes into meltdown after ~20h of consecutive gameplay. Switching rooms will reset the instance ID counter. Maths here:

Spoiler: Math things....

For performance test and a solution to the id ... "issue".. for lack of a better word (still ~ twice as fast as a priority que) see here: https://forum.yoyogames.com/index.p...ested-list-grid-binary-list.13425/#post-89320


@Juju you'll need to flip your angle check.

( _dir_x*( _x - x ) + _dir_y*( _y - y ) > _cos_rng * _dist )
flip logic of delta x,y and cos_rng to smaller
( _dir_x*( x - _x ) + _dir_y*( y - _y ) < _cos_rng * _dist)

Left is original, right is fixed. Angle of 90, vision cone 30.

Spoiler: Picture Proof

Also for those who like easier to digest code - this does exactly the same thing but is slightly slower with GMS2 YYC.

if ( _dist < _min ) || ( _dist > _max ) || abs(angle_difference(_dir,point_direction(_x,_y,x,y)))>_range continue;

Finally we can prolly squeeze a last drop of performance out of the script by checking max distance before min dis. realistically there should be more instances outside of a given range than inside. this is terribly minor though.

 

[Juju]

you'll need to flip your angle check.

No way man it's an exclusion angle <_< >_>

Cheers for actually testing it! I'll edit the original post.