GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2020-08-09 21:04:30

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

collision_cone_list

Expand///   collision_cone_list(x, y, direction, length, angle, vertices, obj)
//  
//  Returns: ds_list
//
//  Make sure to have an object named o_sensor in the project
//    because object_add() is obsolete.
//  
//  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 width of the cone
//  vertices  - The cone is made of several triangles, this is how many triangles will be drawn to achieve the effect, the bigger the number of "triangles", the more detailed the cone will be, 12 is a good start value
//                   0 will auto calculate.
//  obj       - The object to detect collision with.
//  
/// GMLscripts.com/license

var xx=0,yy=0,dir=argument2-(argument4/2),lng=argument3,ang=argument4,steps=argument5, prmitive_array;

if (steps = 0) {steps = ang/15} //3 triangles per 45 degrees

//calculate how big the cone will be
var surf_left   = 0;
var surf_right  = 0;
var surf_top    = 0;
var surf_bottom = 0;

prmitive_array[0,0] = 0;
prmitive_array[0,1] = 0;

for(i=0; i<=steps; i++)
{
  var _xx = xx+lengthdir_x(lng,dir+(ang*i/steps));
  var _yy = yy+lengthdir_y(lng,dir+(ang*i/steps));
  
  prmitive_array[i+1,0] = _xx
  prmitive_array[i+1,1] = _yy
  
  var surf_left   = min(surf_left, _xx)
  var surf_right  = max(surf_right, _xx)
  var surf_top    = min(surf_top, _yy)
  var surf_bottom = max(surf_bottom, _yy)
}

x_off = abs(surf_left)
y_off = abs(surf_top)


//once the cone's size is calculated and then vertex's are ready to be drawn
//make the surface
var surf_col = surface_create(round(surf_right - surf_left), round(surf_bottom - surf_top))
surface_set_target(surf_col)


///once the surface is created, actually start work on drawing the primitive
var pr=pr_trianglefan;
draw_primitive_begin(pr);

draw_vertex(prmitive_array[0,0]+x_off, prmitive_array[0,1]+y_off);
       
for(i=0; i<=steps; i++)
{
  var _xx = prmitive_array[i+1,0]+x_off
  var _yy = prmitive_array[i+1,1]+y_off
  
  draw_vertex(_xx,_yy);
}

draw_primitive_end();
surface_reset_target();

// create the sprite
var spr = sprite_create_from_surface(surf_col, 0, 0, round(surf_right - surf_left), round(surf_bottom - surf_top), 0, 0, x_off, y_off);
sprite_collision_mask(spr, 0, 1, 0, 0, 0, 0, 0, 0);
//free the surface
surface_free(surf_col);


//create the object and apply variables
var col_sensor = instance_create(argument0,argument1,o_sensor)

var object = argument6

with col_sensor
{
  sprite_index = spr
  var collision_list = ds_list_create()
  
  //cycle through all of the collided objed deactivating them
  while (place_meeting(x, y, object))
  {
    var obj_col = instance_place(x,y, object)
    ds_list_add(collision_list, obj_col)
    instance_deactivate_object(obj_col)
  }
  
  //when finished re activate all collided object in list
  if not ds_list_empty(collision_list)
  {
    for (var i = ds_list_size(collision_list)-1; i >= 0; i--)
    {
      instance_activate_object(collision_list[| i])
    }
  }
}

sprite_delete(spr)
instance_destroy(col_sensor)


return collision_list

Offline

#2 2020-08-09 22:38:55

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

Re: collision_cone_list

Thanks for the interesting script and welcome to the forums.

The sprite creation aspect of this makes it relatively slow, though it may be acceptable in many cases.

With some caching this function could be a lot faster at the expense of some memory if we observe a couple of things:

  • All circular sectors ("cones") of the same angle are geometrically similar.

  • All similar circular sectors can be made identical with translation, rotation, and scaling.

When the function is first called, a persistent singleton collision object can be created and a generic collision mask generated. It will be created with the given angle and desired precision. The collision object is positioned, rotated, and scaled to perform the requested collision checks. At the end of the function the collision object is not deleted and the collision mask is saved to the cache. The next time the function is called, it uses the existing collision object. If the angle and precision matches one in the cache, it uses the existing collision mask, otherwise a new one is created.

Generally, the mask itself would be created at a dimension (precision) that is suitable for most collisions and that precision would always be used. Smaller collision areas will be unaffected by scaling the collision mask. Areas larger than the dimensions of the collision mask will be less precise due to "pixelation" errors (but probably not in a noticeable way unless they are greatly scaled up). It is probably desirable to do the initialization when the game starts rather than during game play, if a common precision and the required angles are known at that time. All that said, this caching system could be very wasteful with memory if the function is called with many different angles and dimensions.

