What is the most efficient way of detecting objects in Range?

[Petrik33]

So, Hello everybody! In my platformer game I have different entities that need detection code in their behaviour like The Tower with Ranged Attack, so I wonder which function is it better to use to do that? This is what I personally do as a beginner:

attack_cooldown+=attack_speed;
if(floor(attack_cooldown)>=attack_time)
{
    var in_range = ds_list_create();
    var front_range = attack_front_range;
    var back_range = attack_back_range;

    if(image_xscale = -1)
    {
        front_range = attack_back_range;
        back_range = attack_front_range
    }

    var number_in_range = collision_rectangle_list(x- back_range,FLOOR_Y - 55,x+front_range,FLOOR_Y,enemy_parent,0,true,in_range,0);

    //Here I could have collision_rectangle instead, so just instead
    //Instead of ds_list it would return just one instance

    if(number_in_range = 0)
    {
        ds_list_destroy(in_range);
        return noone
    }
    else return in_range
}
else return noone

So the question relates to the code with collision_ractangle function: is there any better way of detecting objects in range than that?
Edit: Found a mistake in the code

 

[Yal]

If you specifically only need one target, instance_nearest gives you the nearest instance of a particular object type - so you could replace the entire code with
return instance_nearest(x,y,enemy_parent).


EDIT: Oh, there's a max range... it gets a bit more complicated, then, but not much:

var n = instance_nearest(x,y,enemy_parent);
if(!n){
  return noone
}
//Now we know it exists since it's a valid ID
if(n.x > x - attack_range_back && n.x < x + attack_range_front){
  return n;
}
else{
  return noone;
}

 

[Petrik33]

If you specifically only need one target, instance_nearest gives you the nearest instance of a particular object type - so you could replace the entire code with
return instance_nearest(x,y,enemy_parent).


EDIT: Oh, there's a max range... it gets a bit more complicated, then, but not much:

var n = instance_nearest(x,y,enemy_parent);
if(!n){
  return noone
}
//Now we know it exists since it's a valid ID
if(n.x > x - attack_range_back && n.x < x + attack_range_front){
  return n;
}
else{
  return noone;
}

Yeah, thank you, looks simple, but I am not really sure about the background of such functions like the instance_nearest, it seems to be inefficient for me, but I don't really know, so I will try it, againg, thank you!

 

[rytan451]

instance_nearest is probably the fastest possible method. It's certainly faster than collision_rectangle_list.

 

[Deleted member 45063]

Just to provide an alternative (although instance_nearest might be enough for you), you can also maintain a priority queue with the distances from any enemy to a particular tower instance (assuming these are static). Something like:

// Tower create
enemy_distances = ds_priority_create();

// Tower cleanup
ds_priority_destroy(enemy_distances);

// Enemy create
with (obj_tower) {
  ds_priority_add(enemy_distances, other.id, point_distance(x, y, other.x, other.y));
}

// Enemy step
if (enemy_position_got_changed) {
  with (obj_tower) {
    ds_priority_change_priority(enemy_distances, other.id, point_distance(x, y, other.x, other.y));
  }
}

// Enemy cleanup
with (obj_tower) {
  ds_priority_delete_value(enemy_distances, other.id);
}

This would mean that any time the enemy changes positions it updates the distance in all of the towers' priority queue so that a simple lookup yields the closest one:

// Tower step or something
if (!ds_priority_empty(enemy_distances)) {
  var target = ds_priority_find_min(enemy_distances);
  var distance = ds_priority_find_priority(enemy_distances, target);
}

Not sure about about the performance when compared with instance_nearest for this case, but the advantage is that you always have a ready queue with the distances. You could also tweak it so that the priority queue only has the instances below a certain threshold, etc

 

[Petrik33]

Just to provide an alternative (although instance_nearest might be enough for you), you can also maintain a priority queue with the distances from any enemy to a particular tower instance (assuming these are static). Something like:

// Tower create
enemy_distances = ds_priority_create();

// Tower cleanup
ds_priority_destroy(enemy_distances);

// Enemy create
with (obj_tower) {
  ds_priority_add(enemy_distances, other.id, point_distance(x, y, other.x, other.y));
}

// Enemy step
if (enemy_position_got_changed) {
  with (obj_tower) {
    ds_priority_change_priority(enemy_distances, other.id, point_distance(x, y, other.x, other.y));
  }
}

// Enemy cleanup
with (obj_tower) {
  ds_priority_delete_value(enemy_distances, other.id);
}

This would mean that any time the enemy changes positions it updates the distance in all of the towers' priority queue so that a simple lookup yields the closest one:

// Tower step or something
if (!ds_priority_empty(enemy_distances)) {
  var target = ds_priority_find_min(enemy_distances);
  var distance = ds_priority_find_priority(enemy_distances, target);
}

Not sure about about the performance when compared with instance_nearest for this case, but the advantage is that you always have a ready queue with the distances. You could also tweak it so that the priority queue only has the instances below a certain threshold, etc

Yeah, good suggestion, thank you for that!

 

[TheouAegis]

The only thing faster would be comparing x-coordinates if this is a side-scroller, or comparing y-coordinates if it's a vertical scroller, with one-dimensional movement.