   Creating a text-based explosion
  Hi.I'm at the final stages of my first game, which is a text-based strategy game. However I still have a slight problem.I have an object, which is basically a napalm bomb, and you can determine it's blast radius via a command-line parameter. The explosion should look like this (radius = 3) when exploded in xy-coordinate (3, 3).  0 1 2 3 4 5 60 . . . & . . .1 . . & & & . .2 . & & & & & .3 & & & & & & &4 . & & & & & .5 . . & & & . .6 . . . & . . .Walls can prevent the napalm from spreading around like this:  0 1 2 3 4 5 60 . . . & . . .1 . . & & & . .2 . & & & & & .3 & & & & & # .4 . & & & # . .5 . . & & & # .6 . . . & . . .Napalm can spread anywhere as long as it's (in this example) three blocks away from the original explosion coordinate.I decided to create a recursive function to take care of the explosion. The basic idea of it is that it calls the explode-function on every cardinal direction, so it can spread easily.The idea is just great, but the implementation is somehow flawed. I created a simple testcase for you, which compiles but segfaults. I think there's a infinite loop of somesort, but I can't figure out how to fix it. If you comment out the last two "if(notWall(...)" parts, you'll see that the explosion works on one direction.Anyway, thanks in advance. Here's the code:#include <iostream>#include <string>#include <vector>#include <cstdlib>using namespace std;void printMap(const vector<string>& World);bool notWall(const int xCoord, const int yCoord, const vector<string>& World);void explode(int x, int y, vector<string>& World);int main() {    vector<string> World;    for(int i = 1; i <= 10; ++i) {   string row = "";   row.assign(10, '.');   World.push_back(row);    }    explode(5, 5, World);    printMap(World);}void explode(int x, int y, vector<string>& World) {    if( abs(x - 5) + abs(y - 5) == 5 ) {   return;    }    else {   World.at(y).at(x) = '&';   if(notWall(x + 1, y, World)) {  explode(x + 1, y, World);   }   if(notWall(x, y + 1, World)) {  explode(x, y + 1, World);   }   if(notWall(x - 1, y, World)) {  explode(x - 1, y, World);   }   if(notWall(x, y - 1, World)) {  explode(x, y - 1, World);   }    }}void printMap(const vector<string>& World) {    for(int i = 0; i < World.size(); ++i) {   for(int k = 0; k < World.at(i).size(); ++k) {  cout << World.at(i).at(k) << " ";   }   cout << endl;    }}bool notWall(const int xCoord, const int yCoord, const vector<string>& World) {    if(xCoord < World.at(0).size() && xCoord >= 0) {   if(yCoord < World.size() && yCoord >= 0) {  if(World.at(yCoord).at(xCoord) != '#') { return true;  }   }    }    return false;}
  It looks to me like the cells are calling each other. So for example a cell calls explode() on a left cell which calls explode() on the original cell, which calls the left cell again, etc etc. You need to add a check somewhere to see if a cell already exploded, and if it did, ignore it.   ;  The easiest way to get your explosion recursion to terminate would probably be to pass a radius argument as part of the function signature, and decrement it by one for every recursive step. You could also not recurse into a location if it's a wall or already contains napalm.   ;  I'm guessing you keep drawing ampersands even if there's already one there, resulting in an infinite loop. Let's say we change the notWall function slightly:if(World.at(yCoord).at(xCoord) != '#' && World.at(yCoord).at(xCoord) != '&') { ..Does that solve anything? Of course the function name would now be 'incorrect', but it should quickly point out the problem.   ;Quote:Original post by WanMasterI'm guessing you keep drawing ampersands even if there's already one there, resulting in an infinite loop. Let's say we change the notWall function slightly:if(World.at(yCoord).at(xCoord) != '#' && World.at(yCoord).at(xCoord) != '&') { ..Does that solve anything?Thanks a lot. Works like a charm :);  And then another problems shows up :)If I have a map like this  0 1 2 3 4 5 6 7 8 90 . . . . . . . . . .1 . . . . . . . . . .2 . . . . . . . . . .3 . . . . . . . . . .4 . . . . . . . . . .5 . . . . . . . # . .6 . . . . . . . # # .7 . . . . . # # # . .8 . . . . . . . . . .9 . . . . . . . . . .and the explodes at (6,6) (radius = 5) the explosion shows up like this:    1 2 3 4 5 6 7 8 9  . . . . . . . . . .1 . . . . . . & . . .2 . . . . . & & & . .3 . . . . & & & & & .4 . . . & & & & & & &5 . . & & & & & # & &6 . & & & & & & # # &7 . . & & & # # # & &8 . . . & & & & & & &9 . . . . & & & & & .The recursion only checks the difference between the coordinates, which doesn't notice the walls. In this example the coordinate (8, 7) is 3 blocks away from (6,6), but if you consider the walls then it's 9 blocks. Should I make a counter which checks how many blocks the recursion has gone through? Or is there a easier way?Thanks again.   ;  I would think you would need to implement a line of sight, where as if a explosion happens at X,Y and is blocked at X+1,Y+1, the tiles in that direction are invalided for that particular explosionThen when spreading your napalm just check and see if that tile is invalided for this explosionX+1,Y+1X+2,Y+2does this sound right?Assuming you wanted it like this    1 2 3 4 5 6 7 8 9  . . . . . . . . . .1 . . . . . . & . . .2 . . . . . & & & . .3 . . . . & & & & & .4 . . . & & & & & & &5 . . & & & & & # . .6 . & & & & & & # # .7 . . & & & # # # . .8 . . . & & . . . . .9 . . . . & . . . . .Explosion happens at 6,6we have a wall at 6,7Source - wall = 0,1so we take wall location + 0,1 for radius (5) - wall location from source (1)  - for the source of the napalm = 3 tilesand we could invalidate6,86,96,10Explosion happens at 6,6we have a wall at 7,7Source - wall = 1,1so we take wall location + 1,1 for radius (5) - wall location from source (1)  - for the source of the napalm = 3 tilesand we could invalidate7,78,89,9   ;Quote:Original post by yewbieI would think you would need to implement a line of sight, where as if a explosion happens at X,Y and is blocked at X+1,Y+1, the tiles in that direction are invalided for that particular explosionThen when spreading your napalm just check and see if that tile is invalided for this explosionX+1,Y+1X+2,Y+2does this sound right?Assuming you wanted it like this    1 2 3 4 5 6 7 8 9  . . . . . . . . . .1 . . . . . . & . . .2 . . . . . & & & . .3 . . . . & & & & & .4 . . . & & & & & & &5 . . & & & & & # . .6 . & & & & & & # # .7 . . & & & # # # . .8 . . . & & . . . . .9 . . . . & . . . . .Explosion happens at 6,6we have a wall at 6,7Source - wall = 0,1so we take wall location + 0,1 for radius (5) - wall location from source (1)  - for the source of the napalm = 3 tilesand we could invalidate6,86,96,10Explosion happens at 6,6we have a wall at 7,7Source - wall = 1,1so we take wall location + 1,1 for radius (5) - wall location from source (1)  - for the source of the napalm = 3 tilesand we could invalidate7,78,89,9This would work well for e.g. grenade explosions, but I think the OP's idea of the napalm bomb is that it can spread anywhere (even behind walls) as long as it spreads across maximally radius number of cells.To the OP:Yes, you will need a counter, fortunately it's trivial to implement. Check SiCrane's post again.EDIT: spell check   ;  The statement ... && World.at(yCoord).at(xCoord) != '&' suggested by VanMaster seemed feasible at first, as it will work as a base case for the recursion. But it turned out that it will terminate the recursion pre-maturely in some cases.I found that simply using the counter suggested by sicrane as a base case will work perfectly.eg:void explode(int t, int x, int y, vector<string>& World) {   if(t <= 0) // the base case   return;    World.at(y).at(x) = '&';    if(notWall(x + 1, y, World)) {   explode(t-1, x + 1, y, World);    }    if(notWall(x, y + 1, World)) {   explode(t-1, x, y + 1, World);    }    if(notWall(x - 1, y, World)) {   explode(t-1, x - 1, y, World);    }    if(notWall(x, y - 1, World)) {   explode(t-1, x, y - 1, World);    }};Quote:Original post by pulpfistThe statement ... && World.at(yCoord).at(xCoord) != '&' suggested by VanMaster seemed feasible at first, as it will work as a base case for the recursion. But it turned out that it will terminate the recursion pre-maturely in some cases.I found that simply using the counter suggested by sicrane as a base case will work perfectly.Thanks. This one does actually work, but it is _extremely_ slow when the radius is more than 10. Is it even possible to optimize it easily? Seems to me that it's time to get back to drawing board and think this through again :)I noticed the problem with the ... && World.at(yCoord).at(xCoord) != '&' too. It would make it so much faster, but too bad it's not possible to use it as it would ruin the algorithm.[Edited by - induction on May 10, 2009 4:58:09 PM]