Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am simulating explosions in a 2D maze game.

If an explosion occurs in an open area, it covers a circular region (this is the easy bit.)

However if an explosion occurs in a narrow passage (i.e narrower than the blast range) then it should be "compressed", so that it goes further and also it should go around corners.

Ultimately, unless it is completely boxed-in, then it should cover a constant number of pixels, spreading in whatever direction is necessary to reach this total area.

I have tried using a shortest-path algorithm to pick the nearest N pixels to the origin avoiding walls, but the effect is exaggerated - the blast travels around corners too easily, making U-turns even when there is a clear path in another direction. I don't know whether this is realistic or not but it is counter-intuitive to players who assume that they can hide around a corner and the blast will take the path of least resistance in a different direction.

Is there a well-known (and fast) algorithm for this?

share|improve this question
1  
The intuition and counter-intuition is is deviated by the sight of too many movies! just look to the Heat equation... –  FxIII Jun 25 '11 at 21:15
add comment

4 Answers 4

up vote 2 down vote accepted

Look at water/fluid simulations. The basic idea is that the area is divided into little cubes and each one has a velocity that it's pushing and a "pressure" gauge of how hard it's pushing into the adjoining cubes. All things being equal your explosion will grow outwards in a circle/sphere.

In a situation where the cubes can't expand in one direction (hallways) they'll end up pushing towards the way out.

This might be a good place to start: http://cowboyprogramming.com/2008/04/01/practical-fluid-mechanics/

share|improve this answer
add comment

I've done something to this similar recently in my game. Mine was for water flow, but it could be adapted for explosions. I've already adapted mine for lighting too :).

Essentially your explosion starts with a fixed amount of "blast", this is the total area your explosion covers. Through each iteration of moving your blast outwards you're subtracting from this total number of "blast" pixels. When the count runs out, your explosion stops.

When moving outward, the pixels lined up with the vector that's directly away from the blast is allowed to channel the most blast pixels, it has a higher throughput. This way the paths directly away from the blast get the most blast throughput. You can add rules that when the blast changes direction, the throughput is halved or whatever ends up working best. This ends up being very cellular automata. You define the rules of a cell, and they go out and do all the work.

In my image, black represents walls and you see the height of each cube defines the throughput and the color represents it's current pressure from red to white.

Basically you have a bucket of blast and you need to define the size and direction of the pipes leading away from the blast to flow that blast out. High pressure to low.

What inspired this algorithm for me was Dwarf Fortress and the way the water flowed with pressure. Obviously I don't know exactly how it was done in Dwarf Fortress, but I hacked together my own version that works pretty well. There's a little more info on how I did my algorithm and an interview with the Dwarf Fortress creator here.

enter image description here

share|improve this answer
1  
Oh I love those physical inconsistent models! This is a classical aesthetics issue. Once you get bored of realism you will like something different, as the impressionism followed the romanticism's realism. –  FxIII Jun 26 '11 at 11:34
add comment

This is a fluid dynamics problem, there is no simple way of solving this in a realistic fashion.

In any case, you only need "realism" as far as it gives the game the right feel.

Here is a couple of suggestions:

You might not want the area to stay exactly the same, that could get out of hand in very tight scenarios, so in your equation you could count far pixels as taking more of the blast. Eg. An explosion has 100 blast points, for the centre pixel you subtract 1 point, for those next to it 2, then 3 etc. so an explosion that has to reach far will spend more points per pixel on average.

For the corner thing, in your pathfinding you can add a penalty for corners, so any curve on the path will count as extra distance.

share|improve this answer
    
Add weight is a great idea! –  FxIII Jun 25 '11 at 21:38
add comment

It is just an idea (physically incorrect but who cares?) what about a straight-first aproach?

Starting from the explosion the blasts move to the four directions losing a fixed amount of energy per tile, once a blast keep a direction it will follow it, ignoring the side apertures, until it find an obstacle:

if there are a single way to go(a turn), follow it and go ahead in that direction;

if there are two possible directions (T-intersection) split the blast in two (loosing the energy faster)

if is a dead end stop the blast (this will leave more energy for the other blasts).

Stop when you run out of energy. If no direction are possible but you have still some energy you may choose to stop anyway or to start to consider the skipped + intersections.

This may work if you are in a tiled world. If is not your case, you may try a ray casting aproach: working with growing circles testing if the pixel is in visibility from the explosion point. Once again each pixel set as blast decreases the explosion's energy so you have a stop criterion.

share|improve this answer
1  
Physically this won't be right, but might still look good. Essentially this a breadth-first traversal of a search tree. The root node has at most four children (one for each direction), children have at most three children (one for each exit direction). You can eliminate duplicate nodes from the tree (so traversing ESW, you exclude N from that child because it's the original node and has already been traversed). If a node is invalid (because it's a wall), it and its children can be skipped. Traversing a valid node costs X energy (different node types might take different amounts of energy). –  MrCranky Jun 26 '11 at 9:59
    
This can be one possible good implementation –  FxIII Jun 26 '11 at 11:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.