GameMaker Optimizing Collisions

Coded Games

Member
So I have been working on optimizing my game today and noticed that the largest portion of runtime is the Engine's HandleCollision category (around 40% of total runtime). It make sense, as my game is a bullet hell it can have up to thousands of bullet instances at a time. I have tried being careful about it, the only collision between bullets is the player and it is placed in the player object.

Is there any other collision best practices that I should be following to cut down runtime in this category?

All my bullets use the fastest rectangle bounding box. I have also thought about replacing this with my own collision system where I just check distances between bullets and player, as that is all I really need. But I tried removing the collision event between the player and bullet, just to see if it would make a difference, and it did not.

For testing I want to completely remove the HandleCollision time, I thought that removing the event would have some impact on it but it did not.
 

rytan451

Member
GMS2, internally, uses an R-tree for efficiency when checking collisions. There isn't really any way to optimise collisions except to reduce the number of instances, and to make sure you're using the R-trees. For the latter, it's relatively simple: don't go with (obj_bullet) { if (point_in_circle(.... Don't use a with statement, and then check using the geometry-based collision functions. Instead, check directly against instances using the built-in collision functions

For reducing the number of instances, I have some tips on how to do that:

First, if the player has a set maximum speed, and a bullet has a constant velocity, you can compute, at time of bullet creation, if it's possible for the player to collide with the bullet. That is, if the player were absolutely bent on colliding with that bullet, ignoring other collisions, moving at maximum speed, is it at all possible for the player to collide with that bullet?

Consider a bullet going due right, with the player due south of it. If the player moves at 5 pixels per frame, but the bullet moves at 10 pixels per frame, the player will never catch up to the bullet and collide with it. Since this is all (relatively) simple math, you can calculate this once per linearly moving bullet. If the bullet cannot, under any circumstances, collide with the player, then instead of creating a bullet instance, you can create a particle that acts exactly like the bullet. This particle, of course, can't be detected for collision events.

Though this would remove some fast-moving bullets, a player might be able to catch up with slower bullets, but only outside the playable area. A tiny bit more math can be used to detect if the bullet will be inside the playable area (or have vanished) before the player had collided with it.

You might also, at random, pick a bullet, and if it won't be able to collide with the player, turn it into a particle. I'm not entirely sure how to do that efficiently (if I understand correctly, instance_find takes linear time), but you can give bullets a randomised alarm on when to check if it is possible to collide.

Here's how I would do the math (this all uses vectors):

Let x be the starting position of the bullet (relative to the player).
Let v be the velocity of the bullet.
Let R be the maximum range within which a bullet can collide with a player (so if a bullet 10 pixels away from the player collides with the player, but if it's 11 pixels away, then R = 10).

Therefore, the position of the bullet at time t is x + vt.

If the player is to intercept the bullet (defined as being at the same position) at time t, then it must move at the velocity (x + vt - R(x + vt)/|x + vt|)/t = x/t + v - R(x/t + v)/||x + vt||
Given that the player has a maximum speed S, this means that ||x/t + v - R(x/t + v)/(||x + vt||)|| <= S.

Since R(x/t + v)/||x + vt|| is in the same direction as x/t + v, this inequality is the same as ||x/t + v|| <= S - R/t.

Since t = 0 is when the bullet came into existence, that means that t >= 0.

(I'm not going to prove this) When you minimise t while holding with the inequalities, we see that ||x/t + v|| = S - R/t.

We expand out v and x. We find sqrt((x.x/t + v.x)^2 + (x.y/t + v.y)^2) = S - R/t

(I'm not going to do this) We solve for t.

If t is larger than the maximum age of the bullet, then the bullet would have vanished before the player reached it.

Given that the player is inside the playable area (a rectangle), and the bullet starts inside the playable area, if x + vt is outside of the playable area, then the bullet exits the playable area before the player reaches it.

Otherwise, the bullet is able to collide with the player.

Of course, you'd only have to solve the equation once, and then just let the computer do the number work.
 

Coded Games

Member
Unfortunately I have considered many methods of bullet removal and there are not that many ways that wouldn't affect gameplay. In my game bullets are relatively slow, the game is paused the vast majority of the time and the player can teleport large distances. Making bullet replacement methods not viable because basically any bullet, even ones off screen very far away, potentially can be hit or collected. I have methods that remove bullets that are extremely far away from the player but other than that there is not much that can be done.
 

TheouAegis

Member
Does anyone else have collision events with bullets or any other collision event for that matter? If the player and the bullets were the only thing colliding, then there should have been a drop. That makes it sound like your issue is the player's bullets colliding with enemies, but then you should only see slow down if the player is actually shooting and not when the player is idle.

Have you tried clearing all the caches? you have the one that is cleared by the dustpan, but you also have a tent folder and some other one that you can clear inside the preferences. It seems odd to me that it's telling you collision handling is the biggest drain even when supposedly you don't have collision handling. Unless of course there is some code that you missed when you were disabling it.

Also, when you say you disable the collision code between the player and the bullets, did you actually remove the collision event itself or did you just comment it out? It needs to be completely removed. As in deleted, no code at all, no comments, nothing inside the event. Not even a reference to the event.
 

Coded Games

Member
Ok progress is being made! I found one other object that had a collision event with bullets, one that was not even in the room :/. But anyway, once I changed that event to Alarm 11 and the player's collision event to Alarm 11 HandleCollision went from about 40% of my runtime to less than 1%. In my games benchmark (yes I made a benchmark to test optimization changes) it almost doubled frame rates.

So, now that I know that collisions are hurting FPS a ton, how can improve this? So a lot of my bullets are off screen and get turned invisible with a culling script. Does GameMaker still process collisions for those? Is there a way I can disable collisions when they are turned invisible? Do I just set the sprite's mask to nothing?

Also, I probably need to test this but would my simple collisions idea be any faster? I don't need complex collisions, I tried to make them as simple as possible to begin with. But would performance be bad if I just calculated the distance to the player on every bullet and if it was less than some amount then it's a collision. I probably don't even need accurate collisions, I could just check if the difference in X/Y values is less than something, don't even need trig/point_distance.
 

xenoargh

Member
Consider using fewer bullets in the sim via a variety of methods:

1. Fake bullets like rytan451 suggested... but they can turn into real ones when they need to, by performing a distance-check every few (randomized) frames, to distribute the computation load (distance checks are inherently expensive). Too far away? Disable the bullet's physics; now it's just a quad being drawn at a location, and can be managed the old-fashioned way, via changing x and y. Polling every 10 frames or so should be a huge boost in performance; the vast majority of the bullets are no longer performing any collision-event checking, and 10 frames, at 60FPS, should be acceptable, in terms of hits.

2. Bullets that are a long, long way away can delete themselves or turn off physics really early. If this is all confined to one tiny Room, like Robotron, you may try and find out if the player, via teleports, can be in the circle calculated by the lifetime of the bullet before it leaves the area of play. If in a larger room, simply quit spamming bullets from far-away sources. Don't waste CPU time on stuff that won't matter to gameplay.

3. Make sure your bullets are created and moved sanely. Bullets should be created using a common, globalized fixture; don't make new fixtures constantly and destroy them. They should, generally, receive one, and only one, impulse to move. Never move them manually; use impulses / forces if you want to guide them, etc. and do that infrequently. Unless you care about physics interactions, they (and the player) should be sensors, not objects that need to calculate impact velocity vs. mass, etc., etc. (and they can be sensors until they're quite close to players, regardless).
 

xenoargh

Member
Does GameMaker still process collisions for those? Is there a way I can disable collisions when they are turned invisible? Do I just set the sprite's mask to nothing?
1. Yes. Masks have zero effect on Box2D physics simulated objects.
2. Yes. See phy_active.
 

Coded Games

Member
Unfortunately like I said earlier. The room is large and the player has the ability to basically teleport to any point in the room at any time. Also, bullets are both good and bad so the player will regularly teleport off in the distance, where they have not been, to hunt down good bullets. So replacing bullets with fake ones is not a viable option, I can't really delete too many bullets as basically deleting any can impact gameplay. Making good bullets harder to find, and I don't want to just delete bad bullets and leave a patch of good ones.

2/3 I am not using Box2D physics, just basic collision events.

I do have other optimizations in the game, bullets only update certain things, like culling, every 1 in 10 frames. I also pool instances, creating about 10,000 bullets in a stack at the start of the game and activate/deactivate them as needed. This may not be the most optimal, as UpdateActiveLists is also a large portion of my runtime (now 30% post removing collisions).

I have really thought about just making all my bullets one singleton. Just have that object have a list of points that it draws a bullet sprite at. Each step loop through the points, update their position rotation etc. Basically just make my own lightweight objects. If I was using 2.3 this could be a lot easier. But once again, I really don't know if that would be any more efficient and that would be a much more massive change.
 

xenoargh

Member
Hmm.

Why not treat the bullets as a 2D array, XY? Same with velocity. No Objects at all; just quads being drawn if they're inside the cull distance.

You could implement your own basic search optimization, by recording the points they'll be at, at start and end; doing a line-check vs. the player's position every 10 frames before doing a detailed radius-check would be fairly fast. Then you don't need a stack; just add / delete members of the arrays as you go.

Arrays are inherently fast, and even using draw_sprite_ext() isn't bad, although using a vertex buffer / shader would probably be faster. I missed the point about 10K bullets before, sorry; that's a horse of entirely different color; you must use the simplest-possible methods if you're going to get this remotely playable, lol.
 

xenoargh

Member
So, like, with a fixed 10K bullets:

GML:
for(var i = 0; i < 10000; i++){
  myArrayOfBulletsX[i] += myArrayOfBulletsVelocityX[i];
  myArrayOfBulletsY[i] += myArrayOfBulletsVelocityY[i];
  //If inside the cull distance...
  draw_sprite_ext(myArrayOfBulletsX[i],myArrayOfBulletsY[i] ... etc.)
}
Finding out the collision would be something like:
GML:
myArrayOfBulletsTimer[i] -= 1;
if(myArrayOfBulletsTimer[i] <= 0){
  var mightCollide = collision_line(bulletX,bulletY,bulletEndingX,bulletEndingY,obj_player,false);
  if(mightCollide != noone){
    //Do true collision testing this frame
  } else {
   myArrayOfBulletsTimer[i] = 10;//Reset this check
  }
}
 

Coded Games

Member
The problem with the array method is that not all 10k bullets are ever active all at once, and adding or removing elements from an array is very slow, as you have to reinitialize the whole array. The 10k number doesn't really matter, I just want it to always be more than I will ever use as creating instances is slow. So for my current implementation I create 10k of them or something, doesn't really matter, push them onto the stack and deactivate them all. When you want one, you pop one off the stack activate it and you are ready to go, when you want to delete one, deactivate it and push it back onto the stack.

I'd say in normal gameplay there are at most 1-2k bullets. It's just my benchmark room that goes up to over 8k bullets and can still get around 20 FPS. Performance in my game really isn't a massive problem, I just want everything to be as fast as possible. My game uses delta timing so I want people to be able to play at the highest frame rates possible. Break out that 240 Hz monitor. But I also want the lowest minimum specs possible. I have had people play on older laptops and have poor performance.

Also for the code example, don't even need collision_line, would just be:
Code:
var colliding = (abs(obj_player.x - x) < size && abs(obj_player.y - y) < size)
^ This seems like the absolute simplest collision checking you could do. Would be just basic square hitboxes centered on origin.

If I REALLY wanted to get optimization crazy and reduce branching I'm sure I could replace the abs function call with some bitwise trickery.
 
Last edited:

xenoargh

Member
With the array method, you could just have a, isThisBulletActive flag; true/false. If false, don't bother processing.

Iterating through a 10K array is speedy; the hard part is eliminating as much math per bullet as possible. Like, probably start w/ culling; outside cull range? You're already done worrying about collisions, drawing, etc., etc., and just need to move it through simple addition.

Getting rid of Instances would really, really help; each Instance does a fair amount of per-frame CPU time even if it's just sitting there, "doing nothing". It does mean that you have to calculate the angle (once, at creation, unless they curve, guide, etc.) and a few other things; we're talking about a fair number of sub-arrays here that would get accessed at need.

Try making 10K Instances in a Room procedurally, w/ all of them using fast-rectangle collisions per frame vs. player only... no drawing, no nothing; it'll be... inherently slower than using an array.
 

Bart

WiseBart
Also for the code example, don't even need collision_line, would just be:
Code:
var colliding = (abs(obj_player.x - x) < size && abs(obj_player.y - y) < size)
^ This seems like the absolute simplest collision checking you could do. Would be just basic square hitboxes centered on origin.

If I REALLY wanted to get optimization crazy and reduce branching I'm sure I could replace the abs function call with some bitwise trickery.
That's a very efficient formula already.

Did you consider ds_grids to perform that check (or a similar one)? They're by far the fastest way to do those basic calculations.
You can e.g. calculate distance squared this way.
Put in the bullets' (x,y) positions and do a ds_grid_add_region twice: once for -player_x, once for -player_y.
Multiply the resulting grid range by itself (ds_grid_multiply_grid_region) to square the values, then add the two columns (to get distance squared).
For your formula, you'll need to figure out some trick to get the call to abs in there, though.

After that, you have the values of distance squared for each bullet and you can sort the values in the grid using the column that now contains those distances.
Then, in that column, use ds_grid_get_min/ds_grid_get_max together with ds_grid_value_x/ds_grid_value_y to find the value closest to size and its index (not sure about rows/columns).
That gives you a range of instances that need to be considered for collision.

You then draw those. To optimize that, you can pool them in a vertex buffer and send in the transforms using a uniform array.

In the end, there's not a single for loop in your gml code and not a single if required for branching.

Since the bullets probably have basic trajectories with speed and acceleration (x = x0 + v0*(t-t0) + a/2*(t-to)²) you can even do those calculations using the ds_grid functions.
So you don't need to update the bullets' positions after adding them to the grid.

Destroying a bullet would mean keep it in the grid but add a very large offset to its position or do some multiply by zero.

I'd expect this to be the fastest way to do this, assuming you can get the formula in "ds_grid" format.
 

GMWolf

aka fel666
I doubt you will manage to get much better than GMs built in collision detection without sacrifices. Especially if you later decide to have multiple instances the bullets could collide with.

It sounds like you are already doing many things right: only activate the instances you need, etc.

You say you collision detection is 40% of the frame. I'd say in a bullet hell that is to be expected. What else is going on in the frame? Moving a couple objects... That's not very intensive work.

Also looking at percentages is not a very useful metric. Just look at how many microseconds collisions take. And decide on a budget for your collisions.
If there isn't much logic going on (most bullet hell games), then you could easily allocate 1/3 or even 1/2 of a frame to it. At 60fps that gives you 8ms to do collisions.
Hopefully you are nowhere near that number.
 

Coded Games

Member
@GMWolf I still think that it is interesting that when I had a collision event with bullets on an object that didn’t even exist HandleCollisions was doing a lot of work. I also found I can still use collision functions like collision_circle without having HandleCollisions going crazy like a collision event would make it.
 

GMWolf

aka fel666
I still think that it is interesting that when I had a collision event with bullets on an object that didn’t even exist HandleCollisions was doing a lot of work.
Yeah... That sounds like a bug.
Maybe GM is traversing it's tree and checking if the object exists in each leaf?
If they had an object mask for each node that wouldn't be necessary...
 

Coded Games

Member
Yeah... That sounds like a bug.
Maybe GM is traversing it's tree and checking if the object exists in each leaf?
If they had an object mask for each node that wouldn't be necessary...
Yeah, that’s implementation details we would have to ask Yoyo people about. I’m also pretty stuck on 2.2 for the foreseeable feature. So no updates for me. Bart’s ds_grid idea does seem interesting. Reworking instances to grid values will be a lot of work though. These are the kind of things I worry about spending time on because I never really know if it will improve anything.
 

Coded Games

Member
How long does it currently take in milliseconds?
I’m not fully sure. The last screenshot I have shows it as 5ms with average total frame time of around 13ms, so this was mid way into my benchmark. Before it starts slowing down. This was also before removing all collision events.

It’s 4am for me so I’m heading to bed. Will update tomorrow.
 

TheouAegis

Member
Not that it will probably help you much in this situation, although maybe it might give you an idea, but in case you didn't already know, you can actually manipulate deactivated instances. You can still move them around manually, change their sprite, and even check those variables. Namely, all of those bullets off screen, which I think you implied you keep active even though they are off screen, you can deactivate and continue to move manually. The only caveat is you need to know the id of each of those instances, and you cannot use with(), only dot notation.
 

Coded Games

Member
Ok I think I made one fairly simple optimization. I made a secondary object called obj_bullet_collide that is a child of the normal obj_bullet. Now when bullets are culled for visibility I also use instance_change to change between the collide and regular version. The collision event is also now just with the _collide version.

This seems like a slightly better version than the deactivate and manually move method of disabling the collision event as things like with () still work.
 
Last edited:

Pixel-Team

Master of Pixel-Fu
I would consider dividing the screen into a grid of imaginary squares that are as large or larger than the largest bullet. Then make your bullets sort themselves according to their screen position. Then your ship only needs to check collisions with the bullets inside the division he is in. I haven't had to do this yet, but Keith Peters wrote a chapter on advanced collision detection in AdvancED Actionscript 3.0 Animation where he does something similar. It sounds like you may not need to optimize too much further, but it's something to consider if you get into the 1000s of bullets.
 

rytan451

Member
I would consider dividing the screen into a grid of imaginary squares that are as large or larger than the largest bullet. Then make your bullets sort themselves according to their screen position. Then your ship only needs to check collisions with the bullets inside the division he is in. I haven't had to do this yet, but Keith Peters wrote a chapter on advanced collision detection in AdvancED Actionscript 3.0 Animation where he does something similar. It sounds like you may not need to optimize too much further, but it's something to consider if you get into the 1000s of bullets.
This might be an optimisation. You'd have to check adjacent squares, of course, since the player can overlap multiple squares. You'd also have to make the bullet instances handle moving from one grid space to another, which means you'd need a fast data structure to hold which instance is in which square.

If you give each bullet a variable "previous" and "next", then you can store which bullet is in which square by using the instances as a doubly linked list. That'd be O(1) insert/delete time when moving between squares. If a bullet is destroyed, it updates the previous/next variables...

That'd seem like it would work quite well.

But if you're overhauling the entire collision system using this spacial partitioning scheme, might it be more efficient to change instances to structs, and maintain an instance pool to reduce memory allocations and deallocations?
 
Top