Defining path for tower defense game

Question

I'm currently developing a tower defense game as a part of a group project in school. This game will be programmed in C++ using SFML. We are having trouble with finding a good way to define the path our enemies will take. Our maps are generated from a .txt-file:

In the .txt-file, ! is the start, = is the path, # is a wall, and ? is the end. This results in a grid like this:

Our plan is to add the coordinates of every path-grid as nodes to a linked list. The enemies would then have to follow the nodes in the list. So far we have tried to add the nodes to a linked list while generating the map. The map is generated by reading the .txt-file line-by-line (left-to-right and top-to-bottom).

if (file.is_open()) {
while(getline(file, line)) {
  for (auto &ch : line) {
    if (ch == '!') {
      tiles_.push_back(
        std::make_shared<GameCell>("assets/road.png", y, x, true, false, true));
    } else if (ch == '#') {
      tiles_.push_back(
        std::make_shared<GameCell>("assets/grass.png", y, x, false, false, false));
    } else if (ch == '?') {
      tiles_.push_back(
        std::make_shared<GameCell>("assets/road.png", y, x, true, true, false));
    } else if (ch == '=') {
      tiles_.push_back(
        std::make_shared<GameCell>("assets/road.png", y, x, true, false, false));
    }
    y += 100;
    
  }
  x += 100;
  y = 0;
}
file.close();
}

The problem with this is that it only works if the path goes right and down. If the path goes left or up the nodes end up in the wrong order in the linked list.

How can we order the nodes the right way? Or are there better ways of doing this?

Answer 1

This is quite simple once you have already loaded the file into memory: Start from the start tile. Then look for a road tile next to it. Then look for a road tile next to that (other than the one you just came from). Then look for a road tile next to that (other than the one you just came from). Then look for a road tile next to that (other than the one you just came from). Etc. When you get to the finish tile, you are done.

"Look for a tile next to" can just mean checking the tiles up, down, left and right of the current tile.

This means your program needs to have the ability to look up the tile at a specific location and find whether it is a road or not. You can implement this with a 2D array of tiles. Or - as you already have - a 1D array where you can calculate the index based on X and Y.

If your game has multiple paths, a more complicated algorithm is needed - but your game does not have multiple paths.

Answer 2

User253751's answer is good for the example you've given but in a more advanced map it'll break easily. The problem with that idea is that if you have 2 paths joining together doesn't matter where, The enemy will have to choose either one or the other, and it'll have to know which direction is the end. Now this sounds easy and all "just have it go the direction the end is in" but its not that simple. There could be situations in which the paths wont be in the direction making that map broken. As a programmer you have to make sure that no matter what, your program wont break.

Totally the easiest way would be to revamp the way you enter your map into the program. have a csv type data structure with numbers telling you the next directions

0 for wall 1 for up 2 down 3 left 4 right 5 start 6 finish

then you just put those numbers in. if not wall then tile. numbers correspond to next tiles. easy directions without any algorithm business. File to read would look something like this for your example:

52;2;2;2;3;0;0;0
0;0;0;0;3;0;0;0
0;0;0;0;2;2;3;0
0;0;0;0;0;0;3;0
0;0;0;0;0;0;3;0
0;0;0;0;0;0;6;0

Really easy to implement and read. You read every digit for every tile. if has 5 then tile is start. if has 6 then is end. the rest are direction digits for the nexts vector. This way you can also easily implement splits by just putting more than one direction digit next to each other. each number is each tile here: 52 is start tile direction right. The nexts vector is a vector in each tile that acts a bit like your linked list showing you the next tiles from that tile you're on in a way of showing the direction to go to from there. Enemies can pick randomly from any of the tiles in that next tile to go to.

OR if you want to do something harder:

I suggest a little different approach:

• have a 2 dimensional array (a matrix) which will store each tile
• have the tiles have an array of 'nexts'
• the nexts will only store next path tiles
• the vector of nexts will be the direction in which to move
• you load in the walls and tiles into the vector normally via if # emplace back tile with value or desc "wall" if not #, then path etc etc
• now you need to know the direction in which to go. Let each tile have variable 'visited' which will be bool value.
• in loop go from start to finish adding next tile to vector of nexts of previous tile. Set current tiles' visited to true.
• for split path add both next tiles to that tile and for every of those nexts recursively continue same program.
• when 2 paths join happens program will think its a split. let it continue,
• when the above join as 'split' happens, it continues UNTIL it goes back to the actual split before. if the actual split before's next is the tile you're on A.K.A. if you're going in the opposite direction than the split says, recursively back track your steps to the joing that was understood as a split and end that loop. ending that loop and returning those visited bool values back to zero will enable the previous split to continue to the join. I'll try to explain with pictures:

Single path:

On the picture above, On each tile it checks the tiles next to it. If its tile AND its not visited, next for current tile is that next tile. Repeat. No problems here. Will always work

Split/join/advanced: For each split, it recursively does the same thing as for single...

split 1 path 1 split 2 path 1:

split 1 path 1 split 2 path 2

split 1 path 2 split 2 path 1

split 1 path 2 split 2 path 2

So above i showed you every possible turn it could do. By themselves they dont do much but if you stack them, they give you the paths.

so first the first image is done, Its fine cool and all. Then the second is done on top of the first. But the first split has nexts vector as up AND down. Since we are going up and the first split is visited and has opposite direction, WE CANCEL and revert back to second split from which we came from and we stop that iteration of recursion. We're left with image 1 again. Then since we exhausted every recursive next in the second split, the recursion rolls back to previous split to complete it's next's. Image 3 is tried. image 3 fails because that tile above the second split has already been visited and has opposing direction already too. if it was already visited, we stop that iteration of recursion. Image 4 is tried. Same idea as image 3. we get to split that has been already visited so we break and stop there. No more recursions left so we finish the recursive loop completely. We're left with the path for any amount of splits and joins.

This might not be the best option and with bigger and really complex maps it might not fully 100% work but with some tweaks on that level of difficulty i think it will be fine.