This strategy is similar to how my collision_triangle() script works (though it needs some updating). In that case only one triangular collision mask needs to be created because any triangle can be constructed from two right triangles positioned, rotated, and scaled appropriately. Unfortunately circular sectors aren't as flexible.

I'm not saying the above must be done but it is worth considering.


Abusing forum power since 1986.

Offline

#3 2020-08-10 00:19:45

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

Re: collision_cone_list

Yeah that's where i got the main idea from, i was able to optimize this script a bit by using a non-surface approach, though it still isn't optimized enough for my purposes. Would love to get some assistance in improving it further.

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 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

var xx=argument0,yy=argument1,dir=argument2-(argument4/2),lng=argument3,ang=argument4, object = argument5, prec = argument6, notme = argument7;

//grab everything with in a radious,
//we use this method so we dont need to use "all" commands
var circle_list = ds_list_create()
var obj_col = collision_circle( xx, yy, lng, object, prec, notme)
while obj_col != noone
{
  ds_list_add(circle_list, obj_col)
  instance_deactivate_object(obj_col)
  var obj_col = collision_circle( xx, yy, lng, object, prec, notme)
}
//when finished re activate all collided object in list
if not ds_list_empty(circle_list)
{
  for (var i = ds_list_size(circle_list)-1; i >= 0; i--)
  {
    instance_activate_object(circle_list[| i])
  }
}



var collision_list = ds_list_create()

//if we want pixel-perfect collisions check the lines aswell
if prec
{
  //check left side
  var x2 = xx+lengthdir_x(lng, dir)
  var y2 = yy+lengthdir_y(lng, dir)
  var obj_col = collision_line( xx, yy, x2, y2, object, prec, notme)
  while obj_col != noone
  {
    ds_list_add(collision_list, obj_col)
    instance_deactivate_object(obj_col)
    ds_list_delete(circle_list, ds_list_find_index(circle_list, obj_col))
    var obj_col = collision_line( xx, yy, x2, y2, object, prec, notme)
  }
  //check right side
  
  var x2 = xx+lengthdir_x(lng, dir+ang)
  var y2 = yy+lengthdir_y(lng, dir+ang)
  var obj_col = collision_line( xx, yy, x2, y2, object, prec, notme)
  while obj_col != noone
  {
    ds_list_add(collision_list, obj_col)
    instance_deactivate_object(obj_col)
    ds_list_delete(circle_list, ds_list_find_index(circle_list, obj_col))
    var obj_col = collision_line( xx, yy, x2, y2, object, prec, notme)
  }
}


//now iterate through the circle list adding anyone landing with in the bounds of the angle
while not ds_list_empty(circle_list)
{
  var test_obj = circle_list[| 0]
  
  var ox = test_obj.bbox_left+(test_obj.bbox_right-test_obj.bbox_left)
  var oy = test_obj.bbox_top+(test_obj.bbox_bottom-test_obj.bbox_top)
  
  var odir = point_direction(xx, yy, ox, oy)
  if (abs(angle_difference(dir+(ang/2), odir)) <= ang/2) ds_list_add(collision_list, test_obj);
  
  ds_list_delete(circle_list, 0)
}


ds_list_destroy(circle_list)






//when finished re activate all collided object in list
if not ds_list_empty(collision_list)
{
  for (var i = ds_list_size(collision_list)-1; i >= 0; i--)
  {
    instance_activate_object(collision_list[| i])
  }
}



return collision_list

I'm just on a beater laptop which i use for testing to optimize my code so it's run-able on even potatoes, although this script is still dropping the average fps down 300 frames. Assistance would be greatly appreciated.

Last edited by redeyesmaster (2020-08-10 00:20:20)

Offline

#4 2020-08-10 01:13:47

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

Re: collision_cone_list

