GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#21 2020-08-11 01:49:12

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: collision_cone_list

redeyesmaster wrote:

Your new method seems like it will only support up to 90 degree.

Bah! You are right.

Last edited by xot (2020-08-11 01:49:55)


Abusing forum power since 1986.

Offline

#22 2020-08-11 01:50:15

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

The best part about this new method is, if they want more then 180 degrees we could just remove 180 from the cone_angle then anything in the circle that either box collides with would be passed as valid. Saves a ton of time.

Offline

#23 2020-08-11 01:54:48

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

Offline

#24 2020-08-11 01:58:28

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: collision_cone_list

I haven't tried you project but what I've done still doesn't work right. If the sprite being collided with is large enough, it can still collide with all three checks on the opposite side of the cone. It may need to cull anything behind the cone. I need to think about this some more but I'm done for the night.

F6NE1Ap.png

Last edited by xot (2020-08-11 01:58:59)


Abusing forum power since 1986.

Offline

#25 2020-08-11 02:13:56

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

I see what you mean...
SFfvJwq.png

I suppose we could make the image_yscale dynamic based off angle 1:1 = <=90, and 1:2 for anything above 90.

Because if we cull anything behind us, we would possibly remove a potential pass.

...yeah I've been working on cone collision for basically 2 and a half days now. I'm gonna let it fester while i try to come up with a solution.

Offline

#26 2020-08-11 14:55:23

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

I mean, at this point we're already using the with all function, as well as the sprite method. Why not just grab the circle then double check with your collision triangle?

Ideally we could do any angle under 180. By making a formula to calculate the triangle.
J1e8VoU.png

Though this of course means anything 180 and over wouldnt be possible. It could also cause issues with scaling the right triangles up that far, for instance if you have 179 degrees.
qoepkuB.png

So I suggest we take the vertex solution from the original code to help calculate each triangle collision, so for each 90 degrees we have an additional triangle.
tqlbIlz.png

Though this will also mean we will need to extend the triangles slightly to make sure they encompass the entire circle, which since we know the max distance of A, and the two angles, then calculating the rest wont be hard.
YPU2vDX.png


The real question is will this cause an unstable framerate, scaling the rectangles in our current version only needs to happen once, although scaling a triangle twice per vertex (maximum of 4) and having collision checks for each may lead to issues. Though in this one particular case we may be able to cut back on the number of times we need to scale and rotate by making the sprite's origin one of the 45 degree angles, so once we calculate the number of vertex we would scale once, check, then multiply the x scale by -1, check, then rotate and multiply by -1 again.

Which would lead to us only needing to do an initial scale, a max of 4 rotates, and 8 xscale flips.
XnT9Mvi.png

And come to think of it, we could even cut those numbers and calculations down even further. We would only ever need to know the cone's vertex angle, and length of side A, We can calculate side B from those, then rotate the same triangle around the already checked circle. only having to rescale it once.
CO3xnDZ.png

I'm almost positive that last one will be our best solution. It would never return a false positive, or fail a collision. The only question is how fast is that check.

Offline

#27 2020-08-11 18:14:11

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

The Triangle method seems to work quite well. although doesnt handle the massive amount too well.
https://i.gyazo.com/db113745212187ee2c2 … e14474.mp4
KjUFKWj.png


Results:

12289 objects:
The un-optimized version, which continues to check object's even if they failed the circle pass.
2200 successful collisions
20%, 3/15 fps

Optimized Version
2200 successful collisions
20%, 3/15 fps


3073 objects:
un-optimized version
15%, 8/53 fps

Optimized Version
33%, 18/53 fps

769 objects:
un-optimized version
136 successful collisions
7%, 33/450 fps

Optimized Version
136 successful collisions
17%, 80/450 fps

1 Object:
un-optimized version
71%, 1000/1400 fps

Optimized Version
64%, 900/1400 fps


The stats seems to show that most of it's lag is coming from the calculations in the code and not entirely from the object collisions them selves. Obviously the over all lag it due to the number of objects, but even our best result is still dropping 30% of frames, give or take. The section of the code I was turning off for the max frame tests was the following:

Expandvar dir = cone_direction;
var vertices = ceil(cone_angle/45)
var ang = cone_angle/vertices  //each triangle will be less then 45 degrees, each one perfectly spaced
var image_width = cone_radius/sin(degtorad(90-ang))*sin(degtorad(ang))

image_xscale = image_width/(sprite_get_width(sprite_index)-1);
image_yscale = cone_radius/(sprite_get_height(sprite_index)-1);

image_angle = cone_direction-90

