How do I reduce collision check?

Get help using Construct 2

Post » Sat Mar 14, 2015 4:54 am

I have an object type which is monster. And the monster has instance variable called Team. When two monster of different team collide with each other, they will be destroyed. i have 200 monsters for each team and when i setup event condition "when monster collide with monster" the collision check will be 200*200 which is 40000! This is because system will check the collision between monster with same team too.
So, how do I arrange the event sheet so that the system will not check the collision between monster of same team? I don't prefer to create new sprite for each team because there will be more than 10 teams of monster in my game and this will make my work messy and complicated.

Edit: I made a mistake,79800 is the initial collision check using the condition above. 40000 checks is the target i want to achieve.
Last edited by StormHo on Sat Mar 14, 2015 4:30 pm, edited 1 time in total.
B
16
S
4
G
1
Posts: 201
Reputation: 1,554

Post » Sat Mar 14, 2015 6:48 am

First, check your average fps through the debugger, or with a Text object set every 0.5 seconds to "fps". I mocked up a quick test with 400 objects all with collision detection enabled and it ran at a solid 60fps in Chrome. (YMMV especially on mobile devices)

If the instances are being destroyed after the collision, you could take advantage of the performance gains of using "On Overlap" instead of "On Trigger" to see if that makes a difference.

More information on the differences between "On Overlap" and "On Collision" available here:
Overlap vs Collision

Given a total of 400 monsters, I'm assuming that your layout size is much bigger than your window size. If that is true and performance is still unacceptable even with the built-in use of collision cells, you can experiment with two different families.

Screenshot:
Collision Cells vs Team Picking Screen.png


There are disadvantages to using "On overlap" but if you're destroying the instances on contact, then it might not matter for you. Overlap may return multiple instances overlapping as well in the same tick. (Team1_Bill overlaps Team2_Nathan, and Team1_Jim overlaps Team2_Sam), might be difficult to parse out if Team1_Bill overlapped Nathan or Sam.


The FPS benchmark is about even for both collision systems until approximately 1000 are on screen, at which point the Team1 overlap Team2 Event routine starts to see marked improvements.

Benchmarking Capx attached.
You do not have the required permissions to view the files attached to this post.
B
31
S
6
G
8
Posts: 232
Reputation: 6,144

Post » Sat Mar 14, 2015 6:54 am

"collision check will be 200*200 which is 40000! This is because system will check the collision between monster with same team too."

I'm pretty sure 40,000 is correct, and what you want (the best you can get for this method).

Each of the 200 monsters on team A has to be checked against each of the 200 monsters on team B. That's 200^2.

If you wanted to check them against the same team too, that would be comparable to the "handshake problem" in mathematics.
Which would be 400*399/2 = 79,800 tests

You need another solution entirely if you want to optimize this. I recommend looking into cellular automata, and drawing on the power of the graphics card to accomplish this feat.

See: http://en.wikipedia.org/wiki/Cellular_automaton

This isn't an easy problem to solve. Your best bet is reducing the number of monsters, if your game design will allow for it.
If you can tell us more about your game, and why such a large number is needed, we may be able to offer simpler solutions.
B
9
S
2
G
1
Posts: 48
Reputation: 710

Post » Sat Mar 14, 2015 6:59 am

cacotigon wrote:I mocked up a quick test with 400 objects all with collision detection enabled and it ran at a solid 60fps in Chrome. (YMMV especially on mobile devices)


Post ninja'd.

I assumed the sheer number of collision tests was the issue, but as cacotigon suggested, it may be something else entirely. It sounds like C2 is already optimizing them pretty well by default.

Maybe there's a lot of other stuff going on, and these collision tests are the straw that broke the browser's back?
Sounds like optimizations elsewhere may avoid the problem and my suggestion may be completely unnecessary.
B
9
S
2
G
1
Posts: 48
Reputation: 710

Post » Sat Mar 14, 2015 4:23 pm

MVG wrote:"collision check will be 200*200 which is 40000! This is because system will check the collision between monster with same team too."

I'm pretty sure 40,000 is correct, and what you want (the best you can get for this method).

Each of the 200 monsters on team A has to be checked against each of the 200 monsters on team B. That's 200^2.

If you wanted to check them against the same team too, that would be comparable to the "handshake problem" in mathematics.
Which would be 400*399/2 = 79,800 tests

You need another solution entirely if you want to optimize this. I recommend looking into cellular automata, and drawing on the power of the graphics card to accomplish this feat.

See: http://en.wikipedia.org/wiki/Cellular_automaton

This isn't an easy problem to solve. Your best bet is reducing the number of monsters, if your game design will allow for it.
If you can tell us more about your game, and why such a large number is needed, we may be able to offer simpler solutions.


Ah I made a mistake. 79800 is the current condition i am facing. I want to reduce 79800 checks to 40000 checks. Meaning I just want to check collision between 2 different team but not the same team.
B
16
S
4
G
1
Posts: 201
Reputation: 1,554

Post » Sat Mar 14, 2015 4:28 pm

cacotigon wrote:First, check your average fps through the debugger, or with a Text object set every 0.5 seconds to "fps". I mocked up a quick test with 400 objects all with collision detection enabled and it ran at a solid 60fps in Chrome. (YMMV especially on mobile devices)

If the instances are being destroyed after the collision, you could take advantage of the performance gains of using "On Overlap" instead of "On Trigger" to see if that makes a difference.

More information on the differences between "On Overlap" and "On Collision" available here:
Overlap vs Collision

Given a total of 400 monsters, I'm assuming that your layout size is much bigger than your window size. If that is true and performance is still unacceptable even with the built-in use of collision cells, you can experiment with two different families.

Screenshot:
Collision Cells vs Team Picking Screen.png


There are disadvantages to using "On overlap" but if you're destroying the instances on contact, then it might not matter for you. Overlap may return multiple instances overlapping as well in the same tick. (Team1_Bill overlaps Team2_Nathan, and Team1_Jim overlaps Team2_Sam), might be difficult to parse out if Team1_Bill overlapped Nathan or Sam.


The FPS benchmark is about even for both collision systems until approximately 1000 are on screen, at which point the Team1 overlap Team2 Event routine starts to see marked improvements.

Benchmarking Capx attached.


It is a rts game and my monster are mini size so i could put all of them in window size. I will give it a shot anyway.
B
16
S
4
G
1
Posts: 201
Reputation: 1,554

Post » Sat Mar 14, 2015 4:57 pm

> @StormHo:


A similar optimization issue was brought up earlier in the forum, you might wanna take a look there:
viewtopic.php?f=147&t=123408
I also described collision checking optimization there, might be useful for you too.

Also here is an example of a multilevel isometric (auto-z-indexing) multilayer (same screen) solution without collision checks at all.
In this, it is shown, how you can manage the same object to block (collide with) one, but not with the other player at the SAME TIME.
You can use that method as well, to detect, if actually an enemy is in range to check collisions at all, and if checking, only between you and enemy objects.
capx: download/file.php?id=10965
original post: isometric-multiple-floors_t121850?start=30
B
8
S
3
Posts: 197
Reputation: 1,207


Return to How do I....?

Who is online

Users browsing this forum: radhaw and 22 guests