Performance questions! (collision and animations)

[rougan]

Hey everyone,
So I have two (theoretical) questions for optimising performance...

1) Say I had 100 bullets and 100 enemies on screen at once, and wanted to check if any two collided. I would have to check every bullet against every enemy- thats 100^2 checks which seems like quite a lot.. is there a better/faster way of doing this?

unrelated question..
2) Let's also say that I've put those 100 enemies into a spritebatch. I also want to animate each of the enemies with a 7 image animation. The only way I can think of doing that is constantly updating the quad used for each item in the spritebatch. However, that seems to be a bit of a redundant use of a spritebatch- aren't they meant to be used for static stuff? Again, are there any better/faster ways of doing this, or is just drawing them normally the best?

Thanks alot

[panther99]

1) I'm not experienced with Love2D but I think it's much easier (if it's possible in Lua), to add trait to enemy object to lose health / kill itself in collision with bullet so you wouldn't have to check for every instance whether there's a collision or not and let them do it on it's own or reversible (if enemies just have to be destroyed right away), add trait to the bullet to destroy enemy when it touches it. Basically it's oftenly implemented like that (at least that's my experience using other engines).

[rougan]

Thanks for the reply! Sorry if i'm being slow but...

to add trait to enemy object to lose health / kill itself in collision with bullet so you wouldn't have to check for every instance whether there's a collision or not

How does the trait know that the collision with the bullet has occured? Surely there's got to more collision checking somewhere?

[panther99]

How does the trait know that the collision with the bullet has occured? Surely there's got to more collision checking somewhere?

No. Look, imagine that you have one model (something like class in object-oriented programming) - all other instances are based on that model. Model says something like this:

Code: Select all

model for enemy object

on collision
    check name of the object
    if object name is bullet
        kill oneself / lose health
...

In Game Maker (my first game development engine), collision action was based on the object that collides with object that is defined in that moment. But as I said, I'm not sure whether it is implementable in Love2D (if it's possible to check traits of other instance).

Every instance of one class checks on it's own when it comes to contact with another instance of same or different class, do you understand me better now?

Code: Select all

Enemy = { name = "enemy", health = 100 }
Bullet = { name = "bullet" }
function Enemy.collision(self, other)
    if other.name == "bullet"
        self.health = self.health - 20
    end
end

[zorg]

Since you roll your own game internals with löve (whether it's OOP-like, ECS-like, a hybrid, or something else entirely), you can implement stuff like that however you wish. It's perfectly doable to have a collision system that checks two fields of two entities, no matter their type, as long as you defined them to have those fields you wish to be checked.

Every instance of one class checks on it's own when it comes to contact with another instance of same or different class

That will still result in 100^2 (or 100*100) checks, unless you're only calling collision exclusively on either bullets or enemies, but not the other. And you're not.

In any case, there are a few ways you could handle this. One case would be to do some extra bookkeeping by putting objects in separate tables according to what they can collide with; at the moment, i can't think of an example use case for this though. Another, probably better way, would be to do spatial hashing. There are already libraries that do this though, like kikito's bump.

[rougan]

Okay thanks zorg, I'll think I'll give bump a go!

[slime]

Using a spritebatch will basically always be more efficient than calling love.graphics.draw multiple times in a row, even if you clear and re-add everything to the batch every frame.

[raidho36]

If every bullet has to call collision against every enemy (which it does) then it'll be 100 times 100.

Spatial partitioning is definitely what you're looking for, depending on world complexity you may go with simple grid (e.g. static screen or side-scrolling game), or a quad tree (e.g. large world where you freely move around).

[ivan]

1) Say I had 100 bullets and 100 enemies on screen at once, and wanted to check if any two collided. I would have to check every bullet against every enemy- thats 100^2 checks which seems like quite a lot.. is there a better/faster way of doing this?

The worst case scenario would be to check
every object against every other object which is: n*(n+1)/2

Checking only bullets vs enemies is called "filtering",
and can reduce the number of check considerably: n1*n2
Since in games you usually have a lot of bullets
and only a few enemies then it wouldn't be an issue.

If both n1 and n2 are large numbers
(you have a lot of enemies AND a lot of bullets) then
you will need some sort of partitioning.
If you treat the bullets as "points in a grid" it
would not be very hard to roll out your own solution.
Then each enemy can query the grid for nearby bullets.
Unless the bullets move really fast in which case
"tunneling" can make the problem much more complicated.

Box2D (love.physics) can handle all of that for you nicely.

PS. It should be noted that this is all speculation,
a better approach is to make a prototype and then use
"profiling" to find the bottlenecks.