var list = ds_list_create()
with (object1) {
    var circle_include = false;
    //  Circle Set
    image_blend = c_white;
    if (collision_circle(other.x, other.y, other.cone_radius, id, true, false)){
        //image_blend &= $FFFFFF;
        circle_include = true;
    }else{
        //image_blend &= $777777
        }
    //  Triangle Set
    if circle_include
    {
      for (var i = vertices; i > 0; i--)
      {
        other.image_angle = dir - other.cone_angle/2 + ang*i - 90; 
        if (place_meeting(x, y, other.id)){
            //image_blend &= $FF33FF
            if circle_include ds_list_add(list, id);
            break;
        }else{
            //image_blend &= $FFFFFF;
        }
      }
    }
}

//cone_direction += 1;


show_debug_message("ds_list_size(list) = "+string(ds_list_size(list)))
while !ds_list_empty(list)
{
  list[| 0].image_blend = c_green
  ds_list_delete(list, 0)
}
ds_list_destroy(list)

Ideas:
- I know for statements are extremely poor, so this could be changed to a while.
- We may also want to have an initial check for the closest objects distance, based off bbox margins and x,y. or just see if the object exists at all might suffice.
- I know we could cut back on the number of sprite collision checks if we just replace every full 90 degrees with a square, possibly making that image 2 of the sprite. Though I'm not to sure if switching back and forth so repeatedly would be all that helpful. I suspect switching images and re scaling is worse then an extra collision check.
- When the cone's angle is 90 degrees or more we would only need squares, which would definitely remove a ton of lag due to precise checking which is required with triangles. But bounding box should saves a good portion of latency.
UYH93qS.png

[EDIT]
I know a few of the photos show false positives but those photos were taken when the triangle was scaled up from 16,16. Once I set the triangle to be 1/3 the cone diameter, everything seems to work better, there is probably an optimally efficient way to scale and cache the triangles but it eludes me. I'll likely do some testing with that system with 1,1 objects and find the best system for scaling, I would imagine something like the radius/view_width but im not positive about that.

Last edited by redeyesmaster (2020-08-11 20:04:43)

Offline

#28 2020-08-11 20:09:55

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

Fun fact, we get about double the frames just by adding,

Expandif (rectangle_in_triangle(bbox_left,bbox_top,bbox_right,bbox_bottom, other.x,other.y,x2,y2,x3,y3) > 0)
            circle_include = true;

Obviously this wouldnt be a proper check as it's only handling the rectangle around the sprite, but that will cull out all of the objects in the circle, behind the cone. I'll have to add this to your 2 squares method and see how that turns out. could be the best method.

[EDIT] Example:
AO1fSi8.png
Wl0nD9p.png

Last edited by redeyesmaster (2020-08-11 21:20:35)

Offline

#29 2020-08-11 22:57:58

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

Reverse Culling method:

79 degrees:
VPdG5Hv.png

<45 degrees:
64CjJdY.png

Optimized:
40%, 6/15 fps
qdaYwu2.png

67%, 36/53
Video: https://gyazo.com/158b66297830024e49b8b2a784cd15e7
jCDHpDE.png

35%, 159/450 fps
HJIx79k.png

107%, 1500/1400 fps  ...wut?
5dMZKKh.png


I think we have our winner, it's extremely well optimized and some how even scored higher then possible on the 1 object test. With out collision code it gets 1400 fps; and with it, it gets 1500. Not sure how that work but I'll mark it off as fps fluctuation. I'll convert this into a commented script tomorrow night and post the final version as a comment to this page.

With the prec value for the script I'll likely return anything before the rotating rectangle check for prec is set to false. If it wasnt for a few key set ups we wouldnt need that check. The only way I can imagine a false check would require something similar to this, though it shouldn't matter that much due to the extremely low likely hood of this:

[EDIT]This top left one would fail actually.
O9ddeZD.png

Which if I'm being totally honest, if you built a giant object so large that it can encompass the cone, and you think it shouldn't have, you probably should have made it different pieces.  Because other then it being large these few deviations are with in acceptable bounds for most projects. Like if I was doing some pvp and I was that close to them I would probably have assumed it was a hit too.

Last edited by redeyesmaster (2020-08-11 23:50:02)

Offline

#30 2020-08-15 22:54:22

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

I finished up the script today just doing some bug tests before it's published.
https://i.gyazo.com/84132989ae8a2312e67 … c7f292.mp4

Offline

#31 2020-08-15 23:44:24

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

The finished code:

Expand///   collision_cone_list(x, y, direction, length, angle, obj, prec, notme);
//  
//  Returns: ds_list
//  
//  x         - the x point of the cone
//  y         - the y point of the cone
//  direction - direction from x,y of the cone expands from
//  length    - the total distance the cone reaches, similar to the radius of a circle
//  angle     - The angle width of the cone
//  prec      - Whether the check is based on pixel-perfect collisions (true = slow) or its bounding box in general (false = fast). 
//  obj       - The object to check for instance collisions.
//  notme     - Whether the calling instance, if relevant, should be excluded (true) or not (false). 
//  
/// GMLscripts.com/license

