[Solved]: Name of Bomberman algorithm?

Problem Detail: 

Last couple of days I've been pulling my hair trying to find the name of a bomberman-esque algorithm which finds solutions to the question of where to place a single bomb so as to blow all targets up, either directly if all targets are within the blast radius (and axis) of a single bomb (placed in an empty cell) or via a chain-reaction by exploding nearby bombs which share the same x- or y-axis within the blast radius (hence the graph exploration issue).

I can describe the situation as following: given a square cell matrix S (the board state) of order n, containing symbols which differentiate between different objects(empty cells, rocks, targets and bombs), identify all empty cells P where a bomb with blast radius R can be placed so that all targets T will be destroyed. The other initially untriggered bombs also share the same blast radius.

Edit: The objects function as follows:

• Empty cell; The only place where a bomb could be placed. Allows explosions to pass through.

• Rocks; Blocks explosion waves.

• Bombs; Sits passively in a cell until reached by an explosion wave, at which point it explodes and sends an explosion wave outwards in the the x- and y- axis, up to the defined blast radius-length away.

• Targets; If reached by an explosion will be destroyed and counts towards the end goal of finding a solution where all targets are destroyed. Allows explosions to pass through.

I started out with a brute-force variant which simply went through all empty cells and started a search from there, which is quite inefficient if all objects are in one corner of a huge board. I came to the following pre-processing insight:

Since a solution is only regarded as valid if all targets have been destroyed, I can therefore begin my search from any random T and if the path generated from that initial T does not destroy all T then there is no solution to that particular S.

I've made an algorithm which manages to find some solutions, but not for all boardstates I'm testing with. (currently only works if no other target is within a blastradius-length from the starting target).

Is this description ringing any bells for you?

My first instinct was an MST, but I've been unable to merge that algorithm with my description above.

Asked By : shaungus2

Answered By : spyr03

As an example, Yellow denotes a target, red cells indicate the radius of the target such that if a bomb was placed in any of the red cells, it would blow up a target.

We can see from the picture that if we listed all the co-ordinates that are red

Pseudocode // Note that this tries to add the centre, or the x,y of the target twice for target in targets:     for i in range(-radius, radius):         set[target].add(target.x + i, target.y)         set[target].add(target.x, target.y + i) 

Then compare two sets for overlap, and if there is overlap between all of them, then we have an answer.

---

Pinky Purple is a bomb, and the blue is the radius that if another bomb explodes within, it will detonate too

Note that now we have to do a check before adding the co-ordinate to the set

If it is a blank cell it is easy, just add it.

If it is a bomb, dont add it, but add all the possible co-ordinates that will set off the bomb, and if during our checks, we encounter another bomb, we need to add that list too. I would make a recursive method here

def bombLinks(candidate.x, candidate.y, bombSet):     for i in range(-radius): //0 to the -radius shouldn't be checked for bombs, since thats where we came from         candidateType = blockAtCell(candidate.x + i, candidate.y)         if(candidateType = "Blank"):             bombSet.add(candidate.x + i, candidate.y)         candidateType = blockAtCell(candidate.x, candidate.y + i)         if(candidateType = "Blank"):             bombSet.add(candidate.x, candidate.y + i)      for j in range(radius):         candidateType = blockAtCell(candidate.x + j, candidate.y)         if(candidateType = "Blank"):             bombSet.add(candidate.x + j, candidate.y)         else if(candidateType = "Bomb"):             bombSet.add(bombLinks(candidate.x + j, candidate.y, bombSet))         candidateType = blockAtCell(candidate.x, candidate.y + j)         if(candidateType = "Blank"):             bombSet.add(candidate.x, candidate.y + j)         else if(candidateType = "Bomb"):             bombSet.add(bombLinks(candidate.x, candidate.y + j, bombSet))     return bombSet 

If it is anything else, we could ignore it, or if we want it so that explosions can't pass through certain blocks, we can do some more checks here

for target in targets:     for i in range(-radius, radius):         candidate.x, candidate.y = target.x + i, target.y         candidateType = blockAtCell(candidate.x, candidate.y)         if(candidateType == "Blank"):             set[target].add(candidate.x, candidate.y)         else if(candidateType == "Bomb):             set[target].add(bombLinks(candidate.x, candidate.y, []))          candidate.x, candidate.y = target.x, target.y + i         candidateType = blockAtCell(candidate.x, candidate.y)         if(candidateType == "Blank"):             set[target].add(candidate.x, candidate.y)         else if(candidateType == "Bomb):             set[target].add(bombLinks(candidate.x, candidate.y, [])) 

Whew, thats a lot of code, and you may have a better way of traversing the list of possible bomb locations, just don't forget that you can end up in an infinite loop if you check for bombs both directions

After all that, check the overlap between the sets. If there is an answer, great, otherwise pick the location that came up the most

Please excuse my terrible pseudo code, especially the loops

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45312