2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why not try reversing the goal? Start with all the targets T, and find all the locations of bombs that will blow it up. So if on the search it finds a bomb, you can extend the range to anything that would blow that bomb up. By the end you'll have a list of locations that will blow up each target, the location that occurs the most is the best place to put a bomb $\endgroup$ – spyr03 Aug 15 '15 at 20:28
  • $\begingroup$ Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. When posting a question, make sure to give enough context, and show how you tried to answer it on your own, so as to be very precise regarding your problem. This helps better answers. --- In this question, I do not understand the role of rocks and players. $\endgroup$ – babou Aug 15 '15 at 20:38
  • $\begingroup$ @spyr03 You mean starting a new search from the beginning for every target? Or a width-first iterating over all targets, saving possible locations on a queue for further ? My current implementation handles the chain reaction but it's just the initial pathing choice which can mess it up (if another target is just besides the initial T location which is used it would have to move backwards almost..maybe I should think about that) $\endgroup$ – shaungus2 Aug 15 '15 at 21:29
  • $\begingroup$ @babou Clear definitions for objects have been submitted. I tried to put the question more in general algorithm terms, since I wasn't sure my choice was correct and was wondering whether someone with more knowledge (or better memory) than me could immediately remember the name of an already existing algorithm suitable for this problem. If I were to post my implementation of all the C++ code (performance is on my mind) I would get into very minute specifics, which perhaps would be better framed as a question for the stackoverflow. $\endgroup$ – shaungus2 Aug 15 '15 at 21:34
0
$\begingroup$

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.

Example1, two targets

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

Example2, two targets and a bomb between

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

$\endgroup$
  • $\begingroup$ So having a pre-processing phase go through all targets, "extending" from each an area of candidate locations, up to the blast radius length away and halting short of it if you encounter a rock or bomb. All bombs encountered are added to a bomb-queue for later. One way to check for your darkred overlap locations is to have the location "x-y" as key and an integer as value, just add 1 to each extended empty cell as you go, although this would require either a board size matrix of ints or an array of structs with location and internal counter. Then just check if any loc.counter == totalTargets $\endgroup$ – shaungus2 Aug 16 '15 at 2:14
  • $\begingroup$ @shaungus2 Sounds reasonable, be careful of halting if you reach a bomb, because you may miss a location just after that will set off that bomb and another chain that the bomb would have missed $\endgroup$ – spyr03 Aug 16 '15 at 2:20
  • $\begingroup$ Right, perhaps better to not halt the extending in that direction if encountered a bomb - or wont that solve itself in the next phase when the discovered bombs extend their "trigger" area ? In this first phase. if you didn't find any overlap or bombs, and T > 1, then there is no solution to this S - no need to try and place your bomb on every extended cell and test. Now you extend the areas from all encountered bombs in the previous, up to the blast radius, rock or bomb. Bombs are added to the queue. You pass through targets if the blast range allows it. $\endgroup$ – shaungus2 Aug 16 '15 at 3:04
  • $\begingroup$ You repeat this process until you've gone through the bomb-extending-cycle without finding any new bombs. Now you have a result of a large list of possible places to place your bomb, but a lot of those places are perhaps leaf-nodes with only a value of 1 in the big array I mentioned earlier. In these places you can't find any solution either, since even if you do place your bomb and trigger other bombs, finding a long chain, there won't be a target on this branch, since in that case those bombs would already have exploded from the other direction, by those very targets. A heatmap perhaps? $\endgroup$ – shaungus2 Aug 16 '15 at 3:14
  • $\begingroup$ @shaungus2 That would be right, I'm not sure how to continue tbh $\endgroup$ – spyr03 Aug 16 '15 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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