///NOTE: make sure to have an object named o_sensor in your project, or below change the variable to what ever you wish.

var xx = argument0
var yy = argument1
var cone_direction = argument2
var cone_radius = argument3
var cone_angle = argument4
var object = argument5
var prec = argument6
var notme = argument7


///change this variable to what ever you would like the sensor object to be.
var sensor_object_index = o_sensor


if (notme){
  var notme_id = id;
}else{
  var notme_id = -1
}


//  Create Collision Mask, 1x2 pixel rectangle
if !variable_global_exists("collision_cone_list_sprite")
{
  var surf = surface_create(1,2);
  surface_set_target(surf);
  draw_clear_alpha(c_white, 1);
  surface_reset_target();
  global.collision_cone_list_sprite = sprite_create_from_surface(surf, 0, 0, 1, 2, false, false, 1, 1);
  sprite_collision_mask(global.collision_cone_list_sprite, false, 0, 0, 0, 0, 1, 1, 0);
  surface_free(surf);
}

//assign the sensor object
if (prec || (cone_angle >= 180))
{
  if instance_exists(sensor_object_index){
    var sensor = instance_nearest(xx,yy,sensor_object_index);
  }else{
    var sensor = instance_create(xx,yy,sensor_object_index);
    // Set Collision Mask
    sensor.sprite_index = global.collision_cone_list_sprite;
    sensor.mask_index = global.collision_cone_list_sprite;
  }
  sensor.image_xscale = cone_radius;
  sensor.image_yscale = cone_radius;
}


if (cone_angle < 180)  // calculate the points of the triangle check
{  //if the angle is larger then 179.9 this would hinder us
  var angled_length = cone_radius/sin(degtorad(90-cone_angle/2))*sin(degtorad(90));
  var x2 = x+lengthdir_x(angled_length,cone_direction-cone_angle/2);
  var y2 = y+lengthdir_y(angled_length,cone_direction-cone_angle/2);
  var x3 = x+lengthdir_x(angled_length,cone_direction+cone_angle/2);
  var y3 = y+lengthdir_y(angled_length,cone_direction+cone_angle/2);
}


//create the list to return
var list = ds_list_create()


with (object) {
  //  Circle Check
  if (collision_circle(xx, yy, cone_radius, id, prec, false)) && (notme_id != id)
  {
    //Triangle Check
    if (cone_angle >= 180) || (rectangle_in_triangle(bbox_left,bbox_top,bbox_right,bbox_bottom, xx,yy,x2,y2,x3,y3) > 0)
    {
      if prec || (cone_angle >= 180)
      {
          if (cone_angle <= 180){
            //  Plane Check 1
            sensor.image_angle = cone_direction - cone_angle/2 -90;
            if (place_meeting(x, y, sensor.id)){
              //  Plane Check 2
              sensor.image_angle = cone_direction + cone_angle/2 +90;
              if (place_meeting(x, y, sensor.id)){
                // Finalize
                ds_list_add(list, id);
              }
            }
            
          }else{  //  if the angle is larger then 180
            var include = false;
            if (cone_angle >= 360){
              //if angle is 360 just add everything in the circle
              var include = true;
            }else{
              //  Plane Check 1
              sensor.image_angle = cone_direction - cone_angle/2 -90;
              if (place_meeting(x, y, sensor.id)) var include = true;
              //  Plane Check 2
              sensor.image_angle = cone_direction + cone_angle/2 +90;
              if (place_meeting(x, y, sensor.id)) var include = true;
            }
            //  Finalize
            if (include) ds_list_add(list, id);
          }
      }else{ //if prec = false
        ds_list_add(list, id)
      }
    }
  }
}
if (instance_exists(sensor_object_index)) instance_destroy(sensor);
return list

Thanks for all the help and allowing me to also use this board basically as a rubber ducky. I really hope people can make use of this code.

Last edited by redeyesmaster (2020-08-15 23:52:28)

Offline

#32 2020-08-16 00:31:07

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

As a bonus here is the collision_cone, with out the returning of a list.

Expand///   collision_cone(x, y, direction, length, angle, obj, prec, notme);
//  
//  Returns: Returns: Instance id or noone 
//  
//  x         - the x point of the cone
//  y         - the y point of the cone
//  direction - direction from x,y of the cone expands from
//  length    - the total distance the cone reaches, similar to the radius of a circle
//  angle     - The angle width of the cone
//  prec      - Whether the check is based on pixel-perfect collisions (true = slow) or its bounding box in general (false = fast). 
//  obj       - The object to check for instance collisions.
//  notme     - Whether the calling instance, if relevant, should be excluded (true) or not (false). 
//  
/// GMLscripts.com/license

