Jump to content

  • Log In with Google      Sign In   
  • Create Account


Cascading explosions with many objects


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 Amrazek   Members   -  Reputation: 202

Like
0Likes
Like

Posted 31 August 2008 - 08:18 PM

It was difficult to come up with a thread title for this one. Here's the problem in a nutshell: I have a large number of objects that need to destroy neighboring objects when they explode. Specifically, mines. I went with a brute force approach but it's not even close to fast enough to suit my needs, since I want to have a fairly large number of mines at any given time. Here's a picture to give you an idea of the intent: Example Grey balls = Mines Red circle = explosion range 1. Initial exploding mine 2. Caught in the effect of 1., so explodes as well 3. Caught in the effect of 2., etc This is a simple example. It quickly becomes a cpu hog as the mines increase in number: Example 2 I tried a brute force approach, where I simply keep a list of all the mines that exploded initially and then iterate through all of the mines, destroying the ones in range, adding them to the exploded list, and starting over until I managed to get all the way through but it's far too slow. Since the mines can move around the field, calculating everything at the beginning of the level isn't possible. A few google searches provided some information on spatial partitions, and of those the R-Tree looks the most promising but I have no experience with it and I'm not sure it would be fast enough when it has to be reconstructed every frame with approximately a thousand objects. Any suggestions?

Sponsor:

#2 tetractys   Members   -  Reputation: 146

Like
0Likes
Like

Posted 31 August 2008 - 08:42 PM

I have found a similar problem in a game in development
(MekaWars)
For the moment, I tried with a non-optimal solution.
If you find any good optimization, please, let me know.
Thank you in advance.

#3 ToohrVyk   Members   -  Reputation: 1587

Like
0Likes
Like

Posted 31 August 2008 - 08:53 PM

As far as trees go, I would suggest going for something as simple as a balanced binary search tree sorted by horizontal position (it's usually available in language standard libraries). Whenever a bomb explodes, I would search the [x-radius, x+radius] interval for other bombs, remove them from the set and add them to an explosion list. Then, I would iterate the process for all the other bombs.

#4 pto   Members   -  Reputation: 194

Like
0Likes
Like

Posted 31 August 2008 - 08:57 PM

I achieved something similar by doing it iterativly. You do get a sleight delay in explosion times with my method, however in my case it actually looked alot cooler so I was happy with it. Anyway I did this: When a mine explodes it adds a explosion radius object that will get checked NEXT frame. Each frame you only check the active explosions (which is usually only 1 or 2) so individually its quite fast as you split the work over many frames. You end up with this:

Frame 1: Mine 1 explodes, adds an invisible explosion object to the list, gets deleted

Frame 2: Inisible explosion object kills mine 2, gets deleted, mine 2 adds an invisible explosion radius, gets deleted.

Frame 3: Invisible Explosion 2 kills mine 3, ....

So each frame any mines being hit Explode, and setup the explosion for NEXT frame.

It does mean that your big line of mines will not blow up instantly. However you will get a cool effect of the explosion propogating down the line ... especially if you add a 200ms delay or so in there between the mine blowing up and adding the explosion object to blow up the next ones :P

#5 Amrazek   Members   -  Reputation: 202

Like
0Likes
Like

Posted 31 August 2008 - 11:46 PM


Thanks for the suggestion, pto. It worked out perfectly and looks much cleaner as well. I'm getting 1100+ objects with lots of explosions and keeping above 60 fps, which is quite acceptable at this point.

ToohrVyk: Good idea on the binary search tree. I'm going to try integrating it in to see if there's a speed boost to be had :)



#6 0BZEN   Crossbones+   -  Reputation: 2004

Like
0Likes
Like

Posted 01 September 2008 - 12:31 AM

you can look at sweep and prune. It's like sorting the objects along the x and y axis to find out which ones can collide (i.e. the explosion radius overlap). Given you have good frame coherence (the objects dont teleport around from frame to frame), it's pretty efficient.

#7 smcameron   Members   -  Reputation: 101

Like
0Likes
Like

Posted 01 September 2008 - 06:57 AM

Hm, I did something similar once, as an experiment -- I had the exploding objects throw chunks of debris, and had the debris do collision detection, and when the debris hit stuff, it would cause those things to explode too, throwing yet more chunks of explosive debris, etc, and so causing a chain reaction in a "natural" way -- the behavior wasn't coded in per se, as in "look around for nearby mines and explode them too," it just emerged from the way the chunks of debris behaved (as though they were little bombs). This also spreads the calculations over many frames, although if you gather too much critical mass in one spot the sheer amount of debris flying around could overrun the cpu's ability to track it fast enough. It was pretty fast though, only running into trouble when things got ridiculously explodey. But my way seems like it would be even more of a cpu hog than what you're doing, so I don't know.

What is a "large number" of mines?

Maybe you should do something like have each mine keep a list of nearby mines -- you'd only have to calculate it once, and update the mines when new mines were added. Then, when a mine blows, it already has a list of nearby mines to blow up as well, and they in turn already have a list, etc. (That might presume that mines don't move around though, else they'd have to update their lists as they moved -- though they could cheat there too, by cribbing off the lists of their already nearby mines instead of searching the total list of mines.)





#8 Amrazek   Members   -  Reputation: 202

Like
0Likes
Like

Posted 01 September 2008 - 09:03 AM

The target up to this point has been at least 1,000 mines. More is better though.

smcameron: That was something I considered initially, but the mines are mobile and move when the player is nearby. Maintaining the lists could work, but it seems like there's a lot of frame to frame calculation involved there.

oliii: Looks interesting, and somewhat similar to ToohrVyk's solution. Would this still work if mines very occasionally did teleport?

#9 Amrazek   Members   -  Reputation: 202

Like
0Likes
Like

Posted 02 September 2008 - 04:34 PM


Here's an update. I've implemented oliii's suggestion and it's definitely the way to go. I'm very satisfied with the results:

Static test:
Free Image Hosting
FPS: 50.67
Objects: 5040

Cascade explosion test (each of the rings of mines are exploding simultaneously)
Free Image Hosting
FPS: 40.1
Objects: 2558

The rendering itself appears to be the main bottleneck, as the frame rate quickly shoots up to 170'ish when there is nothing in view but the cascade continues.

Thanks for all of your suggestions!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS