Performance alternatives to collision detection?

I was reading this blog post about not wasting time optimizing unnecessary things when I came across this:

There are only a few select cases where the game logic takes longer than rendering and determines the framerate. These cases are usually obvious and easy to optimise as well:
• Checking for collisions between too many objects. If you test for overlap between instances of an object with 100 instances, there are thousands of combinations of pairs of instances that Construct 2 has to check every tick, which can total over half a million collision checks per second. You can either check on a timer, e.g. every second instead of every tick, or simply reduce the object count again.

What are some faster alternatives to collision detection? Let's say I have an RTS type game where the player and dozens of NPCS can harvest from hundreds of nodes (trees and mines). Right now I use collision detection to determine when to initiate the harvesting function. I'm worried this will bog down the game when there are a lot more instances around. Checking for overlap every second seems like it might cause the objects to miss being detected. Maybe a smaller increment, like 0.5. That might not be enough to speed it up. Does the collision detection for the Solid behavior also have this limitation?

If the overlap timer doesn't work out, the only solution I can think of would be to break it up into smaller zones. Any other ideas out there?

Collision tree's tend to work really well. I don't know why C2 doesn't use a Binary or Quad tree. C2 uses a Bruteforce model of comparing everything. Some had previously linked to a js api that used quadtree, but no one has done a behaviour plugin as of yet. Maybe at some point.

The solution you mentioned should be fine. By default games run at 60 FPS, so will be doing collision checks 60 times a second. If you do a collision check every 0.5 seconds it will be 30 times faster. Even if you do a collision check every 0.1 seconds, it will be 6 times faster, and fairly unlikely to miss any collisions providing the objects are relatively slow moving.

If possible, you should also use additional conditions to filter down the list of objects being checked. E.g.:

+ Sprite: is overlapping Block

+ Sprite: is moving

In this case it collision checks every Sprite, since it's the first condition, then of those that are overlapping it filters down to just the moving instances. The instances that are not moving had an unnecessary collision check. The other way round:

+ Sprite: is moving

+ Sprite: is overlapping Block

This first picks only the moving Sprites, then of those, runs a collision check. This can save a huge amount of collision checks if most of the Sprite objects are not moving.

Ashley, do you mean 0.1 seconds or 0.1 * dt seconds?

Excal - 0.1 seconds! There's no point using dt when the units are already seconds. "Every 0.1 seconds" happens at the same time interval regardless of the framerate, which is the whole point of framerate independence. I'd suggest re-reading delta-time and framerate independence.

Ashley

This info was really helpful! I was trying to generate a forest this morning and my recursion was off a bit and it made a massive forest which got choppy on my modest laptop when I tried to move. I did a bunch of these optimizations and it was able to easily handle the massive forest.

For some reason I was thinking the tick was every 0.16 seconds and going to 0.5 would only lessen it by ~3 instead of ~30. Thanks again for the help.