///  NOTE: make sure to have an object named o_sensor in your project,
//     or below change the variable to what ever you wish.

var xx = argument0
var yy = argument1
var cone_direction = argument2
var cone_radius = argument3
var cone_angle = argument4
var object = argument5
var prec = argument6
var notme = argument7


///change this variable to what ever you would like the sensor object to be.
var sensor_object_index = o_sensor


if (notme){
  var notme_id = id;
}else{
  var notme_id = -1
}


//  Create Collision Mask, 1x2 pixel rectangle
if !variable_global_exists("collision_cone_sprite")
{
  var surf = surface_create(1,2);
  surface_set_target(surf);
  draw_clear_alpha(c_white, 1);
  surface_reset_target();
  global.collision_cone_sprite = sprite_create_from_surface(surf, 0, 0, 1, 2, false, false, 1, 1);
  sprite_collision_mask(global.collision_cone_sprite, false, 0, 0, 0, 0, 1, 1, 0);
  surface_free(surf);
}

//assign the sensor object
if (prec || (cone_angle >= 180))
{
  if instance_exists(sensor_object_index){
    var sensor = instance_nearest(xx,yy,sensor_object_index);
  }else{
    var sensor = instance_create(xx,yy,sensor_object_index);
    // Set Collision Mask
    sensor.sprite_index = global.collision_cone_sprite;
    sensor.mask_index = global.collision_cone_sprite;
  }
  sensor.image_xscale = cone_radius;
  sensor.image_yscale = cone_radius;
}


if (cone_angle < 180)  // calculate the points of the triangle check
{  //if the angle is larger then 179.9 this would hinder us
  var angled_length = cone_radius/sin(degtorad(90-cone_angle/2))*sin(degtorad(90));
  var x2 = x+lengthdir_x(angled_length,cone_direction-cone_angle/2);
  var y2 = y+lengthdir_y(angled_length,cone_direction-cone_angle/2);
  var x3 = x+lengthdir_x(angled_length,cone_direction+cone_angle/2);
  var y3 = y+lengthdir_y(angled_length,cone_direction+cone_angle/2);
}


with (object) {
  //  Circle Check
  if (collision_circle(xx, yy, cone_radius, id, prec, false)) && (notme_id != id)
  {
    //Triangle Check
    if (cone_angle >= 180) || (rectangle_in_triangle(bbox_left,bbox_top,bbox_right,bbox_bottom, xx,yy,x2,y2,x3,y3) > 0)
    {
      if prec || (cone_angle >= 180)
      {
          if (cone_angle <= 180){
            //  Plane Check 1
            sensor.image_angle = cone_direction - cone_angle/2 -90;
            if (place_meeting(x, y, sensor.id)){
              //  Plane Check 2
              sensor.image_angle = cone_direction + cone_angle/2 +90;
              if (place_meeting(x, y, sensor.id)){
                // Finalize
                return id;
              }
            }
            
          }else{  //  if the angle is larger then 180
            var include = false;
            if (cone_angle >= 360){
              //if angle is 360 just add everything in the circle
              var include = true;
            }else{
              //  Plane Check 1
              sensor.image_angle = cone_direction - cone_angle/2 -90;
              if (place_meeting(x, y, sensor.id)) var include = true;
              //  Plane Check 2
              sensor.image_angle = cone_direction + cone_angle/2 +90;
              if (place_meeting(x, y, sensor.id)) var include = true;
            }
            //  Finalize
            if (include){
              return id;
            }
          }
      }else{ //if prec = false
        return id;
      }
    }
  }
}
if (instance_exists(sensor_object_index)) instance_destroy(sensor);
return noone

This is not optimized, for instance if the angle is 360 it could simply do a circle check with out all the other checks, although other then that it would work the exact same as the cone list script.

Offline

#33 2020-08-17 16:00:37

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: collision_cone_list

You have really been busy! I'm sorry I dropped out of the conversation for a couple of days. I'll try to check these out tonight.


Abusing forum power since 1986.

Offline

#34 2020-08-18 01:50:05

redeyesmaster
Member
Registered: 2020-08-09
Posts: 43

Re: collision_cone_list

xot wrote:

You have really been busy! I'm sorry I dropped out of the conversation for a couple of days. I'll try to check these out tonight.

Lol, busy is an understatement. When I'm building code for others to use I try my best to get the most efficient code possible, as it's unlikely it'll ever be updated. Also the use of o_sensor is annoying to me as it doesn't allow a drop in an use experience. really wish the creation of objects wasn't removed.

Speaking of we should probably make sure all the collision scripts which use objects are all using the same object name. I never checked what the others were using.

Offline

Board footer

Powered by FluxBB