How to make sure there's always a walkable path for enemies in a tower-defense game?

Question

I am making a 2D tower defense game. So far I have a 2d array which acts as a grid for my game. I'm able to place towers on it, run enemies and some dragging and tower firing stuff.

Now I am facing a problem in tower placement logic. I want that there's always a walkable path for enemies, meaning that the user should not be able to block the way completely by placing towers. Eg. if the user places towers vertically on a map, the algorithm must prevent the placement of a tower that will complete the vertical line. Or in any other way there must be at least one free (walkable) space so that the enemy can escape.

My current logic checks in all directions whenever tower has placed. If there is a tower upwards it calls the same function again on that upper tower until it hits a wall. It returns 1 for upward wall and 5 for downward wall and returns function(up/down tower) if there is a tower. here is the code:

int checkCollision(tower)
{                           
    if( there is a  tower up) 
    return checkCollision(up tower);

    if(there is a tower down) 
    return checkCollision(down tower);                                      

            ......all directions.....       

    if( there is a wall on UP )     
        return 1;

    if( there is a wall DOWN ) 
        return 5;

        ....all walls......

    return 0;   
}   

Now what I want is, simultaneously check if there is a northern wall and southern wall or check any other directions with any other possibility (like up-down, up-diagonal, down diagonal... and so on) to not let the user place a tower as there should be one place left for enemy.

I am unhappy with my code at the moment. I mean my code tells me that a wall is found but how can I check that a wall is found in one direction and a wall also found in another direction? I dont want to go into possibilities like:

if(checkCollision(tower) == 1 && checkCollision(tower) == 5) 
  "You cannot place"

I want something like:

    if( any combination of more than 2 wall found and there is entry/exit point in between)  //so it is wall to wall
    "You cant place"

I have also tried pre-calculating flags if there are walls on two sides (like up-down, up-diagonal etc.) then don't let the user place the tower but that still doesn't work.

Answer 1

Wouldn't it be simpler to use a pathfinding algorithm to check whether the AI still has a clear route? Presumably you use one already to make the enemies navigate from the entrance to the exit, so just run it with the tower added, and if it fails then the tower isn't allowed.

Answer 2

I assume you already have some code (using something like the A* algorithm) for the enemies to find a path to their destination. Every time the player tries to place a tower, you can just put a temporary obstacle where the tower would be and run the pathfinding code to check that there will still be a path for the enemies.

You can optimize this in various ways. For example, if the newly placed tower only touches at most one existing obstacle, it cannot block the path. You can also save the results of previous checks (at least until something changes), so that if the player tries the same location several times, you don't have to re-check it every time.

Also there are some techniques that only work in some cases. For example:

• If the possible locations of towers don't overlap, you can use a bridge-finding algorithm to find exactly which locations will block the path of the enemies.

• If the playing field is two-dimensional, there's a clever trick based on the fact that there exists a clear path from the left side to the right if and only if there does not exist a continuous wall from the top to the bottom. Thus, you can label each tower (or other obstacle) depending on which, if any, side of the playing field it is connected to by a wall.

  Maintaining these labels as new towers are added is easy and quick. If a new tower would link two sides together, it would block the path of the enemies. Of course, if a tower is removed, you still have to recalculate the labels, but you only need to do that when a tower is actually destroyed, rather than every time the player merely hovers the cursor over a potential location for a new tower.

Answer 3

I agree with SimonW that you should just run your pathing algorithm. For completeness, here is a trick used by Starcraft/Warcraft TD maps, which do not have a way to check if the pathing algorithm passes/fails.

Let's say enemies can come anywhere from the top of the buildable area, and have to move to anywhere below the buildable area; and there are walls to the left/right. Do a flood-fill of all towers touching the left-wall. If any towers found touch the right-wall, the path is blocked.

Answer 4

it should be more like

bool checkCollision(tower)
{
if(there is tower above)
  return checkCollision(tower above);
if(there is tower below)
  return checkCollision(tower below);
...
...
...
if(wall above)
  return 1;
if(wall below)
  return 5;
...
...
...
return 0;
}

then later in your code where you want to check whether to allow placing the tower or not:

if(!checkCollision(tower above) && !checkCollision(tower below) && !checkCollision(tower left)...[check all sides]...)
  //You can place the tower
else
  //You cannot place the tower

Also, change your algorithm to add the ability to return the coordinates of which tile of wall was found adjacent to the string of towers. Checking whether the same wall tile was returned and discarding that would allow you to go through loops of towers as well.

By loop of tower I mean (don't mind my ascii art):

--------------------------
|                        |
|   TT                   |
|TTTTTTTTT               |
|       X T              |
|       T                |
|                        |
En                       Ex
|                        |
|                        |
|                        |
|________________________|

It would not let you place a tower at X. The tower above, the tower on diagonals, the tower on the right and the tower below all will report wall collisions, however the coordinate of the wall tile will be the same. This is what you need to screen out as well.

Answer 5

Easy, I just built my first path finding program today, it took me a little over 2 hours and apart from declaring variables, it's only 27 lines of code including closing brackets.

program in your pathfinder an array for all your real walls, and an array for all your hipothetical walls, if a player wants to make a tower on a space, then the space selected is a hypothetical wall; Run your pathfinder to include hypothetical walls, if the program comes back with a path found then the tower can be built, if not then the tower isn't allowed to be built.

Cheers

Here's my code,

function PathFind(){

var keepgoing:Number=1;
var count:Number=1;
var smallcount:Number=0;
var keepgoing2:Boolean=false;
var startX:Array=[];
var startY:Array=[];
startX[0]=new Array();
startX[1]=new Array();
startY[0]=new Array();
startY[1]=new Array();
startX[0][1] = disc.loca;
startY[0][1] = disc.locb;
startX[1][1] = String(disc.loca)+"$";
startY[1][1] = String(disc.locb)+"$";


for(var c:Number=1; c<=keepgoing; c++){
    smallcount=0;
    for (var a:Number=1; a<=3; a++){
        for (var b:Number=1; b<=3; b++){
            if (a==2 || b==2){
                if(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].valid==true && SpaceII[startX[0][c]+(a-2)][startY[0][c]+(b-2)]==true){
                    count++;
                    smallcount++;
                    SpaceII[startX[0][c]+(a-2)][startY[0][c]+(b-2)]=false;
                    startX[0][count]=Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDx;
                    startY[0][count]=Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDy;
                    startX[1][count]=startX[1][c]+String(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDx)+"$";
                    startY[1][count]=startY[1][c]+String(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDy)+"$";
                    if(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].goal==true){
                        keepgoing2=true;
                        disc.stringA = startX[1][count].toString();
                        disc.stringB = startY[1][count].toString();
                        //thisText.text=startX[1][count] + "%" + startY[1][count] + "*";
                        success=true;
                    }                       
                }
            }
        }
    }
    if(keepgoing2==true){
        c = keepgoing;
    } else {
        keepgoing = keepgoing + smallcount;
    }
}

}

Basically, my code will create an array of paring X & Y strings, Then my moving units inherit the first successful pairing strings, and then they just disect the strings one segment at a time. Each coordinate is broken with a "$".

And the beautiful thing about the above code is that 'keepgoing' will only ever get as big as the grid size, and becomes more efficient with the more towers that are placed, it's efficiency being maximized when there is only one set path.

If you need any help with what I've got above here for you just let me know.