That sort of approach can work and is faster but it presumes an object's collision mask is relatively solid. You've taken care to test with the center of the bounding box, which is better than the origin (used by most similar approaches I've seen), but it is still susceptible to false positives and negatives.

u2T64Au.png

These are contrived examples but they illustrate the potential problems.

Years ago on the old GMC forums there was a topic where many of us tried to solve the triangle collision problem. All of the solutions had trade offs in performance and accuracy. After a few attempts trying to solve the collision error problems, I eventually arrived at collision_triangle(), a pixel-accurate solution.


Abusing forum power since 1986.

Offline

#5 2020-08-10 01:34:30

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

Re: collision_cone_list

hmm, I see your point, the issue with the original script is that typically when handling collision you would be dealing with dynamic objects. So keeping information stored in cache wouldn't always be helpful. Unless of course you are making a platformer and you're just walking right. Though say you're making a twinstick shooter, angle and direction would consistently be different. Possible scaling from different weapons would also be an issue.

For my personal use I'm looking to make it a single script for easier management, I'm making a top down arpg where switching out weapons is consistent. So changing the angle and direction is almost definitely a must for my use. Though the multiple drawing per frame are a huge resource hog.

Offline

#6 2020-08-10 02:13:17

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

Re: collision_cone_list

Changing the direction and scale isn't an issue with caching system, it's exactly the problem it solves, but using many different cone angles could be.

Something I failed to mention earlier is deactivating and activating large numbers instances like this may be slow and maybe even a little unstable depending on when its done. I don't have any hard data on this. I've been told a better way is to move the instances away from the collision area instead of deactivating them (perhaps millions of pixels away), and move them back when you are done. It's said to be faster and it doesn't require updating internal task schedules which may have weird or unpredictable side effects.


Abusing forum power since 1986.

Offline

#7 2020-08-10 14:57:40

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

Re: collision_cone_list

After testing the method of changing their positions then moving them back it appears it's slightly less efficient then just handling their active state.

The method I'm using for this is simply adding/subtracting 1000000 to the collided objects x.

I've noticed that having the line collisions actually seems to save on calculations, saving about 20% of the frames, because roughly 10% of the objects are removed from the overall circle check, I believe it would be best to try to maximize the number of collisions we can for sure remove, similarly to the line checks with collision_circle, rectangle, or oval. Though coming up with a formula to find the maximum fill area for any given cone would be beyond my math skills. But the idea would work something like this:

Ro9CHlS.png

It might grab all the objects before the circle, in which case if the forth check (red circle) returns no instances then we can stop there. Though if it does return something we iterate down to the removal of possible hundreds of non important instances by checking a rectangle which would encompass the entire cone, to cut down on the number of needed checks, Though if the width of the cone is 270 degreees or over then this would be pretty futile, a simple check could prevent that though. once we have everything we know for sure is in the cone removed, and we have everything we know for sure isnt in the cone removed from a possible list, then we can check the remainder of the possible list for anything which may have fallen in the angle range.

Come to think of it, if the cone width is above 180 we could just flip the lists, so say cone width is 270, well we would check for 90 and return the other list.

None of which are perfect solutions but optimization is key here.

Removing the following code should help a lot:

Expand//now iterate through the circle list adding anyone landing with in the bounds of the angle
while not ds_list_empty(circle_list)
{
  var test_obj = circle_list[| 0]
  
  var ox = test_obj.bbox_left+(test_obj.bbox_right-test_obj.bbox_left)
  var oy = test_obj.bbox_top+(test_obj.bbox_bottom-test_obj.bbox_top)
  
  var odir = point_direction(xx, yy, ox, oy)
  if (abs(angle_difference(dir+(ang/2), odir)) <= ang/2)
  {
    ds_list_add(collision_list, test_obj)
    test_obj.x += 1000000
  }
  
  ds_list_delete(circle_list, 0)
}

Offline

#8 2020-08-10 17:21:10

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

Re: collision_cone_list

I just thought of a different way to do pixel-perfect collision with just a circle collision and a single-pixel sprite. Might simplify collision_triangle() as well.

Spring-boarding off your idea of repeatedly culling collision candidates, you can create the initial set with collision_circle_list() and then use a scaled and rotated rectangular sprite to cull those instances with two partitioning planes. In practice, I do it with a two-pixel high sprite to make scaling and positioning simpler.

xmZ5wTY.gif

The white instances are the ones within the cone. The gray instances were culled by the collision circle. The magenta, cyan, and blue instances were culled by one or both partitioning planes. Some alternate logic is needed for cone angles greater than 180 degrees. I think a similar approach could work with just two passes of a single semicircle collision mask.

Proof of concept:
https://xotmatrix.github.io/demos/colli … index.html

I had some strange problems getting it to compile correctly under HTML5.

EDIT:

I just realized you are probably using GMS1 because you used obsolete function instance_create() and don't take advantage of collision_circle_list(). These compatibility issues make me crazy.

Last edited by xot (2020-08-10 19:33:55)


Abusing forum power since 1986.

Offline

#9 2020-08-10 19:31:56

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

Re: collision_cone_list

Funny I was just about to show my new example of recursive culling with my above template, I've been working with a few mathematicians to find the formula for best fit circle in circle sections, This is What we were able to come up with:
https://i.gyazo.com/55a60f67fc95a308514 … e574d9.mp4
9bwCSG2.png

This method appears to be outside of the bounds but that's just an issue with the draw functions when view is zoomed in.

The formula was

Expandvar t = degtorad(ang)  //theta is meassured in radians
var R = lng
var dir = direction

var r = R * (sin(t/2) / (1 + sin(t/2)))

var center_x = xx+lengthdir_x(R-r, dir)
var center_y = yy+lengthdir_y(R-r, dir)

So with the line and first circle collision both now possible to put those instances into the passed list, we can temporarily deactivate them or move them, which will leave up with roughly "angle%" less instances (assuming we're surrounded equally on all sides) then we can use handle the remaining objects,
-grab the red circle radius,
-if any are present,
--grab the yellow rectangle,
--and compare if those objects are in the red circle list,
--if any are present
---check the rectangle's list for point direction

Offline

#10 2020-08-10 19:50:47

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

Re: collision_cone_list

Come to think of it, You could actually get pixel perfect collision with collision line if you only did lines from the outer border pixels. Temporarily removing the collided objects, then you would never actually need to account for the extras with in the radius. It would require more checks but the overhead may be less than expected. As it seems to cut down on my collision system quite a lot. I suppose I should start by trying 10k line checks against nothing first.

Example:
R75gYSo.png
[EDIT] This did not work out well.


On second thought, this would deffinently create move collision checks then using a "least-squares formula" Which there are a few good examples found on this page:
https://people.sc.fsu.edu/~jburkardt/cp … _test.html
Example:
sample01.png
Though to be honest im not to sure how well that example could help solve this issue.

[Edit] No matter how you slice it, you would still end up with a max of 1 rectangle collision per pixel length.

Last edited by redeyesmaster (2020-08-10 20:19:58)

Offline

#11 2020-08-10 20:25:55

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

Re: collision_cone_list

I added a GMS1 port of that proof-of-concept to this page.

https://xotmatrix.github.io/demos/colli … index.html


Abusing forum power since 1986.

Offline

#12 2020-08-10 21:38:34

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

Re: collision_cone_list

I've noticed you method has a VERY small margin of error, where occassionally there will be yellow pixels in front and behind the facing direction. Though I greatly appreciate the gms 1 link. I'll add it to my test project and see how it does.
Example:
https://gyazo.com/4792c3cedfe92b3c63134161e1ff43ce
I may just be color blind but I'm almost positive a few dots are passing through. Might need to test with different colors and I'll edit in another video.

[Edit 1]
Yeah it was giving false positives.
https://i.gyazo.com/809ad549a32586d2872 … e0c327.mp4

[Edit 2]
Nevermind those were the double culled out objects
https://gyazo.com/aa001b7d24c656b140793c73e48aa6ee

[Edit 3]
I knew i wasnt crazy, I kept testing it and in the top right you can see a pixel make it through, given a long enough distance this could make for a sizable gap
https://i.gyazo.com/0b60f4b49e526fe63fe … 1a323a.mp4

Stats:
Using with all, and calculating their distance and directions
27% of the over all frames 81/300

Red's culling collision system
48%, 130/270

Red's surface collision system
21%, 21/220

All of which are using their most precise settings, although same angle and length as well as number of objects collided/not collided.
The over all frame fluctuation is coming from my computer's background tasks. The important number is the percentages. I'll still need to adjust your new system and incorporate it into a script. But I presume it will likely be the best candidate, though ill try 2 version. With and with out the all of an object.

Last edited by redeyesmaster (2020-08-10 23:22:51)

Offline

#13 2020-08-11 01:05:41

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

Re: collision_cone_list

Those false positive stray collisions are caused by rounding errors. The dimensions of the sprite and the circle are not exactly the same in practice. Increasing the size of the culling sprite by one or two pixels (or more if you're paranoid) should ensure it always overlaps the boundary of the circle.

Expandimage_xscale = cone_radius + 1;
image_yscale = cone_radius + 1;

Abusing forum power since 1986.

Offline

#14 2020-08-11 01:07:22

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

Re: collision_cone_list

It will amaze me for years, but calling every single object with a with statement and having each one check for it's self with a unique collision check is by far the most efficient way, I wont even need to run a frame drop test as i see no difference. The only issues I see are larger sprites will get excluded because they are slightly in the culling. I know currently the script only cares about their x,y but I plan to adjust this in the future.
Example:
9h39UsM.png
With 4x as many object:
https://i.gyazo.com/0dcf2dd80081e77ef06 … 937ad3.mp4

Last edited by redeyesmaster (2020-08-11 01:18:57)

Offline

#15 2020-08-11 01:11:02

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

Re: collision_cone_list

Oh, shoot. I didn't think that through with the larger sprite. The partitioning plane sprite needs to be flopped over and logic needs to be reversed. If all three collisions happen, it's in the cone ... I think? I haven't tested it.

EDIT:

Yeah, that almost works but it's having more problems with rounding errors.

Kq5plol.png
chfKW2h.png

Last edited by xot (2020-08-11 01:22:02)


Abusing forum power since 1986.

Offline

#16 2020-08-11 01:21:38

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

Re: collision_cone_list

I edited my last post to show a working video of 4 times as many object being tested, the max returned collisions is just over 2200. It's working quite well.

Offline

#17 2020-08-11 01:24:42

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

Re: collision_cone_list

Honestly those rounding errors are only popping up when the cones angle is 0, which... well we can just return a blank list at that point.

Last edited by redeyesmaster (2020-08-11 01:25:32)

Offline

#18 2020-08-11 01:36:05

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

Re: collision_cone_list

WUSIFds.png
mDgvNpr.png
I changed the collision system, and made everything export to a list. The new system also has a secondary check to see if it even passed the previous step, should cut down on calculations a ton. It's not currently in script form but here is the updated code

Step Event:

Expandd = point_direction(x,y,mouse_x,mouse_y)
cone_direction = d
angle = min(point_distance(x,y,mouse_x,mouse_y)/cone_radius,1) * 180
cone_angle = angle
/*
var list = collision_cone_list(x,y,d,cone_radius,45,object1,true,true)
show_debug_message("ds_list_size(list) = "+string(ds_list_size(list)))

ds_list_destroy(list)
///*/


//cone_angle = 180 * mouse_x / room_width;

image_xscale = cone_radius;
image_yscale = cone_radius;

var dir = cone_direction;
var ang = 90 + cone_angle / 2;
var list = ds_list_create()
with (object1) {
    var include = true
    //  Circle Set
    image_blend = c_white;
    if (collision_circle(other.x, other.y, other.image_xscale, id, true, false)){
        image_blend &= $FFFFFF;
    }else{
        image_blend &= $777777
        include = false;
        }
    //  Plane Set 1
    other.image_angle = dir - ang;
    if (place_meeting(x, y, other.id)) && include{
        image_blend &= $FF33FF
    }else{
        image_blend &= $FFFFFF;
        include = false;
    }
    //  Plane Set 2
    other.image_angle = dir + ang;
    if (place_meeting(x, y, other.id)) && include{
        image_blend &= $FFFF33
    }else{
        image_blend &= $FFFFFF;
        include = false;
    }
    if (include) ds_list_add(list, id);
}

//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)

Honestly with all the methods we have now we could put them into one large script, and give a precise value for each, this would be the standard but if they needed an absolutely pixel perfect system we could add the line checks as well. Though I have no idea on how we would make that formula work.

Last edited by redeyesmaster (2020-08-11 01:44:29)

Offline

#19 2020-08-11 01:42:44

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

Re: collision_cone_list

redeyesmaster wrote:

Honestly those rounding errors are only popping up when the cones angle is 0, which... well we can just return a blank list at that point.

That was my feeling, or use collision line. The partitioning sprite can be adjusted to work without that but I'm not happy with the math yet.

Ec73DiG.png

EDIT:

Relevant changes:

Expandvar surf = surface_create(1, 1);
surface_set_target(surf);
draw_clear_alpha(c_white, 1);
surface_reset_target();
sprite = sprite_create_from_surface(surf, 0, 0, 1, 1, false, false, 0, 1);
sprite_collision_mask(sprite, false, 0, 0, 0, 0, 1, bboxkind_precise, 0);
surface_free(surf);
Expandvar dir = cone_direction;
var ang1 = cone_angle / 2;
var ang2 = 90 - ang1;

with (object1) {
    //  Circle Set
    image_blend = c_white;
    image_blend &= collision_circle(other.x, other.y, other.image_xscale, id, true, false) ? $FFFFFF : $000000;
    //  Plane Set 1
    other.image_angle = dir - ang1;
    image_blend &= place_meeting(x, y, other.id) ? $FFFFFF : $444400;
    //  Plane Set 2
    other.image_angle = dir - ang2;
    image_blend &= place_meeting(x, y, other.id) ? $FFFFFF : $440044;
}

Sorry, I'm using ternary operators in the original GMS2 version. Using GMS1 is torture. There is something wrong with it on my system. The IDE runs extremely slowly making it very hard to use.

Last edited by xot (2020-08-11 01:48:42)


Abusing forum power since 1986.

Offline

#20 2020-08-11 01:46:58

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

Re: collision_cone_list

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

Offline

Board footer

Powered by FluxBB